What the ZNO leads to...#6

What the ZNO leads to... (Editorial)

Ключове речення умови — про «хербатку»: ефективність відновлюється до максимуму щоразу, коли набір розв'язано повністю. Отже, кожен набір учасник починає з повною ефективністю .

З'ясуємо, скільки задач можна зробити за один такий «захід». Першу годину ефективність дорівнює , другу — e-1, і так далі до одиниці, після чого вона стає нулем і робота зупиняється. Тому максимум задач в одному заході дорівнює

E = e + (e-1) + \ldots + 1 = \frac{e(e+1)}{2}.

Тепер алгоритм для кожного учасника очевидний. Ідемо по його наборах по порядку:

  • якщо a_i \le E, набір повністю розв'язано — додаємо a_i до відповіді, ефективність відновлюється, переходимо до наступного набору;

  • якщо a_i > E, набір не подужати навіть за повний захід: учасник розв'язує з нього рівно задач, ефективність падає до нуля і відновити її вже нічим. Додаємо і зупиняємось.

Порахувавши так X_a для Дані та X_b для Діани, порівнюємо їх і виводимо переможця (або Draw), а в другому рядку — рахунок, починаючи з результату переможця.

Стежте за типами: сягає 10^9, тому E \approx 5 \cdot 10^{17} — це вже майже межа 64-бітного типу, а сума задач може досягати 2 \cdot 10^{14}. Рахуйте все у 64-бітних цілих.