Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

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

Задачи олимпиады "Олимпиада, посвящённая Дню рождения российской информатики"

Задача A. Горсть монет

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

Вчера честный майнер Вася добыл «горсть» криптомонет – новой криптовалюты GoldCoin. Особенности технологии таковы, что каждая монета «весит» W байт. К сожалению, ночью на Васю напали хакеры, и утром он обнаружил, что его кошелек стал «легче» в K раз. Хакеры украли целых N монет!

Помогите Васе вспомнить, сколько монет он добыл.

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

Входной файл INPUT.TXT содержит целые числа N, W и K (1 ≤ N, W, K ≤ 109), где N – количество монет, которые украли хакеры, W – «вес» одной монеты в байтах, K – во сколько раз полегчал Васин криптокошелек.

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

В выходной файл OUTPUT.TXT выведите единственное число X – количество монет, которые добыл Вася. Гарантируется, что X – целое число.

Пример

INPUT.TXTOUTPUT.TXT
18 2 510

Задача B. Скидки

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

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

Какой суммы достаточно, чтобы оплатить покупку трех товаров, если известна цена каждого?

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

Входной файл INPUT.TXT содержит три натуральных числа, разделенных пробелами: A, B, C – стоимость первого, второго и третьего товара (A, B, C ≤ 109).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
18 11 617
210 10 1020

Задача C. Количество байт

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

В некоторой стране автомобильный номер длиной N символов составляют из заглавных букв (используются только K различных букв) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов). Определите объём памяти, отводимый этой программой для записи M номеров.

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

Входной файл INPUT.TXT содержит целые числа N, K и M (1 ≤ N, K, M ≤ 20 000).

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

В выходной файл OUTPUT.TXT выведите объём памяти в байтах, отводимый программой для записи M номеров.

Примеры

INPUT.TXTOUTPUT.TXT
17 18 60300
26 33 125625

Задача D. Игра с ладьей

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

На бесконечной вправо и вверх шахматной доске находится ладья. Два игрока передвигают ее по очереди. За один ход разрешено сдвинуть ладью вниз или влево на произвольное (ненулевое) количество клеток так, чтобы ладья не покинула доску. Цель игры – переместить ладью в левый нижний угол, то есть клетку с координатами (1,1). Известно, что оба игрока придерживаются оптимальной стратегии. Игрок №1 ходит первым, при этом он обязан совершить хотя бы один ход. Если первый ход сделать нельзя, то определить победителя также невозможно. Требуется написать программу, которая найдет номер победившего игрока, либо определит, что этого сделать нельзя.

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

Входной файл INPUT.TXT содержит два натуральных числа, разделенных пробелами: X и Y – координаты ладьи перед первым ходом (X,Y ≤ 109).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
11 10
21 61

Задача E. Проблема Коллатца

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

Студент Василий начитался новостей о Григории Перельмане и решил, что тоже хочет миллион долларов. Получить его он собирается, исследовав проблему Коллатца. Эта проблема предполагает следующую последовательность преобразований: некоторое натуральное число N делится на 2, если оно четное, в противном случае умножается на три и увеличивается на единицу. Получившееся число N1 (равное либо N/2, либо 3N+1) подвергается той же процедуре, и так далее. Существует гипотеза, что любое натуральное число N в результате вышеописанных преобразований превращается в единицу. Количество шагов, требующихся для получения единицы, зависит от исходного числа по весьма сложному принципу: так, 27 превращается в 1 за 111 шагов, а 3 – за 7.

Василий предположил, что быстрее всего в единицу превращаются числа Мерсенна – числа вида 2n-1, где n – целое положительное. Теперь ему хочется проверить эту теорию. Помогите ему, напишите программу, которая по заданному числу Мерсенна N и размеру отрезка M будет выяснять, существует ли число K (N < K ≤ N+M), которое будет превращаться в единицу за меньшее число шагов, нежели N.

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

Входной файл INPUT.TXT содержит целые числа N (3 ≤ N ≤ 10100) и M (0 ≤ M ≤ 10100), разделенные пробелом.

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

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

Пример

INPUT.TXTOUTPUT.TXT
13 54

Задача F. Ученики

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

Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество учеников (N ≤ 100). Далее, для каждого ученика определены 4 строки, содержащие фамилию, имя, класс и дату рождения соответственно. Фамилия и имя – строки, не превышающие 20 символов английского алфавита: первая буква заглавная, остальные – строчные. Класс – строка, состоящая из числа (от 1 до 11) и заглавной английской буквы (от «A» до «Z»). Дата рождения – строка в формате «ДД.ММ.ГГ». Гарантируется, что внутри одного класса нет однофамильцев.

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

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

