Матч 360, Игра с подстроками (TakeSubstringGame)

Дивизион 2, Уровень 3

На доске написано целое число n и два игрока по очереди делают ходы. Своим ходом игрок выбирает положительное число m, являющееся собственной подстрокой строки, отображенной на доске (подстрока называется собственной, если она не равна всей строке). Число n уменьшается на m и ход переходит к следующему игроку.

Например, если n = 2309, то игрок может выбрать m = 2, 3, 9, 23, 30, 230 или 309. Соответственно вычитая его из 2309, можно получить одно из чисел: 2000, 2079, 2279, 2286, 2300, 2306 или 2307.

Игрок, который не сможет сделать ход, проигрывает. Найти значение m, которое должен отнять первый игрок своим первым ходом чтобы обеспечить себе выигрыш. Если таких значений несколько, то вернуть наименьшее. Если такого значения не существует, вернуть -1.

Класс: TakeSubstringGame

Метод: int winningMove(int n)

Ограничения: 0 £ n £ 10⁶.

Вход. Целое число n.

Выход. Ход, который должен сделать первый игрок чтобы обеспечить себе выигрыш. Если такого хода не существует, вернуть -1.

Пример входа

n

5

10

239

Пример выхода

-1

1

9

РЕШЕНИЕ

игра

Задача решается построением массива win, элементы которого заполняются 0 или 1 в зависимости от того, является ли соответственно позиция проигрышной или выигрышной. Первый игрок для обеспечения себе победы должен делать ход в проигрышную позицию. Если такого хода не существует, то возвращаем -1.

Если n < 10, то сделать ход нельзя и все позиции от 0 до 9 являются проигрышными. Последовательно заполняем ячейки массива от win[10] до win[n]. Ячейка win[i] считается выигрышной, если существует такая подстрока d в числе i, для которой ячейка win[i – d] проигрышная и d > 0. Остается для каждого значения i перебрать все подстроки в нем и проверить выше описанные условия. Совершаем перебор всех подстрок с длинами l, где 1 £ l < len (количество цифр в числе i), начиная с позиции k (0 £ k £ len – l). Заметим, что условие l ¹ len обеспечивает перебор только собственных подстрок.

Если по окончанию заполнения массива окажется win[n] = 0, то позиция n проигрышная, возвращаем -1. Иначе ищем наименьшее значение d, для которого win[i – d] = 0, и запоминаем его в переменной sub.

ПРОГРАММА

#include <stdio.h>

#include <string.h>

int win[1000001];

char s[10];

class TakeSubstringGame

{

public:

int winningMove(int n)

{

int i, k, d, l, x, len, sub = 0;

for(i = 10; i <= n; i++)

{

sprintf(s,"%d",i); len = strlen(s);

sub = 2000000000;

for(l = 1; l < len; l++)

for(k = 0; k <= len - l; k++)

{

for(d = x = 0; x < l; x++)

d = d * 10 + s[k+x] - '0';

if ((d > 0) && (!win[i-d]))

{

win[i] = 1;

if (d < sub) sub = d;

}

}

}

if (!win[n]) return -1;

return sub;

}

};