Темы
    Информатика(2609 задач)
---> 228 задач <---
    2003(8 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(19 задач)
    2008(19 задач)
    2009(18 задач)
    2010(18 задач)
    2011(18 задач)
    2012(19 задач)
    2013(19 задач)
    2014(20 задач)
    2015(21 задач)
    2016(20 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

По новым правилам Московской командной олимпиады итоги олимпиады подводятся следующим образом.

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

Каждая задача оценивается из 2-х баллов. 2 балла получает программа, которая проходит все тесты. Кроме того, 1 баллом оцениваются решения, которые проходят некоторое количество первых тестов в задаче (это количество определяется жюри, оно может быть различным в различных задачах, это количество, как и общее количество тестов по задаче, участникам не сообщается). Жюри может (однако не обязано) указать в условии дополнительные ограничения, которым удовлетворяют тесты, за прохождение которых ставится 1 балл.

Помимо баллов за решение задач, команды получают штрафное время. За каждую задачу штрафное время определяется следующим образом.

  • Если за данную задачу у команды 0 баллов (независимо от того, делала команда попытки сдачи этой задачи или нет), штрафное время за эту задачу равно 0.
  • Если у команды 1 балл за эту задачу, то штрафное время за задачу определяется как время в минутах от момента начала тура до момента, когда была сделана первая попытка, которая была оценена в 1 балл, плюс по 20 штрафных минут за каждую попытку по этой задаче, ей предшествовавшую. Заметьте, что все попытки, которые делаются после того, как команда получила 1 балл за задачу (но до того, как она получила 2 балла), не влияют на штрафное время и на баллы по задаче (даже если после этого будет сделана попытка, которая получит 0 баллов, 1 набранный балл у команды останется).
  • Если у команды 2 балла за задачу, то штрафное время за эту задачу определяется как время в минутах от момента начала тура до момента, когда задача была сдана на 2 балла, плюс по 20 штрафных минут за каждую предшествовавшую неверную попытку по этой задаче (при этом неверными теперь считаются в том числе и попытки, получающие 1 балл). Заметьте, что все попытки, которые делаются после того, как команда решила задачу полностью, не влияют на штрафное время.

При этом если произошла ошибка компиляции программы, то такая попытка не учитывается при подсчете неверных попыток (то есть она вообще игнорируется).

Например, если на 1-й минуте команда послала программу, которая набрала 0 баллов, то штрафное время равно 0. Пусть на 2-й минуте команда послала решение, которое набрало 1 балл, тогда команда имеет за эту задачу 1 балл и штрафное время, равное 22 минутам (2 минуты от начала тура + 20 штрафных минут). Если на 3-й минуте команда сдала решение задачи на 2 балла, то результат по этой задаче у команды 2 балла, а штрафное время равно 43 минуты (3 минуты от начала тура + 2*20 минут за 2 предыдущие попытки).

И баллы, и штрафное время, полученное командой по разным задачам, суммируются (получаются суммарные баллы и суммарное штрафное время). Команды ранжируются сначала по баллам, а при равном количестве баллов — по штрафному времени (чем меньше штрафное время, тем выше место команды).

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

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

В первой строке задается число N — суммарное количество задач (1N≤26). Во второй строке содержатся N чисел Ai — количество тестов в каждой задаче (2Ai100). В третьей строке задаются N чисел Bi — количество тестов, которое должно пройти в соответствующей задаче, чтобы команда получила за нее 1 балл (0<Bi<Ai).

Далее идет M — количество сделанных командой попыток. Затем следуют M строк, каждая из которых содержит 3 числа: первое задает время в минутах от начала тура до момента совершения данной попытки, второе — номер задачи, третье — количество пройденных тестов (или –1, если произошла ошибка компиляции). Все попытки упорядочены по времени, ни в какую минуту команда не делала более одной попытки.

По правилам олимпиады общее количество попыток не превышает 200, продолжительность тура — 3-х месяцев (на самом деле, командная олимпиада длится обычно не более 5 часов, однако жюри олимпиады не исключает, что эти же правила когда-нибудь будут использоваться в заочном туре, который длится как раз 3 месяца).

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

Выведите два целых числа — количество набранных командой баллов и суммарное штрафное время.

Примеры
Входные данные
1 
20 
10
3
1 1 0
2 1 10
3 1 20
Выходные данные
2 43
Входные данные
2
17 24
2 2
2
5 1 1
8 2 -1
Выходные данные
0 0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дана дробь 1. Требуется ее сократить, то есть записать это же число в виде 2, где c — целое число, d — натуральное число и d минимальное возможное.

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

Вводятся два целых числа a и b (–100a100, 0<b100).

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

Выведите два числа c и d.

Оценка задачи

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

Примеры
Входные данные
3 6
Выходные данные
1 2
Входные данные
-2 5
Выходные данные
-2 5
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Группа людей называется современниками, если был такой момент, когда они могли собраться все вместе и обсуждать какой-нибудь важный вопрос. Для этого в тот момент, когда они собрались, каждому из них должно было уже исполниться 18 лет, но еще не исполниться 80 лет.

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

Будем считать, что в день своего 18-летия человек уже может принимать участие в такого рода собраниях, а в день 80-летия, равно как и в день своей смерти, — нет.

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

Сначала на вход программы поступает число N — количество людей (1N10000). Далее в N строках  вводится по шесть чисел — первые три задают дату (день, месяц, год) рождения, следующие три — дату смерти (она всегда не ранее даты рождения). День (в зависимости от месяца, а в феврале — еще и года) от 1 до 28, 29, 30 или 31, месяц — от 1 до 12, год — от 1 до 2005.

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

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

Никакое множество не должно быть указано дважды.

Если нет ни одного непустого максимального множества, выведите  одно число 0.

Гарантируется, что входные данные будут таковы, что размер  выходных данных  для правильного ответа не превысит 2 Мб.

Оценка задачи

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

Примеры
Входные данные
3
2 5 1988 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
Выходные данные
2 
3 
Входные данные
3
2 5 1968 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
Выходные данные
2 
1 3 
Входные данные
3
2 5 1988 13 11 2005
1 1 1 1 1 10
2 1 1910 1 1 1928
Выходные данные
0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Напишите программу, находящую количество троек целых чисел a, b, p таких, что p — простое число, числа удовлетворяют равенству:

3

и каждое из чисел a, b и p лежит в промежутке от N до M (то есть Na M, Nb M, Np M).

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

Вводятся два целых числа N и M (0NM100000)

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

Выведите искомое количество троек чисел a, b, p.

Оценка задачи

1 балл получат программы, правильно решающие задачу при ограничениях 0NMN+5000.

Примеры
Входные данные
1 8
Выходные данные
1
Входные данные
5 20
Выходные данные
1
Входные данные
1 7
Выходные данные
0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Клавиатура сотового телефона выглядит так:


1 — пробел



2 — abc


3 — def


4 — ghi



5 — jkl


6 — mno


7 — pqrs



8 — tuv


9 — wxyz

Режим ввода T2005 устроен следующим образом. В телефоне есть словарь. Пользователь, чтобы ввести слово, последовательно нажимает клавиши, на которых написаны буквы этого слова. Например, чтобы ввести слово begin пользователь должен нажимать клавиши 23446. Но как только в словаре оказывается только одно слово с таким началом, это слово автоматически подставляется и, кроме того, после этого слова автоматически добавляется пробел. Например, пусть пользователь нажал клавиши 234, и оказалось, что слов, ввод которых начинается с нажатия именно этих клавиш, — ровно одно. Тогда автоматически подставится это слово и пробел после него, а все последующие нажатия клавиш уже будут относиться к вводу следующего слова.

Если для ввода какого-то слова нужно нажать последовательность клавиш, которая может являться началом какого-то другого слова, то после ввода этого слова нужно нажать клавишу 1, что соответствует вводу пробела. При вводе пробела считается, что вы ввели все слово целиком (а не только какое-либо его начало). Если после ввода пробела оказалось, что в словаре такой последовательности клавиш удовлетворяет несколько слов, подставляется первое из них в алфавитном порядке. Если (опять же после ввода пробела) оказалось, что в словаре нет слова, которое может быть введено такой последовательностью клавиш, то все, что было введено после предыдущего пробела (введенного или автоматически подставленного, или, если в тексте ранее не встречалось ни одного пробела — от начала текста) удаляется. Если после ввода пробела (как нажатием "1", так и автоподстановкой) или в начале текста нажимается клавиша "1", то ее нажатие игнорируется.

Вам дан словарь и последовательность нажатий клавиш. Выведите текст, который был введен пользователем.

Примечание: в тексте используются только маленькие латинские буквы и символ пробел.

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

Сначала на вход программы поступает число N — количество слов в словаре (2N100000). В следующих N строках задается словарь. Каждое слово записано в отдельной строке. Слова расположены в алфавитном порядке. Никакое слово в словаре не встречается дважды. Длина каждого слова не превосходит 10 символов.

Далее вводится число M — количество нажатий клавиш (1M20000). Затем задается M разделяющихся пробелами чисел, описывающих нажатые клавиши. Последней нажатой клавишей всегда является клавиша "1".

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

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

Примечание:


2
a
z
2
5 1



Примечание: в этом примере выходной файл должен быть создан, но должен быть пустым, в частности, в него не нужно выводить пробел.

Оценка задачи

1 балл получат программы, правильно решающие задачу при ограничениях 2N100, 1M200.

Примеры
Входные данные
5
po
pod
sasha
shla
shosse
12
7 4 5 7 2 7 6 1 7 4 6 1
Выходные данные
shla sasha po shosse 
Входные данные
2
sem
vosem
6
7 8 9 7 8 1
Выходные данные
sem vosem 

Страница: 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест