Подразделы

Другие разделы

Дата и время

11/12/2024 14:38:12

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

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

print1. Удивительные числа

Число `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 должна содержаться в числе один и только один раз).

Ответ Ответ: 3816547290

См. также задачу 653

print2. Морской бой

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

Ответ Ответ: требуется 15 ходов

Возможная последовательность ходов:

Ходы указаны формате: столбец, строка
* – возможное положение подводной лодки
+ – возможное новое положение подводной лодки
после ее хода
. – пустое место

Начальная позиция:
******
******
******
******
******
******

ход 1: 2,2
..+***
..+***
+++***
******
******
******

ход 2: 2,4
.+****
.+****
..+***
..+***
+++***
******

ход 3: 3,2
...+**
...+**
..++**
++****
******
******

ход 4: 2,5
..+***
..+***
.+****
..+***
..+***
..+***

ход 5: 3,3
.+****
..++**
...+**
..++**
.+****
.+****

ход 6: 3,5
+*****
.+****
..+***
...+**
...+**
...+**

ход 7: 5,5
******
+*****
.+****
..++++
......
......

ход 8: 5,3
******
***+++
+**+..
.+*+..
..+...
......

ход 9: 3,4
******
******
*+++++
+.....
......
......

ход 10: 5,2
***+..
***+..
***+..
*++...
+.....
......

ход 11: 3,2
*+....
*+....
*++...
***+..
*++...
+.....

ход 12: 3,4
**+...
**+...
*+....
*+....
*+....
*+....

ход 13: 2,2
......
......
++....
**+...
**+...
**+...

ход 14: 2,5
......
++....
**+...
++....
......
......

ход 15: 2,3
......
......
......
......
......
......

Подлодка уничтожена!
loading