Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 98 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада
    8 класс(18 задач)
    9-11 классы(228 задач)
Страница: << 14 15 16 17 18 19 20 Отображать по:
#111272
И последние станут первыми
  
Темы: [Перебор]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
6 megabytes

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

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

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

Первая строка содержит три натуральных числа: N — количество команд, K — количество задач, L — лимит на суммарное число посылок по задачам (N ≤ 1000, K ≤ 12, K ≤ L ≤ 200).

Далее следуют N строк, описывающих саму таблицу на момент заморозки. i-я строка содержит название команды (строка из латинских символов и цифр длины не более 50) и K элементов, показывающих успех команды по каждой из задач. j-й элемент таблицы имеет вид  * Wrong(Time), где:

 *  — знак ‘ + ’ или ‘ - ’, показывающий, решила ли команда задачу;

Wrong — количество неуспешных посылок по данной задаче;

Time — минута, на которой команда сдала задачу (0 ≤ Time ≤ 239); если данная задача ещё не была решена, Time = 0.

Команды упорядочены от первого места на момент заморозки к последнему. Напоминаем, что команды сортируются по числу решённых задач, а при равном количестве — по увеличению штрафного времени, которое складывается из времени сдачи задачи и общего количества неудачных попыток по решённым задачам, умноженного на 20. Продолжительность олимпиады — 5 часов.

Гарантируется, что ни одна команда не превысила лимит на число посылок и что никакие две команды не имеют одинаковый с точки зрения сортировки результат.

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

Если порядок команд теоретически мог измениться за последний час соревнований на обратный, то сначала выведите строку «Possible», а затем подробную таблицу окончательных результатов в формате, аналогичном таблице из входного файла (см. пример). Если соревнование так закончиться не могло, то выведите единственную строку «Impossible».

Примеры тестов

Входные данные
3 3 10
winner +2(235) +3(170) -2(0)
middle -2(0) +1(30) -0(0)
looser -1(0) +5(30) -0(0)
Выходные данные
Possible
looser +1(240) +5(30) +0(240)
middle +5(241) +1(30) +0(240)
winner +2(235) +3(170) +2(240)
Входные данные
2 2 20
winner +10(1) +0(10)
looser -0(0) +1(1)
Выходные данные
Impossible

#111273
Бег по кругу
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
6 megabytes

Спортивный программист для достижения вершин своего мастерства должен быть натренирован в совершенно разных аспектах, в том числе и физически. Кто-то для этого садится на велосипед, кто-то ныряет в бассейн, а молодой программист Влад бегает по стадиону. Но из-за неаккуратного обращения с личными вещами его секундомер может измерять время только в минутах, без указания секунд и тем более их долей.

Чтобы следить за прогрессом своего ученика, тренеру Влада приходится довольствоваться показаниями этого прибора. Каждый раз, когда Влад пробегает мимо тренера, сделав очередной круг по стадиону, тот записывает в блокнот показания секундомера в минутах. Фактически показания секундомера соответствуют целому числу минут, прошедших к определенному моменту времени. Причём, если секундомер показывает, например, 1, то это может обозначать и время ровно 2 минуты, так как 1.(9) = 2.

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

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

В первой строке входного файла находится единственное натуральное число N — количество записей в блокноте тренера (2 ≤ N ≤ 105). В следующей строке находятся сами эти записи — разделённые пробелами целые числа a1, a2, ..., aN (0 ≤ a1 ≤ a2 ≤ ... ≤ aN ≤ 106). Здесь a1 соответствует времени, когда Влад пробежал мимо тренера в первый раз.

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

Выведите два неотрицательных вещественных числа, разделённых пробелом, — минимальное и максимальное возможное количество минут, за которое спортсмен пробегал один круг. Ваш ответ должен отличаться от правильного менее чем на 10 - 3.

Если ответа не существует, то есть Влад не мог бежать с постоянной скоростью так, чтобы записи тренера получились именно такими, в единственной строке выведите «No solution».

Примеры тестов

Входные данные
5
2 3 5 6 8
Выходные данные
1.33333 1.66667
Входные данные
5
1 6 9 14 17
Выходные данные
4 4
Входные данные
3
1 5 6
Выходные данные
No solution
Входные данные
5
1 1 2 3 3
Выходные данные
0.5 0.75

Примечание

Во втором тесте время 4 соответствует показаниям секундомера 1.(9), 6.0, 9.(9), 14.0, 17.(9).

В четвёртом примере минимальное время соответствует показаниям секундомера 1.5, 1.(9), 2.5, 3.0, 3.5, а максимальное — показаниям 1.0, 1.75, 2.5, 3.25, 3.(9).

#111846
Карта метро
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В одном уездном городе Эн было решено построить собственное метро. Все силы города были мобилизованы на выкапывание станций и прокладку подземных путей дедовскими лопатами.

Вся эта история нас бы совершенно не интересовала, если бы однажды в мэрию города не пришло письмо из далёкой страны Емакира. Оказалось, что компания Alpep подозревает администрацию уездного города в нарушении их патента на jMetro и грозится возбудить против города Эн дело. Согласно патенту, jMetro — это метро, в котором:

  • существует ровно одна узловая станция, в которой начинаются все радиальные линии метро, и это единственная станция, принадлежащая хотя бы двум радиальным линиям;
  • существует ровно одна кольцевая линия, все станции которой лежат на радиальных линиях, причём на каждой радиальной линии лежит ровно одна станция кольцевой линии;
  • кольцевая линия не проходит через узловую станцию;
  • кольцевая линия не проходит через конечные станции радиальных линий.

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

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

В первой строке заданы два числа N и M ( 1 ≤ N , M ≤ 2·10 5 ) — количество станций метро и перегонов между ними. Следующие M строк содержат описания перегонов: каждая из них содержит по два числа — номера станций, между которыми есть перегон. По каждому перегону составы могут ездить как в одну, так и в другую сторону. Между любыми двумя станциями существует не более одного перегона. Никакой перегон не соединяет станцию саму с собой.

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

Выведите « YES », если метро уездного города Эн нарушает патент jMetro, и « NO » в противном случае.

Примечание

Первый пример соответствует рисунку из условия.

Примеры
Входные данные
15 19
1 4
4 11
2 10
3 2
8 7
7 6
12 10
15 10
11 2
14 9
6 13
7 9
7 11
2 5
8 3
6 10
3 6
11 3
12 3
Выходные данные
YES
Входные данные
5 4
2 1
2 3
2 5
2 4
Выходные данные
NO
Страница: << 14 15 16 17 18 19 20 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест