Кафедра ИТ

Олимпиада по программированию

Одесская Национальная Академия связи им. А.С. Попова


Олимпиада по программированию
состоится 3 марта (четверг) в 15.00 в 244 аудитории (2-й лаб. корпус).
Для участия в олимпиаде, необходимо знание хотя бы одного языка программирования (Paskal, С++, Java,
Python и другие)

Олимпиада по информатике и программированию

Задания 2015/2016

 

1. Сумма.  Дано натуральное число N (известно, что ) и положительное вещественное x. Вычислить значение выражения   (10 б.)

 

2. Число наоборот. Дано не более чем четырехзначное натуральное число N (т.е. 0 < N < 10000). Напишите число, полученное, если записать цифры исходного числа задом наперед, при этом ведущие нули в полученном числе нужно опустить, т.е. для 123 ответ будет равен 321, а для 1200 ответ равен 21. В исходном числе ведущих нулей тоже нет. (20 б.)

 

3. Фигуры. Заданы 2 геометрические фигуры в плоскости: два прямоугольника, стороны которых параллельны осям координат. Для первого прямоугольника координаты верхнего левого угла (X1,Y1), правого нижнего (X2,Y2). Для второго прямоугольника координаты верхнего левого угла (X3,Y3), правого нижнего (X4,Y4). Определить, имеют ли фигуры общие точки (т.е. пересекаются или касаются). На рисунке прямоугольники не имеют общих точек (ответ «No»). Выведите «Yes», если есть хотя бы одна общая точка. (20 б.)

 

 

4. Матрица. Задана матрица размерности N на N, содержащая целые числа. В каждой строке числа упорядочены по возрастанию (т.е. каждый следующий элемент в строке больше предыдущего элемента той же строки). Определить существует ли целое число, которое присутствует в каждой строке матрицы и если да, вывести это число, иначе вывести «No».  Если таких чисел несколько, вывести минимальное число.

Пример матрицы

Ответ

4

0 1 2 4

1 2 4 9

2 3 4 10

-5 0 2 4

размер (N)

 

сама

матрица

 

2

(25 б.)

 

5.  Не очень сложные числа. Задано натуральное число N (известно, что ). Вывести в возрастающем порядке все числа в интервале от 2 до N включительно, которые являются простыми числами или квадратами простого числа. Простым числом называется число, которое делится без остатка только на два натуральных числа: на единицу и на само себя. Единица не является простым числом. Например, при N = 30 ответ выглядит так: 2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29.    (25 б.)

 

 

Примеры заданий для олимпиады по программированию

Задача A. Семья

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

Известно, что отец старше сына на N лет, а сын моложе отца в M раз. Определите, сколько лет отцу и сколько лет сыну.

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

Входной файл INPUT.TXT содержит два натуральных числа N и M, разделенных пробелом (1 ≤ N, M ≤ 104). Входные данные таковы, что возраст отца и возраст сына являются целыми числами.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
11 22 1
220 525 5

Задача B. Паркет - 2

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

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

Напоминание: правильный многоугольник – это выпуклый многоугольник, у которого все стороны равны между собой и все углы равны между собой.

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

Входной файл INPUT.TXT содержит целое число N – количество вершин в правильном многоугольнике (3 ≤ N ≤ 1000).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
14YES
25NO

Задача C. Обмен

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

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

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

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

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

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

В выходной файл OUTPUT.TXT выведите количество вариантов обмена фантиками по модулю 109+9.

Примеры

INPUT.TXTOUTPUT.TXT
121
232
349

Задача D. Апельсины - 2

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

На склад привезли коробку свежих апельсинов. Известно, что при поступлении апельсины весили ровно N грамм, а их влажность была F%. При хранении на складе апельсины могут либо вбирать в себя влагу из окружающего воздуха, либо терять влагу, если в помещении жарко и сухо. На складе решили апельсины ежедневно взвешивать и записывать изменения их массы в журнал: на сколько уменьшилась или увеличилась их масса по сравнению с предыдущим днем из-за поглощения влаги из воздуха или, наоборот, усыхания. Через M дней выяснилось, что апельсины необходимо перевезти на другой склад. Для этого нужно указать их текущий вес и влажность (в процентах).

Напомним, что влажность – это количество воды в веществе (в процентах) от первоначальной массы вещества.

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

Первая строка входного файла INPUT.TXT содержит три целых числа, разделенных пробелом: N – вес апельсинов (1 ≤ N ≤ 109), F – влажность апельсинов в процентах (1 ≤ F ≤ 99), M – количество дней (0 ≤ M ≤ 100). Далее идет M строк, в каждой из которых указано целое число K (|K| ≤ 107) – на сколько грамм изменился вес апельсинов по сравнению с предыдущим днем (со знаком «+», если он увеличился и со знаком «-», если уменьшился).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15000 99 2
+1500
-4000
2500 98
281 20 1
+15
96 33
310 67 1
+10
20 84
41000000000 23 1
+10000000
1010000000 24

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

(Время: 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