Задача А. Автодополнение
Задача B. Фотография в блог
В этой задаче так-же нужно было переборное решение.
Сначала перебираем первую сторону как степень двойки(пускай это будет S) , когда мы знаем это число пытаемся определить максимальную 2ю сторону(пускай это будет L) которую мы можем получить(возможно ее мы не можем получить): первый вариант S*0.8>m ,тогда L=0 (мы ее не можем получить можно поставить 0, и произведение будет 0), второй вариант S*1.25<m , тогда L равно максимальному целому числу меньше равному S*1.25, иначе S*0.8<=m<=S*1.25 L=m. Посчитав их проверяем на оптимальность. Аналогично делаем и для второй стороны. Единственно что нужно помнить в случае равности ответа приоритет отдается тому, когда высота больше.
Сначала перебираем первую сторону как степень двойки(пускай это будет S) , когда мы знаем это число пытаемся определить максимальную 2ю сторону(пускай это будет L) которую мы можем получить(возможно ее мы не можем получить): первый вариант S*0.8>m ,тогда L=0 (мы ее не можем получить можно поставить 0, и произведение будет 0), второй вариант S*1.25<m , тогда L равно максимальному целому числу меньше равному S*1.25, иначе S*0.8<=m<=S*1.25 L=m. Посчитав их проверяем на оптимальность. Аналогично делаем и для второй стороны. Единственно что нужно помнить в случае равности ответа приоритет отдается тому, когда высота больше.
Задача С. Лягушонок
Ответом будет последовательность: 1 ,N ,2 ,N-1, 3 ,N-2 ...
Доказать это можно очень просто, так-как разница между числами всегда будет уменьшаться на единичку.
Алгоритм задачи такой: идем слева на право и берем для каждого человека из первого множества самого ближнего из второго , который стоит не левее его самого , ну то есть если мы рассматриваем человека номер i, то нам надо найти минимальное j, что i<=j и A[i]=B[j]. И сделать нужные переходы. Так-как ограничение всего-лишь 300, то такое решение будет работать. Так-же это решение будет выдавать самый оптимальный ответ. Для больших ограничений эта задача решается сортировкой слиянием. Ну то есть сначала нужно сделать некоторые преобразования, а именно для каждой ячейки определить где она должна будет стоять, дальше выходит довольно не сложный алгоритм.
Доказать это можно очень просто, так-как разница между числами всегда будет уменьшаться на единичку.
Задача D. Физкультура
Задача Е. Тупики
Зададим динамику Ans[tree,dl] (tree,dl - битмаски) где будем хранить ответ:
1). мы составили дерево из вершин tree.
2). тупиками у нас вершины dl.
Очевидным есть ответ для двух бит, если между вершинами есть ребро то 1 , иначе 0.
Если кол-во бит больше(пускай єто будет состояние (m1,m2)) то ответ считаем так: зафиксируем некоторую вершину i которая есть тупиком и некоторую вершину j которая не есть тупиком и есть ребро между i и j. Мы будем убирать вершину i из дерева, тогда возможны два перехода , тупик i исчезает и получаем состояние (m1 xor (1 shl i),m2 xor (1 shl i)) , тупик i исчезает и j стает тупиком (m1 xor (1 shl i),m2 xor (1 shl i) xor (1 shl j)). Когда посчитали ответ для состояние(Ans[m1,m2] ),тогда разделим его на кол-во бит в m2.
Ответом будет сумма Ans[(1 shl n)-1,dl] , причем кол-во бит в dl = K.
1). мы составили дерево из вершин tree.
2). тупиками у нас вершины dl.
Очевидным есть ответ для двух бит, если между вершинами есть ребро то 1 , иначе 0.
Если кол-во бит больше(пускай єто будет состояние (m1,m2)) то ответ считаем так: зафиксируем некоторую вершину i которая есть тупиком и некоторую вершину j которая не есть тупиком и есть ребро между i и j. Мы будем убирать вершину i из дерева, тогда возможны два перехода , тупик i исчезает и получаем состояние (m1 xor (1 shl i),m2 xor (1 shl i)) , тупик i исчезает и j стает тупиком (m1 xor (1 shl i),m2 xor (1 shl i) xor (1 shl j)). Когда посчитали ответ для состояние(Ans[m1,m2] ),тогда разделим его на кол-во бит в m2.
Ответом будет сумма Ans[(1 shl n)-1,dl] , причем кол-во бит в dl = K.
Comments (0)
