day2-v3

Кондиционер
Имя входного файла:
cond.in

Имя выходного файла:
cond.out

Ограничение по времени:
2 секунды

Ограничение по памяти:
256 мегабайт

В офисе, где работает программист Петр, установили кондиционер нового типа. Этот кондиционер отличается особой простотой в управлении. У кондиционера есть всего лишь два управляемых параметра: желаемая температура и режим работы.
Кондиционер может работать в следующих четырех режимах:
«freeze» охлаждение. В этом режиме кондиционер может только уменьшать температуру. Если температура в комнате и так не больше желаемой, то он выключается.
«heat» нагрев. В этом режиме кондиционер может только увеличивать температуру. Если температура в комнате и так не меньше желаемой, то он выключается.
«auto» автоматический режим. В этом режиме кондиционер может как увеличивать, так и уменьшать температуру в комнате до желаемой.
«fan» вентиляция. В этом режиме кондиционер осуществляет только вентиляцию воздуха и не изменяет температуру в комнате.
Кондиционер достаточно мощный, поэтому при настройке на правильный режим работы он за час доводит температуру в комнате до желаемой.
Требуется написать программу, которая по заданной температуре в комнате troom, установленным на кондиционере желаемой температуре tcond и режиму работы определяет температуру, которая установится в комнате через час.
Формат входного файла
Первая строка входного файла содержит два целых числа troom, и tcond, разделенных ровно одним пробелом (–50 
· troom 
· 50, –50 
· tcond 
· 50).
Вторая строка содержит одно слово, записанное строчными буквами латинского алфавита режим работы кондиционера.
Формат выходного файла
Выходной файл должен содержать одно целое число температуру, которая установится в комнате через час.
Примеры входных и выходных файлов
cond.in
cond.out

10 20
heat
20

10 20
freeze
10

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

Праздничный ужин
Имя входного файла:
dinner.in

Имя выходного файла:
dinner.out

Ограничение по времени:
2 секунды

Ограничение по памяти:
256 мегабайт

Рядом с офисом компании, в которой работает программист Джон, открылось новое кафе. Директор компании решил провести там новогодний ужин.
Меню праздничного новогоднего ужина в кафе состоит из k типов блюд. Для каждого типа блюда есть несколько вариантов на выбор. Всего есть a1 вариантов для первого типа блюда, a2 вариантов для второго типа блюда, и так далее, ak вариантов для k-го типа блюда. Всего, таким образом, предлагается a1Чa2ЧЧak различных заказов праздничного ужина.
Всего на ужине будут присутствовать m сотрудников компании. Каждый сотрудник должен заказать ровно один вариант блюда на выбор. Таким образом, ужин каждого сотрудника будет состоять из k блюд. Для того чтобы ужин каждого сотрудника компании был уникален, администратор кафе придумал следующую схему. Сотрудники делают заказ ужина по меню один за другим. Каждый сотрудник выбирает k блюд, по одному варианту каждого типа. После выбора варианта заказа из меню, сотрудник указывает на одно из заказанных им блюд, и этот вариант этого типа блюда больше не предлагается тем сотрудникам, которые делают заказ после него.
Каждый сотрудник компании запомнил, сколько возможных заказов ужина ему было предложено. Выяснилось, что директору, который выбирал первым, было предложено на выбор n1 = a1Чa2ЧЧak заказов. Тому, кто выбирал вторым, досталось лишь n2 < n1 заказов, поскольку один из вариантов одного из типов блюд уже не был доступен, и так далее. Джону, который выбирал последним, был предложен выбор лишь из nm заказов. Джон заинтересовался, а какое количество вариантов каждого типа блюд было на выбор у директора компании.
Требуется написать программу, которая по заданным числам k, m и n1, n2, , nm выяснит, какое количество вариантов каждого типа блюд изначально предлагалось на выбор.
Формат входного файла
Первая строка входного файла содержит два целых числа k и m, разделенных ровно одним пробелом (1 
· k 
· 20, 2 
· m 
· 100). Вторая строка содержит m чисел: n1, n2, , nm (для всех i от 1 до m выполняется неравенство 1 
· ni 
· 109).
Формат выходного файла
Выходной файл должен содержать k чисел: a1, a2, , ak. Если возможных вариантов решения поставленной задачи несколько, требуется вывести любой. Соседние числа должны быть разделены ровно одним пробелом. Гарантируется, что хотя бы одно решение существует.
Пример входного и выходного файлов
dinner.in
dinner.out

3 3
12 8 4
3 2 2

