Форум DL

Мой профиль

Пишу C

Мой профиль

E 2020
Решение:
Используя Формулу для нахождения центра масс:
X=1+Z[(4i+1+ji)/(4i+3-ji)] (Z от i=2 до i=n/2)
Y=n/4-Z[1/(f^2+f+1)]/6-1/6 (Z от i=2 до i=n/2)
f=2i-ji-1
Z - знак суммы
i - какая по счету '('
ji -номер '(' в строке

Можно перебрать всевозможные неповторяющиеся варианты составления строки из '(' и ')'
т.к. формула зависит от каждой скобочки и скобочки не связанны никакой зависимостью, то меняя расположение одной скобочки меняется только одна часть формулы
Тогда будем перебирать все варианты(их 171)
будем хранить в векторе значения для каждой i-той '(' и результат. далее будем перемещать n/2 скобочку вправо пока это возможно, если мы достигли конца передвигаем n/2-1 скобочку на 1 единицу вправо и ставим n/2 скобочку на следующую позицию продолжаем выполнять этот алгоритм пока это возможно, когда мы дойдем до конца перемещаем n/2-2 скобочку на 1 вправо, n/2-1 на следующую позицию, n/2
на следующую позицию, продолжаем выполнять этот алгоритм...
когда нам нужно переставить первую скобочку (а это нельзя) заканчиваем и ищем нужный нам ответ(получившееся значение храним в переменной, а также множество ji, если погрешность стала меньше)
при перемещении i-той скобочки меняется i-тая часть суммы, тогда будем забирать из вектора значение i-той '(' перед переносом и отнимать это от результата, пересчитываем после переноса и прибавляем это к результату, а также меняем i-тое значение вектора, значение храним в переменной, а также множество ji, если погрешность стала меньше.
Выводим наш ответ.
Пример:
(((()))) -> ((()())) -> ((())()) -> ((()))() -> (()(())) -> (()()()) -> (()())() -> (())(()) -> ()((()))

Мой профиль

C 2020
Итоговое решение:
сначала пройдемся по графу и удалим все ребра принадлежащие циклам(либо обозначим их как 1, a остальные как 0).
далее будем идти из каждой точки дфсом и когда мы найдем два тупика (они есть если у этой точки есть хотя бы одно ребро) закинем пару этих вершин как часть ответа и удалим ребра между этими вершинами(пометим их как 1), будем это выполнять для каждой точки.

Мой профиль

Егор Короткевич:

C 2020
15 6
13 1 2 3 4 1 5 6 7 8 9 7 10 5
2 10 11
2 10 12
2 9 13
2 9 14
2 9 15
0 0
--------
4
4 5
13 14
9 15
11 12
0

Мне кажется, что тут должно быть
15 6
13 1 2 3 4 1 5 6 7 8 9 7 10 5
2 10 11
2 10 12
2 9 13
2 9 14
2 9 15
0 0
--------
4
5 1
13 14
9 15
11 12
0

Мой профиль

Егор Короткевич:

C 2020
Итоговое решение:
сначала пройдемся по графу и удалим все ребра принадлежащие циклам(либо обозначим их как 1, a остальные как 0).
далее будем идти из каждой точки дфсом и когда мы найдем два тупика (они есть если у этой точки есть хотя бы одно ребро) закинем пару этих вершин как часть ответа и удалим ребра между этими вершинами(пометим их как 1), будем это выполнять для каждой точки.

Я написал C по этому решению
Я реализовал вот так:
1) удалил циклы
2) из каждого листа находим какой-нибудь другой лист и удаляем путь между ними. При удалении рёбер проверяем появились ли новые листья.
Конец

До этого я хотел реализовать в один проход(объединить пункты 1 и 2) используя не рекурсию, а стек. Сохраняя в стеке всю нужную информацию для поиска циклов и пар листьев,
но всё стало как-то сложно и я понял, что не очень понял как я это сделаю.
Поэтому переписал заново в ту реализацию, которая выше.

Один тест не пройден, но мне кажется, что у Егора в тесте ошибка.

Мой профиль

Егор Короткевич:

I 2020
Ставки!
...
наталкивает мысль о использовании вероятности(рандома)
HELP

Это что-то очень странное. Точного решения у нас быть не может. Нужно просто угадать эвристику.

Я написал реализацию с такой эвристикой:
На каждой ставке:
Для "0" считаем сумму 2^(min_errors - errors[i]) для всех игроков i, которые поставили на "0"
Для "1" считаем сумму 2^(min_errors - errors[i]) для всех игроков i, которые поставили на "1"
min_errors -- минимальное количество ошибок среди всех игроков
errors[i] -- количество ошибок игрока i в текущий момент
Делаем ставку на ту цифру, у которой больше сумма.

Благодаря такой эвристике мы ставим на то же, что и хорошие игроки. При этом каждая ошибка игрока уменьшает его важность в два раза.
Можно использовать какую-нибудь другую эвристику. Например уменьшать на 1 важность игрока за его ошибки.

Я протестировал на случайном вводе эту тактику(со степенью двойки). Сделал около 200 тестов. Тесты показали, ... и тут я хотел хвастаться, но заметил, что
На случайных тестах и я и самый крутой игрок ошибаемся где-то в 5000 случаев. Поэтому тесты пройдены.
Этим я хочу сказать, что случайные тесты не показательны.

Мой профиль

B 2019
Дана строка s из заглавных английских букв, Мы можем в любом месте между буквами а также на концах строки вставить букву.
Если подстрока из одинаковых букв увеличилась(добавили букву или она соединилась с подстрокой с такими же буквами) и ее длина >=3 то она уничтожается, а подстроки справа и слева соединяются.
Нужно подсчитать кол-во способов поставить букву так чтобы вся строка уничтожилась(если такое не возможно - ответ 0)
Ввод:
s (1<=s.length()<=3*10^5)
Вывод:
c (кол-во способов)
Решение:
Логически очевидно что может быть всего-лишь одна подстрока в которую можно вставить букву чтобы удалить всю строку, тогда с=s1.length()+1, где s1 - длина этой подстроки.
Чтобы найти подстроку достаточно выполнять алгоритм пока не останется нужная нам подстрока.
Алгоритм:
взять самую левую и самую правую подстроку и уничтожить их
при условии:
1. суммарное кол-во букв >=3
2. они состоят из одинаковых букв
Если не выполняется хотя бы одно условие - вывести 0
Под подстрокой я подразумеваю подстроку состоящую из одинаковых букв и буква слева и справа от подстроки не равна буквам из которых состоит эта подстрока.

Мой профиль

E 2019
Выборы...
Дан двумерный массив состоящий из n кандидатов(столбцы) и m участков (строки).
Наша задача заставить n-того кандидата проиграть(чтобы кто-то набрал >= голосов чем он)
Мы можем уничтожать участки -> все голоса на этом участке исчезнут
Но нужно уничтожить минимальное кол-во участков
Ввод:
n m (2<=n<=100 - кол-во кандидатов, 1<=m<=100 - кол-во участков)
a11 a12 ... a1n - (aij, голоса за j-того кандидата на i-том участке)
a21 a22 ... a2n
...............
am1 am2 ... amn
Вывод:
c (кол-во уничтоженных участков)
i1 i2 i3 i4 ... (номера уничтоженных участков)
Решение:
Чтобы нужный кандидат нам проиграл нужно чтобы выиграл любой другой, тогда будем отдельно рассматривать минимальное количество уничтожения участков чтобы победил каждый кандидат и выбирать из этого минимальный, а после заново рассматривать этот случай чтобы не хранить в памяти удаленные участки для каждого кандидата.
чтобы определить какие участки нужно удалить достаточно составить массив разности, отсортировать и удалять участки с самой большой разницей(которые не в нашу пользу) покуда сумма массива разности не станет в нашу пользу. Далее берем минимальное кол-во удаленных участков среди всех кандидатов (кроме n-ого) и теперь проделываем тоже самое только теперь запоминаем номера удаленных участков и выводим ответ.
Возможно что необходимо удалить 0 участков.

Мой профиль

L 2019
Лексикография.
Дана строка s, нужно составить из нее n слов длиной L в лексикографическом порядке(наименьшее сверху) так чтобы k-тое слово было
самым лексикографически минимальным из возможных вариантов.
Ввод:
n L k (1<=k<=n<=1000 1<=L<=1000)
s
Вывод:
s1
s2
...
sn
Решение:
Отсортируем строку s теперь каждому слову до k-того(включая) присваиваем первому символу k символов начиная с начала строки s.
Если есть строки у которых первый символ равен первому символу k-того слова то помечаем их и выполняем алгоритм 1 пока не останется лишь k-тое слово или максимальная длина слова будет достигнута, После выполняем Алгоритм 2.
Алгоритм 1:
добавляем по одному каждому слову не взятые символы начиная с начала строки s всем словам кроме k-того
далее добавляем первый не взятый символ k-тому слову. Если есть помеченные слова у которых последний символ равен последнему символу k-того слова - оставляем их помеченными, у остальных убираем метку. Снова выполняем Алгоритм 1 пока не
останется лишь k-тое слово или максимальная длина слова будет достигнута, После выполняем Алгоритм 2.
Алгоритм 2:
Добавляем k-тому слову не взятые символы начиная с начала строки s до достижения длины L, после добавляем все оставшиеся символы любым словам до длины L.
В конце делаем сортировку по Лексикографии.

Мой профиль

K 2019
Задача на комбинаторику.
Дано t чисел. Пусть есть некоторое число kj, тогда можно создать множество Pi.
Pj - множество которое состоит из остатков от последовательного деления kj на 2,3,4,... до того момента пока kj не станет равным нулю(оставляем только целую часть при каждом делении)
Нужно посчитать кол-во чисел (не включая это) которые также дает это множества (числа в данном множестве не привязаны к индексам иначе говоря {1,1,2} и {1,2,1} - это одно и то же множество)
Ввод:
t (1<=t<=50000)
k1 (1<=ki<=10^18)
k2
..
kt
Вывод:
a1
a2
..
at
Решение:
Сначала найдем данное множество деля kj на 2,3,4... и записывая остатки.
Пусть теперь каждой позиции числа из этого множества соответствует число на которое мы делим(i+1).
Далее будем считать кол-во не повторяющихся перестановок так чтобы число не превышало i+1, это и будет наш ответ т.к. каждому неповторному множеству соответствует единственное число.
Перед тем как начать подсчет для удобства отсортировать массив.
Формула для подсчета:
aj = C[n]*C[n-1]*C[n-2]*...*C[1]
где n - номер последнего элемента в массиве, С[d] - сочетание из (b[d]-Z(f[e])) по f[i] для d-того элемента.
Z(f[e]) - сумма f[e] от e = d+1 до e = n (e изменяется слева направо и при d = n, Z(f[e]) = 0)
f[d] - кол-во одинаковых чисел в подмножестве с номером d
b[d] - n+1-r[d]
r[d] - значение чисел в подмножестве с номером d
d - номер начиная с начала подмножества одинаковых чисел

Частный случай(не совсем)
нужно отнять эту же формулу только убрать один 0 и уменьшить n на 1
Это можно делать только в случае, когда есть 0 и если его убрать ни одно число не будет >= i+1
GL

Мой профиль

Если не трудно, добавь базовый(е) тест(ы). Какая из них Е задача?

Мой профиль

Тесты B, E, L, K 2019

B:

BBWWBB
-----------------
3

BWWB
-----------------
0

BBWBB
-----------------
0

OOOWWW
-----------------
0

WWWOOOOOOWWW
-----------------
7

LLWWLLWWLLWWLL
-----------------
3

LWWLWWLLWLL
-----------------
3

LWLWWLLWLL
-----------------
0

E:

5 3
6 3 4 2 8
3 7 5 6 7
5 2 4 7 9
-----------------
2
3 1

2 1
1 1
-----------------
0

3 3
2 3 8
4 2 9
3 1 7
-----------------
3
1 2 3

3 3
4 6 4
3 2 4
3 1 4
-----------------
1
3

3 3
3 2 0
1 4 4
4 1 4
-----------------
0

L:

3 2 2
abcdef
------
af
bc
ed

2 3 1
abcabc
------
aab
bcc

3 3 2
bbbbbbbbc
------
bbb
bbb
bbc

K:

10
1
2
3
4
5
6
7
8
11
123456
------
0
0
0
0
0
0
1
1
127

Мой профиль

Написал B. На всех предложенных тестах работает. Завтра допишу остальные.

Мой профиль

Написал E. Чуть по-другому реализовал. От каждого столбца, кроме последнего, отнял последний(массив разности), потом прошёлся по каждому столбцу, находил кол-во элементов меньше 0, запоминал их и рассматривал, чтобы это кол-во элементов было минимально. В начале я нахожу сумму по столбцам, сортирую по убыванию и если элементы равны, то сортирую по возрастанию номеров. Если номер первой суммы не равен n, то ответ 0. На данных Егором тестах работает.

Мой профиль

Егор Короткевич:

3 3
4 6 5
4 2 4
4 1 3
-----------------
1
1

Тут ответ 0. Т.к у первого кандидата 12 голосов и у n-ого(3) тоже 12.