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

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

HotLog


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

Задачи олимпиады "Личное первенство по программированию среди школьников и студентов ИКИТ СФУ"

Задача A. Телефон

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

Услуги телефонной сети оплачиваются по следующему правилу: за разговоры до А минут в месяц – В рублей за минуту, а разговоры сверх установленной нормы оплачиваются из расчета С рублей за минуту. Требуется написать программу, вычисляющую плату за пользование телефоном для разговоров продолжительностью Т минут в месяц.

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

Входной файл INPUT.TXT содержит натуральные числа A, B, C и T, не превышающие 1000. Числа располагаются в одной строке и разделены пробелами.

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

В выходной файл OUTPUT.TXT выведите единственное целое число – месячную плату за пользование телефоном.

Примеры

INPUT.TXTOUTPUT.TXT
130 2 3 3060
220 1 3 3050

Задача B. Балда

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

А вы играли в «балду»? Это такая игра, когда из букв одного слова нужно составить как можно больше других слов. И чем длиннее такие слова, тем больше очков игрок заработает. Отсюда понятно, что самые выгодные слова – это те, которые получены перестановкой букв исходного слова.

Хитрый Дима решил написать программу, которая распечатает ему заготовки для игры в "балду". Дима их выучит, и будет побеждать всех своих друзей. Дима решил распечатать группы слов, которые получаются перестановкой букв.

Таких групп может оказаться слишком много, поэтому Дима решил распечатать первые пять с самым большим количеством слов. Ну, а если в словаре окажется менее пяти групп, Дима распечатает их все. А, может быть, и Вы себе такую программу создадите? Глядишь, и пригодится!

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

Входной файл INPUT.TXT содержит число N – количество слов в словаре (2 ≤ N ≤ 25000). Далее идет N слов, по одному в строке. Каждое слово содержит не более 40 символов. Коды ASCII символов в словах превышают 32.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
116
undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet
Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 1: displayed .
Group of size 1: singleton .
28
abc
c++
cba
abc
pascal
java
scalpa
basic
Group of size 3: abc cba .
Group of size 2: pascal scalpa .
Group of size 1: basic .
Group of size 1: c++ .
Group of size 1: java .

Задача C. Шахматное поле

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

На стандартной шахматной доске 8х8 заданы координаты двух клеток. Требуется определить: имеют ли данные клетки одинаковый цвет?

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

Входной файл INPUT.TXT содержит целые числа x1, y1, x2, y2, описывающие координаты двух клеток (x1,y1) и (x2,y2). Ограничения: 1 ≤ x1,y1,x2,y2 ≤ 8.

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

В выходной файл OUTPUT.TXT выведите YES, если поля одного цвета, или слово NO в противном случае.

Примеры

INPUT.TXTOUTPUT.TXT
11 1 4 4YES
21 2 7 5NO

Задача D. Пересечение множеств

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

Даны два неупорядоченных набора целых чисел (может быть, с повторениями). Выдать без повторений в порядке возрастания все те числа, которые встречаются в обоих наборах.

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

В первой строке входного файла INPUT.TXT записано через пробел два целых числа N и М (1 ≤ N, М ≤ 300 000) — количество элементов первого и второго наборов, соответственно. В следующих строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами или символами конца строки. Каждое из этих чисел попадает в промежуток от 0 до 105.

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

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

Пример

INPUT.TXTOUTPUT.TXT
111 6
2 4 6 8 10 12 10 8 6 4 2
3 6 9 12 15 18
6 12

Задача E. Алтайский технический университет

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

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

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

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

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

Первая строка входного файла INPUT.TXT содержит три числа: X,Y – целые координаты памятника и R – вещественный радиус площади (R>0). Во второй строке указано целое число N – количество людей на площади (1 ≤ N ≤ 150). Далее в N строках перечислены координаты точек (xi,yi), в которых находятся люди. Все координаты являются целыми числами, не превышающими по модулю 1000.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
125 25 3.5
7
25 28
23 27
27 27
24 23
26 23
24 29
26 29
3
2350 200 2
5
350 202
350 199
350 198
348 200
352 200
4

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


