Задачи заочного тура региональной олимпиады по информатике 1999

Число `a_1\ a_2\ …\ a_k`, состоящее из `k` десятичных цифр, будем называть "удивительным" (от английского to divide – делить), если для любого `i` от 1 до `k` число `a_1\ a_2\ …\ a_i`, образованное из первых `i` цифр числа, делится без остатка на `i`.

Например, число 3456 является удивительным, так как 3 делится на 1, 34 делится на 2, 345 делится на 3, 3456 делится на 4. Также удивительным будет число 44440.

Найти все десятизначные удивительные числа без повторяющихся цифр (т.е. каждая цифра от 0 до 9 должна содержаться в числе один и только один раз).

Двое школьников играют в следующую игру:

Игра ведется на доске размером 6x6. Доску и положение фишки на доске видит только первый игрок. Первый игрок (капитан подводной лодки) ставит свою фишку-корабль на любую клетку доски. Второй игрок (капитан противолодочного корабля) может бросить глубинную бомбу на любую клетку доски, сказав ее координаты. Бомба поражает цель не только на выбранной клетке, но и на всех соседних с ней по горизонтали, вертикали и диагонали. Максимальная площадь поражения бомбы – квадрат 3x3. Если подводная лодка уничтожена взрывом, игра заканчивается. В противном случае первый игрок может передвинуть фишку на одну клетку по горизонтали или по вертикали (но не по диагонали!) или может остаться на прежнем месте.

Найти, сколько потребуется бомб в худшем случае для уничтожения подводной лодки при оптимальной стратегии второго игрока.

Для проверки вашего решения можете дополнительно указать последовательность бомбовых ударов, позволяющую уничтожить подводную лодку независимо от ее первоначального положения и последующих перемещений.

******
******
******
******
******
******

..+***
..+***
+++***
******
******
******

.+****
.+****
..+***
..+***
+++***
******

...+**
...+**
..++**
++****
******
******

..+***
..+***
.+****
..+***
..+***
..+***

.+****
..++**
...+**
..++**
.+****
.+****

+*****
.+****
..+***
...+**
...+**
...+**

******
+*****
.+****
..++++
......
......

******
***+++
+**+..
.+*+..
..+...
......

******
******
*+++++
+.....
......
......

***+..
***+..
***+..
*++...
+.....
......

*+....
*+....
*++...
***+..
*++...
+.....

**+...
**+...
*+....
*+....
*+....
*+....

......
......
++....
**+...
**+...
**+...

......
++....
**+...
++....
......
......

......
......
......
......
......
......