Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 13 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников --> 7-9 классы
    2006(5 задач)
    2007(5 задач)
    2008(5 задач)
    2009(5 задач)
    2010(5 задач)
Страница: 1 2 3 >> Отображать по:
#484
Реклама
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня.

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

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

Если трансляция ролика включается, например, в момент времени 10, то покупатели, пришедшие в супермаркет в момент времени 10 (или раньше) и уходящие из супермаркета в момент 15 (или позднее) успеют его прослушать целиком, а, например, покупатель, пришедший в момент времени 11, равно как и покупатель, уходящий в момент 14 - не успеют. Если покупатель успевает услышать только конец первой трансляции ролика (не сначала) и начало второй трансляции (не до конца), то считается, что он не услышал объявления. Если покупатель успевает услышать обе трансляции ролика, то при подсчете числа людей, прослушавших ролик, он все равно учитывается всего один раз (фирме важно именно количество различных людей, услышавших ролик).

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

В первой строке входного файла вводится  число N - количество покупателей (1<=N<=2000). В следующих N строках записано по паре натуральных чисел - время прихода и время ухода каждого из них. Все значения времени - натуральные числа, не превышающие 109. Время ухода человека из супермаркета всегда строго больше времени его прихода в супермаркет.

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

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

Примеры

Входные данные  Выходные данные  Пояснение
4
1 11
1 3
6 15
1 6 		3 1 6 Трансляция роликов начинается в моменты времени 1 и 6. Первое объявление успевают прослушать покупатели номер 1 и 4, второе - 1 и 3. Когда бы ни начиналась трансляция объявления, 2-й покупатель не сможет его прослушать, так как находится в супермаркете менее 5 минут. Приведенный ответ является не единственным верным ответом на этот тест.
1
1 10 		1 3 25 Объявление, трансляция которого начинается в момент 3, единственный покупатель обязательно услышит. Вторую трансляцию (раз она оплачена) мы можем сделать когда угодно, например, в 25 минут в пустом супермаркете (впрочем, мы не можем начать трансляцию второго объявления, например, в момент 7 - т.к. к этому моменту еще не закончится первая трансляция)
3
1 10
11 20
21 30 		2 1 22 Объявление услышат лишь 2 из 3-х покупателей.
#485
Ставки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B".

Организаторы бегов решили выяснить, могут ли тараканы прийти в таком порядке, чтобы у каждого болельщика сыграла ровно одна ставка из двух (то есть чтобы ровно одно из двух утверждений каждого болельщика оказалось верным). Считается, что никакие два таракана не могут прийти к финишу одновременно.

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

В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и число N, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".

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

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

Если требуемого результата добиться нельзя, выведите одно число 0.

Пример

Входные данные Выходные данные
3 2
2 1 2 3
1 2 3 2 		3 2 1
3 4
1 2 1 3
1 2 3 1
1 2 2 3
1 2 3 2 		0
#508
Кинотеатр
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

\(X\) мальчиков и \(Y\) девочек пошли в кинотеатр и купили билеты на подряд идущие места в одном ряду. Напишите программу, которая выдаст, как нужно сесть мальчикам и девочкам, чтобы рядом с каждым мальчиком сидела хотя бы одна девочка, а рядом с каждой девочкой — хотя бы один мальчик.

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

Вводятся два числа — \(X\) и \(Y\) (оба числа натуральные, не превосходящие 100).

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

Выведите какую-нибудь строку, в которой будет ровно \(X\) символов B (обозначающих мальчиков) и \(Y\) символов \(G\) (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры
Входные данные
5 5
Выходные данные
BGBGBGBGBG
Входные данные
5 3
Выходные данные
BGBGBBGB
Входные данные
100 1
Выходные данные
NO SOLUTION
#510
Метро
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задано описание метрополитена в виде описания веток. Каждая ветка содержит номера станций, которые на ней находятся. Станция, присутствующая на нескольких ветках - пересадочная. Требуется определить маршрут от станции до станции с минимальным количеством пересадок.

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до \(N\). На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции \(A\) на станцию \(B\). Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции \(A\) на станцию \(B\) добраться невозможно, в этом случае ваша программа должна это определить.

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

Сначала вводится число \(N\) — количество станций метро в городе (2≤\(N\)≤100). Далее следует число \(M\) — количество линий метро (1≤\(M\)≤20). Далее идет описание \(M\) линий. Описание каждой линии состоит из числа \(P_i\) — количество станций на этой линии (2≤\(P_i\)≤50) и \(P_i\) чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: \(A\) — номер начальной станции, и \(B\) — номер станции, на которую нам нужно попасть. При этом если через станцию \(A\) проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию \(B\) проходит несколько линий, то нам не важно, по какой линии мы приедем.

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

Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции \(A\) на станцию \(B\) невозможно, программа должна вывести одно число –1 (минус один).

Примеры
Входные данные
5
2
4 1 2 3 4
2 5 3
3 1
Выходные данные
0
Входные данные
5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
Выходные данные
2
Входные данные
10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
Выходные данные
1
Входные данные
4
2
2 1 2
2 3 4
1 3
Выходные данные
-1
#513
Шахматная доска
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.

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

Сначала вводится число \(N\) (1 ≤ \(N\) ≤ 64) – количество выпиленных клеток. В следующих \(N\) строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

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

Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).

Пояснения к примерам

1) Вырезан уголок из трех клеток. Сумма длин его сторон равна 8.

2) Вырезана одна клетка. Ее периметр равен 4.

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