HASP's blog

By HASP, 11 years ago, In Russian

Сегодня писали муниципальный тур Всероссийской олимпиады школьников по информатике. Здесь 3 подгруппы тестов. Первая подгруппа — (N <= 10). Я не знал, как решается эта задача и написал перебор всех перестановок(N!) + разумеется, проверка. Если находил подходящую перестановку, удовлетворяющую входным данным, то ответ — Yes, иначе No. Можете объяснить мне, пожалуйста, решение этой задачи на полный балл? Буду очень благодарен!

UPD: Результаты пришли. Первая подгруппа тестов прошла(20 баллов).

UPD1: Господа минусующие, если вы минусуете, значит, для вас эта задача — пустяк. Так почему бы не написать правильное решение, вместо того, чтобы минусовать?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can take any person and first time consider him a liar and second time consider him a knight. Then by their data we could build all the chain. We should consider the arrangement that will is not contrary, if there is such an arrangement we should print "Yes". If there is no such build then we should print "No".