Темы --> Информатика
    Язык программирования(948 задач)
    Алгоритмы(1617 задач)
    Структуры данных(265 задач)
    Интерактивные задачи(17 задач)
    Другое(50 задач)
---> 2609 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
ограничение по времени на тест
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 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан невзвешенный граф. По графу перемещаются роботы, для которых заданы начальные вершины. Требуется определить, через какое время все роботы встретятся в какой либо вершине или середине ребра.

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

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

Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).

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

Сначала на вход программы поступают числа N — количество залов (1N400) и K — количество туннелей (1K20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1M400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

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

Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

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

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

Примеры
Входные данные
4 5
1 2
2 3
3 4
1 4
1 3
3
1 2 4
Выходные данные
1
Входные данные
3 2
1 2
2 3
2
1 3
Выходные данные
1

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