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

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

HotLog


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

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

Задача A. Киберспорт

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

В киберспорте используется множество систем проведения соревнований. Не так давно для игры StarCraft II была введена новая система отбора трех человек из шести на групповой стадии.

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

Требуется написать программу, которая по результатам 30 игр определяет тройку победителей, либо определяет, что нужны дополнительные игры.

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

Входной файл INPUT.TXT содержит турнирную таблицу 6 x 6. В i-й строке сначала идут 6 цифр «0» или «1» (без пробелов) – информация об играх i-го игрока на домашних картах, далее через пробел – имя (ник) игрока. На главной диагонали таблицы стоят нули. Если в i-й строке и j-м столбце стоит «1», то это означает, что i-й игрок одержал победу над j-м на домашней карте, «0» обозначает проигрыш. Все имена – строки, состоящие не более чем из 10 английских символов.

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

В выходной файл OUTPUT.TXT выведите тройку победителей в алфавитном порядке или слово «Undefined» (без кавычек), если победителей определить невозможно.

Примеры

INPUT.TXTOUTPUT.TXT
1010011 Maru
100010 Solar
000001 Curious
111001 Zest
001001 TY
011100 Sos
Maru
TY
Zest
2000010 Snute
001010 Happy
000101 ByuL
110000 Polt
010001 Classic
001100 Lilbow
Undefined

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

Решения, учитывающие только число выигранных игр, будут оцениваться в 40 баллов.

Решения, определяющие победителей только по числу выигранных игр и по числу выигранных игр на гостевых картах, будут оцениваться в 60 баллов.


Задача B. Произведение

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

Задано некоторое n-значное натуральное число x. Найдите произведение всех чисел, получающихся перестановкой цифр числа x.

Если одно и то же число получается с помощью нескольких перестановок, то его необходимо учитывать соответствующее число раз. Кроме этого, в получающихся с помощью перестановок числах могут быть ведущие нули.

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

Входной файл INPUT.TXT содержит целое число x (1 ≤ x ≤ 109). Оно задано в десятичной системе счисления и не содержит ведущих нулей.

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

В выходной файл OUTPUT.TXT выведите остаток от деления искомого произведения на число 366239.

Примеры

INPUT.TXTOUTPUT.TXT
112252
211121
31010

Задача C. Бессмыслица

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

Никифор утверждал, что бессмыслица, повторенная много раз, становится истиной. Для доказательства этого он применил следующую процедуру: переставил на клавиатуре своего компьютера клавиши в произвольном порядке и набрал некоторый текст. Получилась, естественно, бессмыслица. Он и эту бессмыслицу набрал на том же компьютере с той же подправленной клавиатурой. Новую бессмыслицу Никифор набрал еще раз и так далее – времени-то у него много.

Требуется написать программу, которая найдет максимальное количество шагов его процедуры, чтобы получился исходный текст.

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

Входной файл INPUT.TXT содержит одно целое число N (1 < N < 60) – количество клавиш на клавиатуре компьютера Никифора.

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

В выходной файл OUTPUT.TXT выведите одно целое число – максимальное количество шагов проделанной Никифором процедуры.

Примеры

INPUT.TXTOUTPUT.TXT
144
256

Задача D. Шифрование

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

Шифр простой замены - когда каждая буква алфавита в тексте заменяется некоторой другой буквой того же алфавита (может быть, той же самой). Применив такую замену к исходному открытому тексту, мы получим зашифрованный текст. А применив обратную замену к зашифрованному тексту, мы однозначно определим исходный открытый текст.

Вам даны две строки: α – исходный открытый текст и β - зашифрованный текст. Определите, существует ли такой шифр простой замены, применив который к α мы получим β, а применив обратную замену к β мы получим α.

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

Первая строка входного файла INPUT.TXT содержит строку с исходным открытым текстом. Вторая строка содержит строку с зашифрованным текстом. Строки непустые, содержат не более 104 символов, состоят из английских букв (строчных и прописных, буквы a и A считаются различными), цифр и пробелов.

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

В выходной файл OUTPUT.TXT выведите «YES», если искомый шифр существует, в противном случае следует вывести «NO».

Примеры

