основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Решение задач с acm.sgu.ru

Страницы: 1
Artur
приобщившийся


Рег.: 11/19/04
Сообщений: 79
Из: Барнаул
153. Playing with matches
      #11157 - 06/07/06 05:57 PM

Пусть позиция - количество спичек.
Позиция 0 - выигрышная для ходящего, так как сходивший в эту позицию предыдущий игрок проиграл.
Заполним массив p из 2*500 + 1 элементов таким образом: если все ходы из позиции ведут в выигрышные, то позиция проигрышная, иначе - выигрышная.
Найдем "период" T получившейся последовательности - максимальное число, не большее 500, такое, что p = p[T + i]. Число Т - не вполне подходит под название период, поскольку не является минимальным.
Ответ на задачу для N спичек хранится в ячейке p[N mod T].
Code:
  
import java.io.InputStreamReader;
import java.util.Scanner;

public class Solution {

public static void main(String[] args) {
new Solution().run();
}

final static int per = 500;

private void run() {
Scanner sc = new Scanner(new InputStreamReader(System.in));
int tc = sc.nextInt();
for (int tt = 0; tt < tc; tt++) {
int n = sc.nextInt();
int[] p = new int[2*per + 1];
int m = sc.nextInt();
int[] x = new int[m + 1];
x[0] = 1;
for (int i = 1; i <= m; i++)
x[i] = sc.nextInt();
p[0] = 1; //zero is winning for first
for (int i = 1; i <= 2*per; i++) {
p[i] = 0; //losing for first
for (int j = 0; j <= m; j++)
if (i - x[j] >= 0 && p[i - x[j]] == 0)
p[i] = 1; //winning
}
int last = -1;
for (int t = per; t > 0; t--) {
boolean good = true;
for (int i = 0; i < per; i++)
if (p[i] != p[t + i])
good = false;
if (good) {
last = t;
break;
}
}
if (p[n % last] == 1)
System.out.println("FIRST PLAYER MUST WIN");
else
System.out.println("SECOND PLAYER MUST WIN");
}
sc.close();
}
}


Решение принято, но у меня несколько вопросов:
Почему достаточно 2*500 + 1 ячейки?
Почему не может быть предпериода?

--------------------
per aspera ad astra


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Stanislav
новичок


Рег.: 03/10/05
Сообщений: 5
Re: 153. Playing with matches [Re: Artur]
      #11676 - 07/19/06 09:58 PM

На самом деле достаточно 20 ячеек, и период не превышает 10. Но как это доказать - пока не знаю.

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 166 анонимных пользователей просматривают этот форум.

Модератор:  Sergeyev, Илья Кантор, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 8568

Rate this topic

Переход в