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

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

HotLog


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

Задачи олимпиады "Полуфинал XV Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"

Задача A. Станки

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

Есть два станка, на которых выпускают одинаковые запчасти. Один производит A запчастей в час, другой – В запчастей в час.

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

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

Входной файл INPUT.TXT содержит три натуральных числа: N, A и B (1 ≤ N, A, B ≤ 109).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
110 2 32
25 1 13

Задача B. Распродажа

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

В магазине товар стоил N рублей. Он сначала подорожал на A%. После чего его стоимость округлили до целого значения по стандартным правилам. Спустя некоторое время этот товар подешевел на B%. После чего его стоимость снова округлили до целого числа по стандартным правилам.

Сколько рублей стал стоить товар?

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

Входной файл INPUT.TXT содержит три целых числа, разделенных пробелом: N (1 ≤ N ≤ 109), A (0 ≤ A ≤ 100) и B (0 ≤ B ≤ 99).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1100 10 1099
21 0 501
3999999995 98 51880999991

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

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

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: N – количество элементов последовательности (1 ≤ N ≤ 104) и число М (1 ≤ M ≤ 231-1). Во второй строке записаны A[i] – N элементов последовательности (целые числа, разделенные пробелами, -231 ≤ A[i] ≤ 231-1).

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

В выходной файл OUTPUT.TXT выведите значения минимального и максимального элементов последовательности, которые делятся на M. Если ни одного такого элемента нет – выведите «NO» (без кавычек).

Примеры

INPUT.TXTOUTPUT.TXT
15 3
1 -9 0 5 12
-9 12
23 4
-5 2 13
NO

Задача D. Обратное число

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

Назовем обратным числом для натурального числа N число, получающееся по следующему правилу:

  1. число N записывают в двоичной системе счисления;
  2. все нули заменяют на единицы, а единицы – на нули;
  3. результат переводится в десятичную систему счисления.

Требуется написать программу, вычисляющую обратное число для заданного числа N.

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

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

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

В выходной файл OUTPUT.TXT выведите обратное число для числа N в десятичной системе счисления.

Примеры

INPUT.TXTOUTPUT.TXT
152
2123
3238
487
5100000000073741823

Задача E. Шифровка

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

Британские ученые изобрели новый алгоритм шифрования. Порядок действий для шифрования сообщения следующий:

  1. в строку записывается первое слово сообщения;
  2. второе слово дописывается в начало строки;
  3. третье слово дописывается в конец строки;
  4. четвертое слово снова дописывается в начало строки и т.д.

Кроме того, в каждом слове буквы располагаются таким же образом, т.е.:

  1. записывается первая буква;
  2. вторая буква дописывается в начало слова;
  3. третья буква дописывается в конец слова;
  4. четвертая буква снова дописывается в начало слова и т.д.

При этом:

  1. В качестве букв используются только английские строчные и прописные буквы.
  2. Слова в сообщении разделены строго одним пробелом.
  3. В начале и конце сообщения нет пробелов.

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

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

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

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

В выходной файл OUTPUT.TXT выведите расшифрованное сообщение.

Пример

INPUT.TXTOUTPUT.TXT
1rmrpiea srfaa tEo gveprooEto frasa pervogo primera

Задача F. Формула

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

Задана формула следующего вида:

<формула> ::=<цифра>|M(<формула>,<формула>)|m(<формула>,<формула>)
<цифра> ::= 0|1|2|3|4|5|6|7|8|9

где М обозначает функцию max – максимальный элемент, m обозначает функцию min – минимальный элемент, | - знак «или».

Требуется вычислить значение по данной формуле.

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

Входной файл INPUT.TXT содержит формулу в указанном формате без ошибок (непустую строку, состоящую не более чем из 1000 символов).

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

В выходной файл OUTPUT.TXT выведите цифру – значение данной формулы.

Примеры

INPUT.TXTOUTPUT.TXT
1M(5,m(6,8))6
2M(m(1,2),m(4,3))3
300

Задача G. Экзамены

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

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

Ваша задача – по экзаменационной ведомости определить фамилию и сумму баллов последнего зачисленного абитуриента.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа: N – количество абитуриентов в ведомости и M – количество абитуриентов, которые будут зачислены на первый курс (M ≤ N ≤ 1000). Далее идет N строк, в каждой из которых указана фамилия студента и 3 натуральных числа – баллы за каждый экзамен. Фамилия студента – непустая строка из английских символов (не более 10), первая буква прописная, остальные – строчные.

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

В выходной файл OUTPUT.TXT выведите фамилию и сумму баллов последнего поступившего абитуриента.

Пример

INPUT.TXTOUTPUT.TXT
13 2
Petrov 80 70 59
Ivanov 89 73 61
Sidorov 83 76 50
Sidorov 209

Задача H. Отрезок

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

Точка C - середина отрезка AB на плоскости. Найдите координаты точки B, если известны координаты точек A и C.

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

Входной файл INPUT.TXT содержит четыре целых числа – ХА, YА, ХC, YC - координаты точек A и C соответственно (числа разделены одним пробелом и не превышают 104 по абсолютной величине).

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

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

Пример

INPUT.TXTOUTPUT.TXT
1-4 8 3 710 6

Задача I. Лабиринт минотавра

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

Вы слышали про игру «Лабиринт минотавра»? В этой игре бесстрашный герой Тесей пытается выбраться из запутанного лабиринта. Лабиринт имеет прямоугольную форму – N×M клеток. За один ход Тесей может перейти на соседнюю свободную клетку по вертикали или по горизонтали, либо, если он находится на краю лабиринта, покинуть его. Клетка может быть либо свободной, либо занятой стеной или дверью. Сквозь стены проход невозможен. Сквозь двери можно проходить только при наличии ключа, который подходит ко всем дверям и хранится где-то в лабиринте!

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

  • Сначала он пытается найти выход по свободным клеткам.
  • Если Тесею это не удается – он пытается отыскать ключ, чтобы открывать им двери и искать путь на свободу.

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

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – длина и ширина лабиринта (2 ≤ N, M ≤ 1000). Далее идет N строк по M символов – описание лабиринта. Свободные клетки обозначены символом «.», стены – символом «#», двери – символом «-», «T» – положение Тесея в начальный момент времени, «K» – свободная клетка с ключом. Гарантируется, что в лабиринте только один Тесей и только один ключ.

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

В выходной файл OUTPUT.TXT выведите:

  • Если Тесей может выйти за пределы лабиринта без ключа – минимальное количество ходов, которое для этого понадобится.
  • Если не может – напечатать «No way» (без кавычек) и дополнительно через пробел вывести:
    • минимальное количество ходов, которое понадобится, чтобы добраться из начальной позиции Тесея до ключа;
    • «No key» (без кавычек) - если ключ недостижим.
    • Если ключ достижим, то следует дополнительно через пробел вывести:
      • минимальное количество ходов после взятия ключа, которое понадобится для того, чтобы покинуть лабиринт;
      • «No way» (без кавычек) – если даже с ключом нельзя выбраться из лабиринта.

Примеры

INPUT.TXTOUTPUT.TXT
12 2
T#
#K
1
25 5
-----
-T-K-
-.-.-
-...-
-----
No way 6 2
35 5
.#.#.
#T#.#
#...#
.#.#.
..#.K
No way No key
410 5
#####
#T..#
###.#
#...#
#.###
#...#
###.#
#...#
#K###
#####
No way 15 No way

Задача J. Квадрат

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

Определите, какое наибольшее количество точек с целочисленными координатами можно на листке в клеточку накрыть квадратом со стороной N клеток?

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

Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 104).

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
114
229


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