Задача А. Автодополнение
Задача 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.
Может подскажете в чем дело?Задача А вроде бы простейшая, но упорно дает WA на 16ом тесте, хотя тест ничем особенным не выделяется.
Код(Паскаль):
var
s,s1,answ:string[101];
i,n,min:integer;
begin
readln(s);
readln(n);
min:=maxint;
for i:=1 to n do
begin
readln(s1);
if (copy(s,1,length(s))=copy(s1,1,length(s)))and(length(s1)<=min) then
begin
answ:=s1;
min:=length(s1);
end;
end;
if min=maxint then writeln(s) else writeln(answ);
end.
Цитата из условия:
"Вы должны найти лексикографически наименьший адрес"
Если букв меньше то адрес меньше, разве нет?
Падает на тесте при n=90,количество букв в моем и правильном ответах разное.Собственно,там ещё пачка таких тестов перед этим(есть,например,n=83),но решение проходит их на ура.
Хм.Если дело в этом, то странно, что я впервые споткнулся на этом на 16ом тесте.Спасибо вам.