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

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

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Шестая личная олимпиада"

Задача A. Последовательность

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Задана последовательность целых чисел:

1, 6, 28, 145, 876, …

Требуется определить элемент последовательности по его номеру.

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

Входной файл INPUT.TXT содержит натуральное число N – номер элемента последовательности (N ≤ 20).

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

В выходной файл OUTPUT.TXT выведите N-й элемент последовательности.

Примеры

INPUT.TXTOUTPUT.TXT
126
25876

Система оценки

Решения, работающие верно только для N ≤ 5, будут оцениваться в 25 баллов.


Задача B. Крестные отцы

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Два главы крупных кланов дон Ромарио Магдини и дон Вито Демидетти встретились в центре затихшего города, чтобы выяснить раз и навсегда, кому он принадлежит. «Этот город тесен для нас двоих» – сказал Вито. «Давайте решим вопрос относительно мирным путём, дорогой дон. Предлагаю сыграть в игру. Кто проиграет, тот уходит из города» – сказал Ромарио. После небольшой паузы, Вито сказал: «Я знаю как Вы, дорогой дон, хорошо играете, и даже знаю Вашу любимую игру. Предлагаю немного изменить её правила». «Хорошо, но тогда я хожу первым» – сказал Ромарио.

Доны играют в следующую игру. Дано целое число, записанное в десятичной системе счисления в виде строки, возможно, с ведущими нулями. Участники делают ходы по очереди. Ход заключается в удалении из записи числа одной цифры так, что после этого действия получается либо чётное число, либо пустая строка. Если перед началом хода строка пуста или ход сделать нельзя, то игрок, который должен сделать ход, проигрывает.

Определите, кто выиграет при оптимальной игре обоих сторон, если дон Ромарио ходит первым.

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

Входной файл INPUT.TXT содержит целое десятичное число, состоящее не более чем из 104 цифр, возможно, с ведущими нулями.

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

В выходной файл OUTPUT.TXT выведите «Romario», если выиграет дон Ромарио, или «Vito», если выиграет дон Вито.

Примеры

INPUT.TXTOUTPUT.TXT
11Romario
210Vito
311Vito

Задача C. Ковер

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Драгоценности короля Людовика XIII хранятся в специальных ларцах. Все ларцы имеют одинаковые размеры 40 дюймов длины и 8 дюймов ширины.

Король приказал изготовить ковер и составить на него все драгоценности. При этом придворные должны соблюдать следующие условия:

  • ларцы можно ставить один на другой, но не более 5 штук в стопке;
  • стопки ларцов можно ставить только правильными ровными рядами;
  • все ларцы ставятся на прямоугольный ковер таким образом, чтобы не оставалось пустого места, где можно было бы разместить еще одну стопку;
  • от длинной стороны ларца до другого ларца или края ковра должно быть свободное пространство в 2 дюйма;
  • от короткой стороны ларца до другого ларца или до края ковра должно быть свободное пространство в 4 дюйма.

Людовик XIII хочет, чтобы ковер был оптимальных размеров:

  1. Площадь ковра должна быть минимальной;
  2. Если есть несколько ковров оптимальной площади, выбрать среди них тот, который больше похож на квадрат (т.е. имеет минимальную разницу длины и ширины).

Ваша задача - вычислить размеры такого ковра.

На рисунке показан пример оптимального размещения на ковре 29 ларцов. Размеры такого ковра: 92 дюйма длины и 32 ширины.

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 1012) – количество ларцов.

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

В выходной файл OUTPUT.TXT выведите ответ в формате W X H = S, где W - длина ковра, H – ширина ковра, S – площадь ковра.

Примеры

INPUT.TXTOUTPUT.TXT
1148 X 12 = 576
22992 X 32 = 2944
343136 X 32 = 4352

Задача D. Алиса, Боб и треугольник Паскаля

(Время: 2 сек. Память: 16 Мб Баллы: 100)

