Блог пользователя Sereja

Автор Sereja, 14 лет назад, По-русски

Задача А. Автодополнение

В задаче не было особой сложности в реализации и алгоритме решения, так-как ограничения позволяли  написать решение со квадратичной сложностью. Просто делаем все как и требовалось в условии.

Задача 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. Посчитав их проверяем на оптимальность. Аналогично делаем и для второй стороны. Единственно что нужно помнить в случае равности ответа приоритет отдается тому, когда высота больше.

Задача С. Лягушонок

Ответом будет последовательность: 1 ,N  ,2 ,N-1, 3 ,N-2 ...
Доказать это можно очень просто, так-как разница между числами всегда будет уменьшаться на единичку.

Задача D. Физкультура

Алгоритм задачи такой: идем слева на право и берем для каждого человека из первого множества самого ближнего из второго , который стоит не левее его самого , ну то есть если мы рассматриваем человека номер i, то нам надо найти минимальное j, что i<=j и A[i]=B[j]. И сделать нужные переходы. Так-как ограничение всего-лишь 300, то такое решение будет работать. Так-же это решение будет выдавать самый оптимальный ответ. Для больших ограничений эта задача решается сортировкой слиянием. Ну то есть сначала нужно сделать некоторые преобразования, а именно для каждой ячейки определить где она должна будет стоять, дальше выходит довольно не сложный алгоритм.

Задача Е. Тупики

Зададим динамику 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.
Разбор задач Codeforces Beta Round 49 (Div. 2)
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может подскажете в чем дело?Задача А вроде бы простейшая, но упорно дает 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.


  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Цитата из условия:

    "Вы должны найти лексикографически наименьший адрес"

  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    После того как вердикт получил, можно увидеть тест на котором упал.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Проблема в том что если тест занимает много строк то он отображается  не полностью.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        >>"Вы должны найти лексикографически наименьший адрес"

        Если букв меньше то адрес меньше, разве нет?

        Падает на тесте при n=90,количество букв в моем и правильном ответах разное.Собственно,там ещё пачка таких тестов перед этим(есть,например,n=83),но решение проходит их на ура.

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вовсе нет. В словаре же вы сначала встречаете не все слова длины 4, затем 5 и т.д.:)
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Хм.Если дело в этом, то странно, что я впервые споткнулся на этом на 16ом тесте.Спасибо вам.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обогнали :(