Timus 1134

Материал из Олимпиадное программирование в УлГТУ
Версия от 18:21, 16 июня 2016; Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acm.timus.ru/problem.aspx?num=1134 Timus #1134 — Карты] == Комментарии == Определим…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Ссылка на задачу

Комментарии

Определим maxCount[i] — максимально возможное количество вхождений в последовательность каждого числа i от 0 до N: maxCount[0] = maxCount[N] = 1, для остальных чисел maxCount[i] = 2.

Подсчитаем count[i] — фактическое количество вхождений каждого числа i в последовательность.

Будем идти от 0 до N и проверять условие count[i] <= maxCount[i]. Если для некоторого i это условие нарушено, ответ NO. Кроме того, если count[i] == maxCount[i], то нужно увеличить count[i + 1].

Источник — https://acm.khpnets.info/w39/index.php?title=Timus_1134&oldid=2048