Пояснения к примеру
События в примере могли развиваться, например, следующим образом.
Исходно было 3Ч2Ч2=12 вариантов заказа ужина. Директор, выбрав один из вариантов, указал на свое первое блюдо, поэтому второму сотруднику предлагалось уже лишь 2 варианта первого блюда. У него осталось 2Ч2Ч2 = 8 вариантов ужина. Он также указал на свое первое блюдо, и Джон уже мог выбирать лишь из 1Ч2Ч2 = 4 вариантов ужина.
Космический кегельбан
Имя входного файла:
spacepin.in

Имя выходного файла:
spacepin.out

Ограничение по времени:
2 секунды

Ограничение по памяти:
256 мегабайт

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.
Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом r метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют n рядов, в первом ряду стоит одна кегля, во втором две, и так далее. В последнем n-м ряду стоит n кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке (0, 0). Центры кеглей во втором ряду находятся в точках (–1, 1) и (1, 1). Таким образом, центры кеглей в i-м ряду находятся в точках с координатами (–(i – 1), i – 1), (–(i – 3), i – 1), , (i – 1, i – 1).
Игра происходит следующим образом. Используется шар с радиусом q метров. Игрок выбирает начальное положение центра шара (xc, yc) и вектор направления движения шара (vx, vy). После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора (vx, vy). Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.
На рисунке приведен пример расположения кеглей для r = 500, n = 4 и шара для q = 1000, xc = –2, yc = –2, vx = 1, vy = 1.
13 EMBED Visio.Drawing.11 1415
Требуется написать программу, которая по заданным радиусу кегли r, количеству рядов кеглей n, радиусу шара q, его начальному положению (xc, yc) и вектору направления движения (vx, vy) определяет количество кеглей, сбитых шаром.
Формат входного файла
Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом (1 
· r 
· 700, 1 
· n 
· 200 000).
Вторая строка входного файла содержит целое число q (1 
· q 
· 109).
Третья строка входного файла содержит два целых числа xc и yc, разделенных ровно одним пробелом (–106
· xc 
· 106, –106
· yc, 1000Чyc < –(r + q) ).
Четвертая строка входного файла содержит два целых числа vx и vy, разделенных ровно одним пробелом (–106
· vx 
· 106, 0 < vy 
· 106).
Формат выходного файла
Выходной файл должен содержать одно целое число количество сбитых кеглей.
Пример входного и выходного файлов
spacepin.in
spacepin.out

500 4
1000
-2 -2
1 1
7

Пояснения к примеру
Рисунок ниже показывает, какие кегли будут сбиты (такие кегли обозначены «х»).
13 EMBED Visio.Drawing.11 1415
Система оценивания
Правильные решения для тестов, в которых 1 
· n 
· 1000 и vx = 0, будут оцениваться из 20 баллов.
Правильные решения для тестов, в которых 1 
· n 
· 1000 и vx 
· 0, будут оцениваться еще из 20 баллов.
Правильные решения для тестов, в которых 1000 < n 
· 200 000 и vx = 0, будут оцениваться еще из 20 баллов.
Чтобы получить оставшиеся 40 баллов, решение должно правильно работать также для тестов, в которых 1000 < n 
· 200 000 и vx 
· 0.
«Abracadabra»
Имя входного файла:
sufpref.in

Имя выходного файла:
sufpref.out

Ограничение по времени:
2 секунды

Ограничение по памяти:
256 мегабайт

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.
В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, , tn и набор из m строк-образцов s1, s2, , sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.
Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, , tn, заданному числу m и m строкам-образцам s1, s2, , sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.
Формат входного файла
Первая строка входного файла содержит целое число n (1 
· n 
· 200 000).
Последующие n строк содержат слова t1, t2, , tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.
Затем следует строка, содержащая целое число m (1 
· m 
· 200 000).
Последующие m строк содержат строки-образцы s1, s2, , sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.
Формат выходного файла
Выходной файл должен содержать m чисел, по одному на строке.
Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.
Пример входного и выходного файлов
sufpref.in
sufpref.out

4
abacaba
abracadabra
aa
abra
3
a
abra
abac
4
2
0

Система оценивания
Правильные решения для тестов, в которых 1 
· n 
· 100, 1 
· m 
· 100, будут оцениваться из 30 баллов.








Региональный этап Всероссийской олимпиады школьников по информатике.
Второй тур, 23 января 2012 года


Страница 13 PAGE 14215 из 13 NUMPAGES 14515



Root Entry

Приложенные файлы

  • doc 19003286
    Размер файла: 160 kB Загрузок: 0

Добавить комментарий