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

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


 

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

(Время: 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 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru



Окна в Алматы установка окон в Алматы.