1 Тема от wtq4er

  • wtq4er
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-05-04
  • Сообщений: 8

Тема: камушки...

Есть такая игра: дано N кучек камушков По Si камушков в каждой. Играют двое. Первый берет 1 камушек из любой кучки, 2ой 2 камушка, 1й 3камушка, 2й 4 камушка и т.д.. Выигрывает тот, кто возмет нужное кол-во камушков последним.
Зная N и все Si определить, кто победит - четный или нечетный игрок, исходя из условия, что оба играют оптимально.
Я, как тру быдлокодер, смог написать только алгоритм простого перебора. Естесственно, он не проходит по времени. Реквестирую помощи людей, знающих толк в натуральных числах - как всё это ускорить???
Сама задача вот здесь http://www.codechef.com/problems/RESN04

2 Ответ от cmd

  • cmd
  • Участник
  • Неактивен
  • Откуда: Волжский
  • Зарегистрирован: 2009-06-11
  • Сообщений: 35

Re: камушки...

В условие вроде немного по другому написано:
На i-м ходу надо не i камушков брать, а выбирать любую кучку с номером i, где Si >= i и взять оттуда i камушкев.
Т.е. получается: из i-й кучки можно взять ровно i камушков.
Тогда для каждой кучке можно посчитать сколько раз используя ее можно сделать ходов - cnt_i = [S_i / i] (целочисленное деление с округлением вниз).
Тогда очевидно, что если sum(cnt_i) четное, то выигрывает второй игрок, иначе первый.

3 Ответ от wtq4er

  • wtq4er
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-05-04
  • Сообщений: 8

Re: камушки...

cmd пишет:

В условие вроде немного по другому написано:

Да, где то у меня в мозгу коротнуло, похоже=) условие действительно совсем другое. И решается всё просто. Однако мой вариант гораздо интереснее! big_smile