Областная олимпиада 2008-2009
Завдання ІІІ етапу Всеукраїнської учнівської олімпіади
з основ інформатики та обчислювальної техніки у 2008-2009 н.р.
І тур
1. АТС
Шерлок Холмс построил агентурную сеть мальчишек и снабдил их мобильными телефонами. Каждый агент отправляет СМС, которое регистрируется собственной АТС Холмса и при этом записывается номер отправителя. Некоторые агенты могут отправить несколько СМС. Холмс платит только тем агентам, которые отправили хотя бы одно СМС. Номер телефона представляет собой целое положительное число, которое не превышает 1000000. Имеется список из N номеров. Необходимо написать программу, которая получает этот же список без повторений номеров (учитывается только первое появление номера), не изменяя взаимный порядок следования чисел.
Входные данные: В первой строке входного файла содержится число N (1<=N<=100000). В каждой последующей из N строк содержится одно целое число – зарегистрированный номер телефона.
Выходные данные: Вывести в выходной файл список номеров без повторов. Каждый номер должен размещаться в отдельной строке. Например:
INPUT.TXT
5
123
34
456
123
34
OUTPUT.TXT
123
34
456
2. Помощь мэру
К Шерлоку Холмсу обратился мэр Лондона с просьбой разобраться в запутанных денежных отношениях городских бизнесменов. В их бизнесе часто возникают ситуации, когда бизнесмен А имеет долг перед бизнесменом В, а бизнесмен В имеет в свою очередь долг перед бизнесменом А. В конце года мер решил погасить все взаимные долги а также устранить ситуации, когда бизнесмен А должен бизнесмену В, а бизнесмен В должно бизнесмену C. Шерлоку Холмсу необходимо по имеющимся данным определить «реальные» долги бизнесменов.
Входные данные: В первой строке входного файла содержится целое положительное число N (1<=N<=100). Далее следует N строк по N вещественных чисел в каждой – строки таблицы А, в которой каждый элемент А[i,j] показывает какую сумму денежных средств бизнесмен i должен бизнесмену j. Все числа в строке таблицы разделены пробелами.
Выходные данные: Выходной файл должен содержать N строк, в каждой по одному числу — реальный баланс соответствующего бизнесмена (положительное число — если должны ему и отрицательное число, если должен он). Числа требуется вывести с точностью до двух знаков.
Например:
INPUT.TXT
3
0 13.5 0
2.5 0 20
10 10 0
OUTPUT.TXT
-1.00
1.00
0.00
3. Шифровка
Для шифрования СМС агенты Холмса используют 5 букв (в алфавитном порядке): #, $, &, *, @. Все используемые в СМС слова – пятибуквенные. Холмс создал словарь, в нем первое слово #####, а последнее - @@@@@. Холмсу для печати словаря надо определить количество страниц Р в словаре (на каждой странице словаря напечатано N слов) и номер страницы Q, на которой располагается задаваемое слово А.
Входные данные: Входной файл содержит: в первой строке – число N, во второй – слово А
Выходные данные: Выходной файл должен содержать две строки: в первой строке – число Р, во второй – номер страницы Q, содержащей слово А. Например:
INPUT.TXT
35
####$
OUTPUT.TXT
90
1
Завдання ІІІ етапу Всеукраїнської учнівської олімпіади
з основ інформатики та обчислювальної техніки у 2008-2009 н.р.
ІІ тур
4. Сейф
Доктор Ватсон купил новый сейф фирмы PhigWamm с суперзамком следующей конструкции: вокруг открывающей ручки расположены пронумерованные подряд от 1 до N кнопки. Для того, чтобы открыть сейф необходимо в определенном порядке нажать все кнопки. Доктор Ватсон забыл код, но помнит, что кнопки необходимо нажимать с шагом h (в сторону возрастания номеров, при этом уже ранее нажатые кнопки пропускаются) и последней должна быть нажата кнопка с номером k. Напиши программу, которая поможет Доктору Ватсону узнать, с какой кнопки начинается код сейфа.
Входные данные: В единственной строке входного файла находится три целых числа N, k, h (0<=N,k,h<=30000
).
Выходные данные: В выходной файл необходимо вывести единственное число - номер кнопки, с которой начинается код сейфа.
Например:
INPUT.TXT
3 1 2
OUTPUT.TXT
3
5. Дороги Англии
Шерлоку Холмсу часто приходится преследовать преступников. В Англии есть N городов и система дорог, соединяющая их. Любые два города может соединять не более одной дороги. По любой из дорог, соединяющей два города можно проехать в обоих направлениях. Холмсу необходимо знать, существуют ли города, из которых можно выехать по одной дороге, а вернуться в них по другой. Напишите программу, которая поможет Шерлоку Холмсу.
Входные данные: В первой строке входного файла содержится целое положительное число N (1<N<=50). Далее каждая строка файла содержит по два целых положительных числа i и j, означающих, что есть дорога, соединяющая i-ый и j-ый города.
Выходные данные: В выходном файле указываются целые числа – номера городов, из которых можно выехать по одной дороге, а вернуться в них по другой. Если таких городов нет, то вывести 0.
Например:
INPUT.TXT
5
1 2
2 3
3 4
1 3
5 4
OUTPUT.TXT
1 2 3
6. Тренировка ума
Шерлок Холмс часто решает разные математические задачи для тренировки ума. И сейчас ему попалась одна задача. Дано N целых чисел A1, A2, ..., AN. Требуется найти количество различных значений сумм вида k1A1 + k2A2 + ... + kNAN (0 <= Ai <= 100, 0 <= ki <= 1, все числа целые). Напишите программу, которая поможет Шерлоку Холмсу решить задачу.
Входные данные: В первой строке входного файла содержится целое положительное число N (1<=N<=500), во второй - A1, A2, ..., AN через пробел
Выходные данные: В выходной файл вывести одно число - количество различных значений сумм.
Например:
INPUT.TXT
3
1 1 2
OUTPUT.TXT
5