Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
muravey
Сюжет задачи взят из книги Терри Пратчетта и пары его приятелей "Наука Плоского мира". Откуда его взял автор книги - см. книгу.
Муравья сажают в случайную клетку бесконечного поля из белых клеток, сориентировав так, что его взгляд перпендикулярен двум сторонам клетки и параллелен двум другим. Далее он движется по очень простым правилам:
— оказавшись на белой клетке, муравей поворачивает на 90 градусов вправо, перекрашивает клетку в чёрный цвет и делает шаг вперёд;
— оказавшись на чёрной клетке, муравей поворачивает на 90 градусов влево, перекрашивает клетку в белый цвет и делает шаг вперёд.
Рисовать эпичную панораму истоптанного муравьём поля вам не придётся.
Достаточно лишь посчитать, после какого хода муравей окажется на
расстоянии не меньшем, чем заданное число R, от исходной точки и
сколько в этот момент будет на поле чёрных клеток.
Будем считать, что сторона клетки и шаг муравья имеют длину 1.
Входные данные. Одно натуральное число R, не превышающее миллион.
Выходные данные. В одной строке через пробел два целых неотрицательных числа: номер хода, после которого муравей окажется на расстоянии не меньшем R от исходной точки и количество чёрных клеток на поле после этого хода.
Пример. На расстоянии, не меньшем, чем 2, от исходной точки муравей окажется после 11-го хода, и на поле в этот момент будет 7 чёрных клеток. Не верите - возьите тетрадный листок в клетку, карандаш, резинку и проверьте.
Для отправки решений необходимо выполнить вход.
|