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

Автор abistrigova, история, 11 лет назад, По-русски

Закончился второй раунд. Интересно, как решать C, F?

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Интересно я один пытался запихивать хеши на B ?

Расскажите пожалуйста нормальное решение)

»
11 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +11 Проголосовать: не нравится

F: Для начала посчитаем, какое количество монет может быть перевернуто после выполнения всех действий. Заметим, что если после выполнения некоторых действий может быть перевернуто минимально min и максимально max монет, то может быть перевернуто и произвольное количество монет cnt, такое что min ≤ cnt ≤ max и cnt совпадает по четности с min и max (они всегда совпадают по четности между собой). Поэтому будем просто выполнять последовательно действия и считать эти min и max после каждого действия, зная каковы они были перед выполнением действия. Внутри перехода min и max я считал разбором нескольких случаев, примерно так:


// здесь они названы from и to и показан код, считающий следующее значение для from // x - количество монет, которое надо перевернуть в данный момент if (from >= x) from2 = from - x; else if (x >= to) from2 = x - to; else if ((from & 1) == (x & 1)) from2 = 0; else from2 = 1;

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

Полный код (метод solve в самом конце)

  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +16 Проголосовать: не нравится

    А код для to во избежание багов можно не писать, а вызвать код для from с (from, to) --> (m — to, m — from), и взяв m — результат.

    • »
      »
      »
      11 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Да, вчера вечером я тоже это придумал, но на контесте ограничился "скопировать, просмотреть ошибку, получить WA вслепую" за минуту до конца раунда.