Задачи олимпиады "Личное первенство по программированию среди школьников и студентов ИКИТ СФУ"
Задача A. Орфография
(Время: 1 сек. Память: 16 Мб)
У студента-филолога Васи есть замечательный друг Петя. И Петя никак не может выучить английский язык. Английский текст Петя еще кое-как читает, но пишет с ужасными ошибками, причем чаще всего он вставляет в слова лишние буквы.
Вася решил помочь Пете. Теперь каждый день Вася диктует Пете слова, а Петя их записывает. После семестра занятий Петя стал писать много лучше и теперь делает в словах только по одной ошибке. Чтобы автоматизировать процесс исправления ошибок, Вася просит Вас написать программу, которая удаляет из слова одну лишнюю букву и показывает Пете правильное слово.
Входные данные
Входной файл INPUT.TXT содержит целое число K - номер лишней буквы, а затем через один или несколько пробелов записано слово S, состоящее из английских букв верхнего регистра. Гарантируется, что номер буквы от единицы до длины слова включительно. Длина слова не более 80 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите исправленное слово.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
4 MISTSPELL
MISSPELL
2
2 ABC
AC
Задача B. Unix
(Время: 1 сек. Память: 16 Мб)
Наш любимый сисадмин Алексей установил новую ОС семейства Unix. Основные её особенности - это стабильность, надежность, гибкость и масштабируемость и огромное количество идущего в стандартной поставке программного обеспечения. Одна из таких встроенных программ предназначена для сложения чисел, представленных в троичной системе счисления. Вы понимаете то, что Костя - известный тестер, и делом чести для него является найти ошибку в реализации столь сложной задачи. Помогите ему - напишите свою, абсолютно безошибочную версию «троичного калькулятора».
Входные данные
Входной файл INPUT.TXT содержит два, разделенных пробелом, числа N и M (0 ≤ N, M ≤ 231-1) в троичной системе счисления.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ – сумму N и M в десятичной системе счисления.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 1
2
2
20 102
17
Задача C. Олимпиада
(Время: 1 сек. Память: 16 Мб)
Трое студентов, пятикурсник, третьекурсник и первокурсник, живут в одной комнате общежития и любят участвовать в соревнованиях по программированию по правилам ACM. У каждого из них свой подход к решению задач. Пятикурсник решает все задачи строго по порядку - сначала первую, затем вторую, и так до последней. Третьекурсник решает задачи строго в обратном порядке – сначала последнюю, затем предпоследнюю, и так до первой. А первокурсник сначала решает самую простую задачу, затем – самую простую из оставшихся задач, и так до самой сложной. Сложность задачи определяется временем, необходимым для её решения. Для решения одной и той же задачи наши студенты тратят одинаковое количество времени.
Ваша задача – по описанию соревнований по программированию определить, кто из студентов победит. Напомним, что по правилам ACM побеждает участник, за 300 минут решивший больше всего задач, а при равенстве количества задач – набравший меньше штрафного времени.
Наши студенты – очень сильные программисты, и при решении задач они не делают неправильных попыток. Поэтому за задачу начисляется штраф в размере количества минут от начала соревнования до её посылки на проверку. Если же и количество штрафного времени совпадает – то студент со старшего курса уступает победу студенту с младшего курса.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N (N ≤ 10) – количество задач. Во второй строке записаны через пробел N натуральных чисел – количество минут, необходимое для решения каждой задачи. Время решения задачи не превосходит 300 минут.
Выходные данные
В выходной файл OUTPUT.TXT выведите номер курса студента, одержавшего победу в олимпиаде.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 40 30 60
1
2
4 10 20 30 40
1
Пояснение к примерам
В первом тесте пятикурсник набрал 240 штрафных минут (40 + 70 + 130), третьекурсник – 280 (60 + 90 + 130), первокурсник - 230 минут (30 + 70 + 130).
Во втором тесте третьекурсник набрал 300 минут, а первокурсник и пятикурсник – 200 минут. Но пятикурсник уступил первокурснику.
Задача D. Змейка - 3
(Время: 1 сек. Память: 16 Мб)
Напишите программу, которая выводит элемент из строки Y и столбца X матрицы размера N×M, которая заполнена следующим образом:
0
1
2
3
7
6
5
4
8
9
10
11
Входные данные
Входной файл INPUT.TXT содержит натуральные числа N, M, Y, X (Y ≤ N ≤ 50; X ≤ M ≤ 50). N - количество строк матрицы, M - количество столбцов матрицы, Y и X - номера строки и столбца искомого элемента.
Выходные данные
В выходной файл OUTPUT.TXT выведите искомый элемент.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 4 2 3
5
2
5 2 3 1
4
3
3 4 3 2
9
Задача E. Размен
(Время: 1 сек. Память: 16 Мб)
У вас имеется неограниченное количество монеток N разных достоинств. Определить, можно ли с их помощью разменять заданные К сумм денег.
Входные данные
В первой строке входного файла INPUT.TXT задано число N, далее во второй строке записаны N чисел, задающих достоинства монеток. В третьей строке задано число К – количество сумм. В четвертой строке располагаются К чисел, определяющих размеры сумм. Все числа во входном файле натуральны и не превосходят 1000.
Выходные данные
В выходной файл OUTPUT.TXT выведите К чисел через пробел: для каждой суммы следует вывести 0, если ее разменять нельзя, и 1, если можно.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 3 5 5 3 6 7 11 12
1 1 0 1 1
2
1 10 1 3
0
Задача F. Карточки
(Время: 1 сек. Память: 16 Мб)
На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересовался вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?".
Помогите ему ответить на этот вопрос.
Входные данные
Во входном файле INPUT.TXT задано слово, составленное Петей - строка из маленьких английских букв не длиннее 15 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число - ответ на поставленную задачу.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
solo
12
Задача G. Баллы
(Время: 2 сек. Память: 64 Мб)
Мир наш развивается, строятся города, люди улетают в космос, изменяется система аттестации студентов в СФУ. Но вот проблема - систему аттестации студентов изменили, а программное обеспечение, которое поставлено в деканатах для контроля успеваемости, оставили прежним. Поэтому Вам срочно требуется внедрить во всех деканатах новую программу поиска студентов с заданным баллом!
Входные данные
В первой строке входного файла INPUT.TXT содержатся натуральные числа N и K (N, K ≤ 200 000) – соответственно количество студентов, подлежащих аттестации, и число запросов декана об успеваемости студентов. Во второй строке находятся N целых чисел ai, упорядоченных по возрастанию. Эти числа - аттестационные баллы студентов. В третьей строке располагаются K целых чисел bi, определяющие искомый балл. (0 ≤ ai, bi ≤ 232)
Выходные данные
В выходной файл OUTPUT.TXT выведите для каждого из K запросов через пробел слово «YES», если студент с таким баллом есть, и «NO» в противном случае.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 4 1 6 9 7 9 10 1
NO YES NO YES
2
2 2 1 2 1 3
YES NO
Задача H. Полка
(Время: 1 сек. Память: 16 Мб)
У Андрея есть младший брат Ванечка, который очень любит смотреть мультики. Ванечка вечно разбрасывал по дому и терял свои DVD с мультиками. Поэтому на день рождения Андрей подарил брату длинную полку для того, чтобы Ванечка ставил на нее свои диски. Чтобы на полке был порядок, Андрей просил Ванечку соблюдать простой порядок:
если на полке нет ни одного диска, то Ванечка просто ставит его;
если диск есть, то Ванечка ставит диск либо справа, либо слева от уже расставленных;
забирает диски он так же, то есть снимает только с правого или левого края.
И теперь Андрей хочет узнать, выполнил Ванечка его инструкции или нет.
Входные данные
В первой строке входного файла INPUT.TXT указано целое число N (1 ≤ N ≤ 10000) - количество операций, которые выполнил Ванечка. Далее в N строках находится информация об операциях. Каждая операция постановки диска на полку описывается парой чисел. Первое из них (1 или 2) показывает, что диск ставится с левого края или с правого края соответственно. Второе целое число (от 0 до 10000) обозначает номер диска. Операции снятия диска с полки описывается одним числом 3 или 4, обозначающим с левого и правого края полки соответственно снимается диск.
В начальный момент полка пуста. Гарантируется, что последовательность операций корректна, нет команд снятия диска с пустой полки.
Выходные данные
В выходной файл OUTPUT.TXT для каждой операции снятия диска с полки выведите его номер.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5 1 1 2 2 1 3 3 4
3 2
2
2 1 1 3
1
Задача I. Карточки - 3
(Время: 1 сек. Память: 16 Мб)
Студент-первокурсник Антон никак не может понять странную формулу
1/2 + 1/3 + 1/4 + ... + 1/n + ... → бесконечность
Хорошо, что у Антона есть друг Васька, который отлично знает математику. Вот и придумал Васька, как Антошке объяснить эту самую бесконечность. Взял колоду карт и стал раскладывать карты на столе. Если есть одна карта, она нависает над столом на 1/2 длины карты. Если есть две карты, то верхняя нависает над нижней на 1/2 длины карты, а нижняя - нависает над столом на 1/3 длины. В итоге получается нависание 1/2+1/3=5/6. А если у нас есть N карт, то длина нависающей части уже 1/2+1/3+1/4+...+1/(N+1).
И стал Васька с Антоном в такую игру играть: Антон называет какое-нибудь число, а Вася называет минимальное количество карт, которое нужно положить, чтобы длина нависающей части была бы не меньше этого числа.
Напишите программу, которая помогает Васе каждый раз давать правильный ответ.
Входные данные
Входной файл INPUT.TXT содержит единственное положительное число X - длина нависающей части. Число X задано с двумя знаками после запятой и 0.01 ≤ x < 10.00.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу по формату, приведенному в примерах.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1.00
3 card(s)
2
3.71
61 card(s)
3
0.04
1 card(s)
4
5.19
273 card(s)
Замечание
В условии задачи приведена некорректная физическая модель. Однако, Вам необходимо решить эту задачу согласно описанной математической модели.
Задача J. Суслик и собака
(Время: 1 сек. Память: 16 Мб)
На большом поле находятся суслик и собака. Собака хочет суслика съесть, а суслик хочет оказаться в безопасности, добежав до одной из норок, выкопанных в поле. Ни собака, ни суслик в математике не сильны, но, с другой стороны, они и не беспросветно глупы. Суслик выбирает определенную норку и бежит к ней по прямой с определенной скоростью. Собака, которая очень хорошо понимает язык телодвижений, угадывает, к какой норке бежит суслик, и устремляется к ней со скоростью вдвое большей скорости суслика. Если собака добегает до норки первой (раньше суслика), то она съедает суслика; иначе суслик спасается.
Требуется написать программу, которая поможет суслику выбрать норку, в которой он может спастись, если таковая существует.
Входные данные
Во входном файле INPUT.TXT записано в первой строке два числа – координаты суслика. Во второй строке записаны два числа – координаты собаки. В третьей строке записано число n – число норок на поле. В следующих n строках записаны координаты норок. Все координаты являются целыми числами, по модулю не превышающими 10000, и записываются через пробел. Количество норок не превышает 1000.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести число – номер норки, если у суслика есть возможность в ней спастись. Если у суслика есть возможность спрятаться в нескольких норках, то выведите ту, которая первая шла во входных данных. Если суслик не может спастись, то выведите в выходной файл «NO» (без кавычек).
