Яблука#64

Яблука (Editorial)

Візерунок періодичний. Один блок має вигляд

\underbrace{G \ldots G}_{g} \underbrace{Y \ldots Y}_{y} \underbrace{R \ldots R}_{r} \underbrace{Y \ldots Y}_{y} \underbrace{G \ldots G}_{g},

тобто його довжина дорівнює p = 2g + 2y + r. Далі блок повторюється без змін, тому колір позиції залежить лише від за модулем .

Обчислимо n' = n \bmod p і подивимось, у яку з п'яти ділянок блоку потрапляє ця позиція:

  • n' \le g — зелене;

  • n' \le g + y — жовте;

  • n' \le g + y + r — червоне;

  • n' \le g + 2y + r — жовте;

  • інакше — зелене.

Окремо зверніть увагу на випадок n' = 0: він відповідає останній позиції блоку, а блок закінчується зеленим яблуком. Перша ж перевірка n' \le g спрацьовує і дає саме G, тому додаткової обробки не потрібно.

Головна технічна пастка задачі названа прямо в умові: n, g, y, r сягають 10^{12}, тому і сама сума , і всі проміжні величини мають бути 64-бітними.