Пример

INPUT.TXTOUTPUT.TXT
13
Sidorov
Sidor
9A
20.07.93
Petrov
Petr
10B
23.10.92
Ivanov
Ivan
9A
10.04.93
9A Ivanov Ivan 10.04.93
9A Sidorov Sidor 20.07.93
10B Petrov Petr 23.10.92

Задача G. Саша и массив

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

Маленький Саша любит играть с массивами. Недавно ему как раз подарили прекрасный массив из N натуральных чисел (a1, a2, ..., an, 1 ≤ ai ≤ 109). Вчера Саша придумал игру: он выбирает два числа l и r (1 ≤ l ≤ r ≤ N), записывает в тетрадочку их и максимальный элемент ai, где l ≤ i ≤ r.

За день Саша сделал M записей. Но случилось страшное: утром Саша обнаружил, что массив пропал! Помогите Саше восстановить массив, пользуясь его записями!

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

В первой строке входного файла INPUT.TXT находятся два числа N и M (1 ≤ N, M ≤ 1000), разделенных пробелом, – размер массива и число записей, сделанных Сашей. Следующие M строк описывают запросы. В каждой строке находится три числа, lj, rj и qj (1 ≤ lj ≤ rj ≤ N, 1 ≤ qj ≤ 109), разделенных пробелами, — левая и правая границы отрезка и максимум на нем.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13 3
1 1 1
1 2 2
1 3 10
EASY
1 2 10
22 3
1 1 5
2 2 6
1 2 5
FAIL

Задача H. Производная

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

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

  1. знак умножения между коэффициентом и x не выводится;
  2. если коэффициент равен нулю, соответствующий моном не выводится;
  3. если коэффициент равен единице или минус единице, при записи соответствующего монома единица не выводится;
  4. если все коэффициенты равны нулю, выводится 0;
  5. если показатель степени равен нулю, выводится только коэффициент;
  6. если показатель степени равен единице, то единица и знак возведения в степень не выводятся;
  7. если знак '+' предшествует отрицательному коэффициенту или стоит в начале выражения, знак '+' не выводится;
  8. мономы выводятся строго в порядке убывания показателей степени.

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

Входной файл INPUT.TXT содержит строку длиной не более 1000 символов, описывающую многочлен. Коэффициенты многочлена целые, по модулю не превосходящие 104. Показатели степени – целые неотрицательные числа, не превосходящие 104. Гарантируется, что входной многочлен записан в соответствии с пунктами 1-7 правил, указанных в условии задачи.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1-5x^3+4x^2+x+1-15x^2+8x+1
2x^2+4x-10-x2x+3
370

Примечание

Вычисление производной многочлена сводится к вычислению суммы производных каждого его члена. Производная одного члена вычисляется как производная степенной функции по формуле (cxp)' = cpxp-1.


Задача I. Деление

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

На квадратном торте размером N×N расставлено M свечей. Определить, можно ли одним прямолинейным разрезом разделить торт на две части, равные по площади, так, чтобы все свечи оказались на одной половине. Свечи считаем точками. Разрез не может проходить через свечу.

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

Первая строка входного файла INPUT.TXT содержит число N (1 < N ≤ 100) – длину стороны квадрата. Вторая строка теста содержит число M (0 < M ≤ 100) – количество свечей на торте. Третья строка – координаты свечей, разделенные пробелами: X1 Y1 X2 Y2 … Xm Ym (0 < Xi, Yi < N), заданные в системе координат с началом в одном из углов квадрата и осями – сторонами квадрата. Все исходные данные - целые положительные числа. Координаты всех свечей различны.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
16
4
1 1 2 2 1 2 2 1
YES
220
10
1 1 2 2 1 2 2 1 10 10 3 4 7 2 3 8 2 11 11 3
NO

Задача J. Последовательность - 6

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

Дано натуральное число A. К нему применили следующую операцию – все цифры возвели в квадрат и просуммировали.

Например, для числа 123 получим 12 + 22 + 32 = 14.

К полученному результату указанную операцию применили еще несколько раз.

Определите, какое число получится, если указанную операцию повторить ровно N раз для заданного числа A.

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

Входной файл INPUT.TXT содержит два целых числа A и N (0 ≤ A, N ≤ 109).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1123 114
21000000000 10000000001
34 489


 
     
Югорский НИИ ИТ, Югорский ФМЛ