Задача F. Макрос

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

Однажды Бараш решил поучаствовать в литературном конкурсе программистов. Стихотворения принимались на четырех языках: Assembly, Foxy, Lispy, Prology. Как старый поэт-программист, Бараш признавал только Assembly. Поэтому писать пришлось на нем. Он запустил свой верный edit.com под Dos 6.22 и приступил к делу. Учитывая то, что Бараш был ленивым программистом, он вовсю использовал макросы. Это чрезвычайно ускоряло процесс стихосложения, так как у Бараша было множество заготовок, как и у любого старого поэта-программиста.

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

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

Бараш использовал следующий формат макроопределений (вместо каждого символа ‘_’ во входном и выходном файлах будет стоять точно один пробел):

  1. Макроопределения:
    #identificator_{}
    Идентификатор (имя макроопределения) состоит не более, чем из 10 строчных английских букв. Не встречается макроопределений с именем “rep”.
  2. Макровызовы:
    ##identificator_
  3. Циклические макроопределения:
    #rep_n_{}
    n – целое число повторов текста (0 ≤ n ≤ 100).

Назовем блоком текст , заключенный между фигурными скобками. Bсе стихотворение также называется блоком.

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

Рекурсивные вызовы отсутствуют. Вызовы несуществующих макроопределений игнорируются. Все макровызовы, которые в тексте стихотворения стоят ранее макроопределения, считаются несуществующими и, следовательно, игнорируются.

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

Входной файл INPUT.TXT содержит число N - количество строк в стихотворении. Далее идет N строк стихотворения. Общий объем входных данных не превышает 1024 байт.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15
##a_
#a_{a}##a_
#b_{##a__#a_{b}##a_#c_{##a_}_##c_}
##b_##c_
##a_

a

a_b_b
a
24
#a_{#b_{#c_{a}##c_}##b_}##a_
#e_{#b_{#c_{b}##c_}##b_}##e_
#f_{#b_{#c_{c}##c_}##b_}##f_
##a_##e_##f_##b_##c_
a
b
c
abc

Примечание

В примерах символы пробелов во входных и выходных данных обозначены символом "_" (подчеркивание).


Задача G. Единицы

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

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

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

Во входном файле INPUT.TXT записано целое число n (0 ≤ n ≤ 2×109).

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

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — количество двоичных единиц в записи числа n.

Примеры

INPUT.TXTOUTPUT.TXT
152
273

Задача H. Простые числа - 2

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

Знаете ли вы, что такое простое число? Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Например, числа 2, 3, 5, 7, 11 являются простыми. А числа 4, 6, 10 – составными.

Требуется из заданного набора чисел выбрать одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).

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

Первая строка входного файла INPUT.TXT содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
110
3 5 7 9 11 13 15 17 19 21
15
211
2 4 6 8 10 13 39 105 200 201 143
105

Задача I. Спираль

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

Спираль Требуется вывести квадрат, состоящий из N×N клеток, заполненных числами от 1 до N2 по спирали (см. примеры).

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

Во входном файле INPUT.TXT задано целое число N – размер квадратной матрицы (2 ≤ N ≤ 100).

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

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

Пример

INPUT.TXTOUTPUT.TXT
131 2 3
8 9 4
7 6 5
24  1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7
35 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

Задача J. Клад

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

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм действий. Большая часть таких действий просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис). Длина шага в любом направлении равна 1.

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

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

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

Первая строка входного файла INPUT.TXT содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.

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

В выходной файл OUTPUT.TXT выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось OX направлена на восток, а ось OY – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с точностью 10-3.

Примеры

INPUT.TXTOUTPUT.TXT
16
1 3
3 1
1 1
3 3
5 2
7 1
3.000 2.000
21
8 10
-7.071 7.071


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