INPUT.TXTOUTPUT.TXT
1How doth the little crocodile
Hehtceowtow tdlood trierecld 
YES
2Dasha
Misha
NO

Задача E. Осколки

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

На Землю надвигается страшная угроза, к нам летит облако из N огромных астероидов. Известно только то, что все они одинакового размера. У учёных есть ракеты, способные уничтожить астероиды, каждая такая ракета характеризуется зарядом m – натуральным числом от 1 до N. Но, к сожалению, неизвестно, как каждая из ракет поведёт себя при столкновении с астероидом, поэтому было принято решение запустить по одной ракете каждого вида. И только после столкновения стало известно, что ракета с зарядом m после уничтожения астероида образует осколки в количестве, равном наибольшему общему делителю чисел m и N. Помогите узнать, сколько осколков упадёт на Землю, у Вас совсем мало времени!

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

В единственной строке входного файла INPUT.TXT содержится натуральное число N – количество запущенных ракет и взорванных ими астероидов (1 ≤ N ≤ 1018).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
135
2615

Задача F. График

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

Антон работает курьером. У него много заказов. На выполнение одного заказа у Антона уходит ровно один день. Для каждого заказа определена стоимость и срок его выполнения (количество дней, оставшихся до запланированного дня выполнения заказа). Однажды проснувшись, Антон изучил свой график и понял, что возможно он не сможет выполнить все заказы, и его могут уволить. Поэтому он решил выполнить лишь некоторые из них так, чтобы при этом получить максимальный доход.

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

Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 1000) – количество заказов. Затем в N строках описаны данные каждого заказа Ti и Ci (натуральные числа, не превосходящие 105). Где Ti – последний день, в который еще можно выполнить заказ, Ci – вознаграждение за выполнение заказа.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
1 10
2 12
22
23
1 10
1 20
3 24
44

Задача G. Проценты

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

Списки ингредиентов на упаковках иногда сопровождаются их процентным содержанием, чаще всего округленным до целого числа процентов. Чтобы такой список выглядел правдоподобным, в сумме указанные числа должны давать 100%.

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

Вам заданы количества всех ингредиентов, входящих в состав продукта. Для каждого ингредиента известно, положительно или отрицательно влияет на продажи его присутствие в составе. По этим данным необходимо рассчитать процентные доли каждого из ингредиентов от их суммарного количества и округлить их в нужную сторону. При этом не следует допускать, чтобы одновременно доля какого-либо вредного компонента была округлена вверх, а доля какого-либо хорошего - вниз.

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

В первой строке входного файла INPUT.TXT задано количество ингредиентов n (1 ≤ n ≤ 30). Следующие n строк описывают сами ингредиенты: знак «+» для положительно влияющих на продажи, и «-» для отрицательно влияющих, а затем, через пробел, количество соответствующего ингредиента - целое число от 1 до 1000.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
- 10
+ 5
66
34
23
- 10
- 10
- 10
33
34
33

Задача H. Мусорщик

(Время: 1 сек. Память: 16 Мб)
Мусорщик

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

Сотрудники одной из фирм разработали специальную машину «Мусорщик-001», которая предназначена для уборки прямоугольных пустых помещений. Машина не совершенна и может пока двигаться на 1 метр только влево, вправо и вперед (вдоль оси OY). Каждое помещение можно разбить на квадратные сектора со стороной в 1 метр и обозначить те, которые загрязнены. Для уборки помещения достаточно, чтобы машина-уборщик побывала в каждом из загрязненных секторов. Известно, что перед уборкой машина всегда находится в клетке (1,1) .

Одна из компаний, где в штате нет уборщицы, но имеется полный штат программистов, приобрела «Мусорщик-001». Пока программистам никак не удается написать программу, определяющую по заданному плану загрязнения помещения минимально возможную длину маршрута машины-уборщика, необходимого для уборки данной территории. Возможно, Вам удастся им помочь!

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

Первая строка входного файла INPUT.TXT содержит натуральное число n (n ≤ 1000). Следующие n строк содержат по два натуральных числа: xi и yi – координаты загрязненных секторов в заданном помещении (xi, yi ≤ 50).

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

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

Пример

INPUT.TXTOUTPUT.TXT
17
2 1
3 2
5 2
5 4
1 4
3 6
6 6
18


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483