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

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

HotLog


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

Задачи олимпиады "Тринадцатая личная олимпиада"

Задача A. Преобразователь строк - 2

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

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

  • разворот (обозначается символом R) – из строки s1s2 ... sn-1sn получается строка snsn−1 ... s2s1. Пример: из строки «abcde» получится строка «edcba»;
  • сортировка (обозначается символом S) – из строки s1s2 ... sn-1sn получается строка, содержащая те же символы, но отсортированные в порядке неубывания по алфавиту. Пример: из строки «hello» получится строка «ehllo».

Задана строка и последовательность операций над некоторыми ее подстроками. Необходимо определить результат применения этих операций.

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

Первая строка входного файла INPUT.TXT содержит исходную строку. Она не пуста, состоит только из строчных букв английского алфавита. Ее длина m не превышает 200 символов. Вторая строка содержит количество операций n (1 ≤ n ≤ 200).

Каждая из последующих n строк содержит описание одной операции. Описание операции имеет формат «OP L R», где OP – символ, обозначающий операцию, L – позиция первого символа подстроки, к которой применяется операция, R – позиция ее последнего символа (1 ≤ L ≤ R ≤ m). Если до применения операции обрабатываемая строка имела вид s1s2 ... sm, то после применения операции она будет иметь вид s1 ... sL−1 OP(sL ... sR) sR+1 ... sm, где OP(sL ... sR) – результат применения описываемой операции к подстроке sL ... sR.

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

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

Пример

INPUT.TXTOUTPUT.TXT
1helloworld
2
S 1 5
R 6 10
ehllodlrow

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

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

На склад привезли коробку свежих апельсинов. Известно, что при поступлении апельсины весили ровно 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

Задача C. Стрелочки

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

На бумаге нарисовали клетчатое поле N×M клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».

Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю.

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

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

Во входном файле INPUT.TXT заданы сначала размеры поля – число строк N и число столбцов M (1 ≤ N, M ≤ 1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 – вверх, 3 – влево, 4 – вниз. Числа в строке разделяются пробелами.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
16 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
23
22 2
1 2
3 4
0

Задача D. Многоугольник и точки

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

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

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

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

Каждая из последующих N строк содержит по два целых числа – координаты очередной вершины многоугольника. Вершины перечислены в порядке обхода, причём возможны варианты как «против часовой стрелки», так и «по часовой стрелке». Далее следуют M строк, содержащих список точек, заданных в аналогичном формате. Все координаты являются целыми числами и по модулю не превосходят 109.

Гарантируется, что многоугольник не имеет самопересечений, является строго выпуклым, и каждый его угол лежит в интервале от 0 до 180 градусов.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
14 3
1 1
1 -1
-1 -1
-1 1
0 0
0 1
0 2
Yes
Yes
No
23 1
1 0
1 1
0 0
0 1
No


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



http://knyaz-bereg.ru/ земельные участки для жилья в раменском районе.