Темы --> Информатика --> Алгоритмы --> Перебор
    Комбинаторные структуры(59 задач)
    Перебор с отсечением(22 задач)
    Простые задачи на перебор(43 задач)
    Гамильтонов цикл(2 задач)
---> 4 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников
    6-9 классы(30 задач)
    7-9 классы(25 задач)
    10-11 классы(114 задач)
Страница: 1 Отображать по:
#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
#990
Праздники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Нерабочими называются выходные, а также праздники: 23 февраля, 8 марта и K первых дней года. Праздник попавшие на выходные, переносятся. По заданному K требуется определить максимальное количество подряд идущих нерабочих дней.

Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля (День олимпиады по информатике) и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (суббота и воскресенье), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни.

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

Требуется определить, какое наибольшее количество нерабочих дней может идти подряд.

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

На вход подается единственное число K (1≤K≤50).

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

Требуется вывести единственное число — наибольшее количество нерабочих дней, идущих подряд.

Примеры
Входные данные
2
Выходные данные
4
Входные данные
10
Выходные данные
16
#993
Билетики
  
Заданы числа N и K, затем N чисел 0 или 1. Требуется, чтобы числа, находящиеся на расстоянии K совпадали. Допускается одна ошибка.

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

Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N>=K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки — считается, что одно из чисел может исказиться (то есть 0 заменится на 1, или 1 — на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным.

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

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

В первой строке входного файла записаны числа N и K (1<=N<=50000, 1<=K<=1000, K<=N). Во второй строке записано N чисел, каждое из которых является 0 или 1 — информация, считанная с билета.

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

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

Примеры
Входные данные
6 2
1 0 1 0 1 0
Выходные данные
OK
0
Входные данные
6 2
1 1 1 0 1 0
Выходные данные
OK
2
Входные данные
6 2
1 1 1 0 0 0
Выходные данные
FAIL
#112101
Паровозик из Морошково (BC)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

В первой строке через пробел вводятся два натуральных числа: количество часов в одних сутках ( H ) и минут в одном часу ( M ) на Пандоре ( 1 ≤ H , M ≤ 500 ).

Следующая строка содержит четыре целых числа, описывающих время начала ( H s , M s ) и конца ( H f , M f ) светового дня ( 0 ≤ H s , H f < H ; 0 ≤ M s , M f < M ). При этом либо H s < H f , либо H s = H f и M s < M f (гарантируется, что день начинается раньше, чем заканчивается). Если паровозик проезжает мимо водопада ровно в H s часов M s минут или ровно в H f часов M f минут, то считается, что он проехал мимо водопада днём.

Третья строка содержит одно натуральное число N — количество водопадов, рядом с которыми проезжает паровозик ( 1 ≤ N ≤ 100 000 ).

В следующих N - 1 строках вводятся по 2 целых числа H i и M i , описывающих продолжительность временных интервалов для проезда между соседними водопадами: H 1 , M 1 — время в пути между первым и вторым водопадами, H 2 , M 2 — между вторым и третьим и так далее. Гарантируется, что время, затрачиваемое на дорогу между любыми двумя соседними водопадами, строго положительно, не превосходит одних пандорианских суток и записано корректно: 0 ≤ H i ≤ H , 0 ≤ M i < M .

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

Если составить подходящее расписание невозможно, то в качестве ответа выведите одно слово « Impossible » (без кавычек). Иначе выведите два числа H 0 и M 0 , разделённые пробелом, описывающие любое подходящее время проезда паровозика рядом с первым водопадом.

Примечание

Тесты к этой задаче состоят из четырех групп.

  • Тесты 1–2. Тесты из условия, оцениваемые в ноль баллов.

  • Тесты 3–17. В тестах этой группы H = 24 , M = 60 и N ≤ 1000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • Тесты 18–38. В тестах этой группы H ≤ 80 , M ≤ 100 , N ≤ 100000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.

Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.

Примеры
Входные данные
24 60
8 0 22 0
6
6 0
21 0
19 0
12 0
10 0
Выходные данные
12 0
Входные данные
24 60
8 17 20 10
2
11 59
Выходные данные
Impossible
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест