Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Три поросенка

(Время: 1 сек. Память: 16 Мб Сложность: 71%)

Три поросенка играют в следующую игру.

Первый поросенок придумывает натуральное число N1 и сообщает его второму поросенку. После этого второй поросенок придумывает такое натуральное число N2, что существуют такие A1 ≥ 2, B1 ≥ 2, что N2 = A1 + B1 и A1 x B1 = N1, и сообщает его третьему поросенку. Тот аналогично придумывает число N3 и сообщает его первому поросенку, и т.д.

Если какой-нибудь поросенок называет число Ni, для которого следующий поросенок не может придумать числа Ai и Bi, то он выигрывает. Если же игра никогда не заканчивается, то считается, что наступила ничья.

Дано число N. Определите, кто выигрывает, если первый поросенок начинает и придумывает число N.

Поросята играют оптимально. То есть, если для поросенка существует ход, приводящий к его выигрышу, то он его делает; если такого хода не существует, но существует ход, ведущий к ничье, то поросенок делает этот ход; иначе, он делает ход, максимизирующий его число Ni.

Входные данные

Входной файл INPUT.TXT содержит натуральное число N (2 ≤ N ≤ 106).

Выходные данные

В выходной файл OUTPUT.TXT выведите порядковый номер поросенка, выигрывающего игру, или 0, если наступает ничья.

Примеры

INPUT.TXTOUTPUT.TXT
151
2163
340

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 A. Профессор Хаос
 B. Круговая площадь
 C. Гонки на лодках
 D. Шахматные баталии
 E. Магический квадрат
 F. Перемешивание
 G. Три поросенка
 H. Крестные отцы

Красноярский краевой Дворец пионеров, (c)2006 - 2021, E-mail: admin@acmp.ru