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

Рассмотрим последовательность натуральных чисел, из которой вычеркнуты все числа, кратные квадратам чисел больших 1. Первыми элементами этой последовательности являются 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, … Найдите 1000-ое, 1000000-ое и 1000000000-ое по порядку число в этой последовательности.

В качестве решения необходимо отправить файл, содержащий 3 строки, в каждой строке должно быть одно число. Ответы должны идти в порядке, указанном в задаче. Если какой-либо из ответов неизвестен, укажите вместо него число 0.

Оценка задачи: 5 баллов за каждый правильный ответ.

Нободи загадал целое число от 1 до `N`. Вы должны угадать это число, называя любые целые числа. На все попытки (кроме, естественно, первой) Нободи отвечает "теплее" или "холоднее" в зависимости от того, расположено ли названное последним число ближе (теплее) или дальше (холоднее) к загаданному числу, чем предыдущее. Если расстояние не изменилось, то Нободи может сказать "теплее" или "холоднее" по собственному выбору. Процесс угадывания заканчивается, когда вы скажете, что число, названное вами последним, является загаданным числом.

Определите число попыток, требуемых для угадывания любого числа из диапазона от 1 до 10 и из диапазона от 1 до 100. Некоторые числа в диапазоне могут быть угаданы быстрее, необходимо определить минимальное число попыток в худшем случае.

Например, пусть Нободи задумал число от 1 до 2. Нужно назвать число 1, затем 2. Если будет ответ "теплее", говорим "угадал". При ответе "холоднее" нужно назвать 1, получаем ответ "теплее" и говорим "угадал". Число попыток в худшем случае при оптимальной стратегии в данном случае равно 3.

В качестве решения необходимо отправить файл, содержащий 2 строки, в каждой строке должно быть одно число. В первой строке – ответ для `N=10`, во второй строке – для `N=100`. Если какой-либо из ответов неизвестен, укажите вместо него число 0.

Оценка задачи: 10 баллов за каждый правильный ответ.

Шахматист А в среднем на каждые 100 партий выигрывает у шахматиста В на 6 партий больше, чем проигрывает, а доля ничьих равна 80%. Выигрыш приносит победителю одно очно, а ничья по пол-очка обоим игрокам. С использованием генератора случайных чисел промоделируйте матч из 24 партий. С каким результатом он закончится?

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

Оценка задачи: 10 баллов за решение задачи.