Совсем недавно Алиса начала проявлять нездоровый интерес к биномиальным коэффициентам, и каково было ее счастье, когда на день рождения ей подарили треугольник Паскаля! Теперь Алиса каждый день играет с ним и непременно узнает что-то новое о биномиальных коэффициентах, записанных в нем.

Но как это обычно и бывает со всеми игрушками, треугольник Паскаля ей очень скоро наскучил, и, решив, что ее уже ничем не удивить, Алиса выбросила его. Заметив это, Боб, старший брат Алисы, решил, что еще не все потеряно. Недолго думая, он сказал Алисе, что нашел огромное количество новых пар взаимно простых биномиальных коэффициентов, о которых она раньше и не догадывалась, и предложил ей сыграть в одну игру.

Он называет Алисе два целых неотрицательных числа n и k. В ответ Алиса должна назвать свою пару целых неотрицательных чисел m и t, такую что биномиальные коэффициенты C(n, k) и C(m, t) взаимно просты. Затем он спрашивает ее, какие еще взаимно простые с названным Бобом биномиальные коэффициенты она знает.

Боб выписал все названные Алисой биномиальные коэффициенты и собирается удивить ее, назвав еще один такой коэффициент C(p, l), что его нет среди выписанных Бобом коэффициентов и он был бы взаимно прост с названым им ранее.

Дополнительно, Боб решил найти наибольший общий делитель d биномиальных коэффициентов C(n, k) и C(m, t), чтобы проверить, не забыла ли Алиса то, чему научилась, играя с треугольником Паскаля сутками напролет. Помогите Бобу написать соответствующую программу.

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

В первой строке входного файла INPUT.TXT записано четыре целых неотрицательных числа через пробел, не превышающих 500 000: k, n, t, m, причем k ≤ n, t ≤ m.

В следующей строке входного файла записано одно неотрицательное целое число q, не превышающее 500 000 – количество дополнительных биномиальных коэффициентов, которые назвала Алиса.

В последующих q строчках записаны пары из двух неотрицательных целых чисел ti и mi, разделенных пробелом, причем 0 ≤ ti ≤ mi ≤ 500 000.

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

В первую строку выходного файла OUTPUT.TXT необходимо вывести «Yes», если Алиса назвала взаимно простой с C(n, k) биномиальный коэффициент, и «No» иначе (слова должны быть выведены без кавычек). Если выведено «No», то в следующей строке должно быть записано целое число d – наибольший общий делитель биномиальных коэффициентов C(n, k) и C(m, t), взятый по простому модулю 109+9. И, наконец, в последней строчке должны быть записаны два целых неотрицательных числа l и p – параметры биномиального коэффициента C(p, l) соответственно, разделенные пробелом (0 ≤ l ≤ p ≤ 500 000). Если подходящих пар несколько, то выведите любую из них. Гарантируется, что для любых входных данных, удовлетворяющих условию, существует как минимум одна подходящая пара p и l.

Примеры

INPUT.TXTOUTPUT.TXT
12 7 3 5
2
1 5
2 5
Yes
10 11
24 9 2 8
3
2 6
2 47
1 71
No
14
1 73

Пояснения к примерам

В первом тестовом примере Боб назвал биномиальный коэффициент C(7,2) = 21, а Алиса назвала C(5,3) = 10, C(5,1) = 5, C(5, 2) = 10. Видно, что НОД(21, 10) = 1, поэтому названные числа взаимно просты. Указанный биномиальный коэффициент в выходном файле C(11,10) = 11 взаимно прост с названным Бобом и не совпадает ни с одним из названных Алисой.

Во втором тестовом примере Боб назвал C(9,4) = 126, а Алиса назвала C(8, 2) = 28. НОД(126, 28) = 14, что означает, что Алиса ошиблась и нужно вывести No и 14 в первых двух строчках выходного файла. Также Алисой были названы биномиальные коэффициенты C(6, 2) = 15, C(47, 2) = 1081, C(71, 1) = 71. Можно вывести, например, C(73,1) = 73 – взаимно простое с C(9, 4) и не совпадающее со всеми биномиальными коэффициентами, названными Алисой.



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