Задача из ИОИП.

Revision ru1, by Diplomate, 2016-10-15 20:46:18

Не могу понять разбор задачи E из ИОИП прошлого года. Условия задач — http://neerc.ifmo.ru/school/ioip/problems-2016.pdf Разбор — http://neerc.ifmo.ru/school/io/archive/20160327/analysis-20160327-individual.pdf Мне понятно всё до последнего слайда. Вопрос номер один: в разборе утверждается, что при решении задачи для отрезка [0; 2d + 1] задачу можно будет легко решить и для остальных позиций путем проставления 0 и 1 в соответствии с их классом эквивалентности. Но почему не может возникнуть ситуации, когда такое проставление не даст корректного ответа для других отрезков(то есть сумма там не будет равняться требуемой)?

Первый вопрос снимается, если ответить на второй: в последнем пункте говорится, что cj равны между собой, то есть в отрезке [0; 2d + 1] у нас одинаковое количество непроставленных элементов для каждого класса эквивалентности. Действительно, тогда в других отрезках эти числа тоже будут одинаковыми и мы получим ответ на первый вопрос. Но каким образом можно доказать или хотя бы обнаружить это свойство? По-моему это утверждение совсем не очевидно.

Если у кого-нибудь есть другие идеи по поводу этой задачи, буду очень благодарен, если вы их озвучите).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Diplomate 2016-10-15 20:56:20 67
ru1 Russian Diplomate 2016-10-15 20:46:18 1203 Первая редакция (опубликовано)