Воваа

Задача А. Правильное управление (Online)

Задачу добавил: alef

Успешно сдано решений: 6
Предыстория

Много лет тому вперед в одной Очень Большой Корпорации был (хотя, наверное, еще будет) Очень Мудрый Руководитель. Мудрость его столь велика, что никто из его подчиненных даже не пытается постичь его мудрые решения. Раньше, бывало, случалось, что кому и покажется, что какое-то решение недостаточно мудрое, а пройдет день или два, и Очень Мудрый Руководитель примет еще одно мудрое решение. И тут уж всем становится понятно, что предыдущее решение было очень даже мудрое, а если что и казалось - так это лишь потому, что никто и подумать не мог, что будет принято нынешнее.
Очень Большая Корпорация занимается всем, что связано с компьютерами, если выражаться современным языком. Конечно, понятно, что нам трудно представить себе, что эти устройства, производимые с применением йоктотехнологий (йокто = 10^-24), трансформирующиеся силой мысли и обладающие искуственным интеллектом, превосходящим интеллект кое-каких соседей по галактике, еще можно называть компьютерами, но мы все же будем использовать этот и другие современные нам термины, чтобы не отвлекаться каждый раз на рассказ, сколь далеко зашел прогресс.

Задача А. Правильное управление.

Ограничения: время на тест - 2с, память - 256 Мб

Очень Мудрый Руководитель считает, что корпорация должна работать по полному циклу - от добычи необходимых полезных ископаемых до розничной торговли. И решения принимает соответствующие. Например, однажды на совещании он узнал, что за последний месяц уже два раза наблюдались задержки поставок кобальта. Причем первая задержка составляла 38 наносекунд, а вторая, страшно подумать, 2 миллисекунды. Конечно, терпеть такое дальше было совершенно невозможно. И Очень Мудрый Руководитель принял решение приобрести небольшую безжизненную планету, обращающуюся возле звезды Пульхеррима (в созвездии Волопаса). Конечно, можно было бы приобрести шахту возле подводной горы на Земле, но Очень Мудрый Руководитель понимает, что производство постоянно растет, а запасов кобальта в шахте хватит от силы на пару миллионов лет.
В Очень Большой Корпорации дела ведутся таким образом, что ее подразделения обмениваются отчетами между собой. Разумеется, не все со всеми, а те, которые работают над каким-то общим проектом. И пока юристы Очень Большой Корпорации оформляют приобретение в Межгалактической Регистрационной Палате, Очень Мудрый Руководитель задумался, с каким из уже существующих подразделений должно быть связано вновь образованное подразделение по добыче кобальта. С одной стороны, есть Управление полезных ископаемых. С другой - кобальт используется только при производстве печатных плат нечеткой логики, и не будет ли более мудро, чтобы именно с ним новое подразделение обменивалось отчетами?
Очень Мудрый Руководитель поделился этими мыслями со своим Заместителем, на что тот воскликнул:
- Какие проблемы? Почему бы подразделению по добыче кобальта не обмениваться отчетами и с Управлением, и с Производством?
- Так не стоит делать, - спокойно заметил Очень Мудрый Руководитель. - Ведь тогда им придется готовить по два ежедневных отчета, а это лишние затраты человеко-секунд. Если Управлению полезными ископаемыми потребуется такой отчет, оно может запросить его через другие подразделения. А уж подразделению по добыче кобальта и вовсе нет необходимости каждый день получать статистику из Управления.
- Это не такие уж и большие затраты времени! - продолжал настаивать Заместитель. - То же Управление полезных ископаемых обменивается отчетами и с Управлением ресурсами, и с Управлением экологии, и еще с тремя или четырьмя Управлениями. Справляются же!
Очень Мудрый Руководитель промолчал и задумался о том, что, скорее всего, это не единичный случай в Очень Большой Корпорации. Спустя час на его столе лежал отчет о том, какие подразделения корпорации обмениваются между собой отчетами. Да, результат был неутешителен. В корпорации N подразделений. А вот связей между ними Очень Мудрый Руководитель насчитал целых M штук. И он полон решимости оставить минимальное количество связей между подразделениями, но так, чтобы структура осталась целостной и любое подразделение при необходимости могло получить доступ к отчету любого другого подразделения. Более того, поскольку Очень Мудрый Руководитель любит порядок во всем, он хочет, чтобы набор удаляемых связей был лексикографически минимальным.
Это означает, что необходимо удалить M - N + 1 связь между подразделениями. Именно это и нужно сделать Вам.
Гарантируется, что все связи различны и что никакое подразделение не связано непосредственно с самим собой. Также гарантируется, что имеющаяся структура связей обеспечивает возможность обмена отчетами между любыми двумя подразделениями.

Формат входного файла input.txt
Первая строка - два целых числа N и M (3 <= N <= 10^5, 3 <= M <= 10^5)- количество подразделений Очень Большой Корпорации и количество связей между ними.
Каждая из следующих M строк содержит по два целых числа i и j (1 <= i < j <= N), описывающих связь между подразделениями #i и #j.

Формат выходного файла output.txt
Каждая из M - N + 1 строк содержит одну пару вершин, определяющих удаленную связь.
Пары вершин должны быть упорядочены лексикографически, т.е.:
в паре: q < p (номер первой вершины меньше номера второй)
в списке: пара q1 p1 должна быть упомянута раньше, чем пара q2 p2, если либо q1 < q2, либо q1 = q2, но p1 < p2
Если существует несколько ответов, выведите лексикографически минимальный

Пример входного файла - 1:
6 9
1 2
2 5
1 3
2 3
2 4
4 5
3 4
3 6
4 6

Пример выходного файла - 1:
1 2
2 3
2 4
3 4


Пример входного файла - 2:
8 10
1 2
2 4
4 5
2 5
1 3
3 6
6 8
7 8
3 7
6 7

Пример выходного файла - 2:
2 4
3 6
6 7


Пример входного файла - 3:
4 4
1 3
2 3
2 4
3 4


Пример выходного файла - 3:
2 3


Пример входного файла - 4:
5 5
1 5
4 5
2 4
3 4
3 5

Пример выходного файла - 4:
3 4

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



Задача B. Удачный выбор (Online)

Задачу добавил: alef

Успешно сдано решений: 127
Ограничения: время на тест - 2с, память - 256 Мб

Очень Мудрый Руководитель решил посетить магазин компьютерной техники. Он шел вдоль длинной витрины с трансформерпадами новой линейки "ЯСам" (ISome) и, хотя он внешне выглядел спокойным, менеджеры чувствовали, что он чем-то недоволен.
- А почему трансформерпады выставлены именно в таком порядке? - поинтересовался Очень Мудрый Руководитель.
- А мы меняем порядок. Часто. По расцветке корпуса группируем, по набору интерфейсов...
- И как это отражается на продажах?
- Почти никак. Покупатели все равно проходят вдоль всей витрины, чтобы увидеть все модели, а потом обращаются к консультанту.
- Это неправильно, - заметил Очень Мудрый Руководитель. - Ведь мы задумывали ЯСам как очень простое устройство, с которым легко может работать даже маленький ребенок. Когда человек выбирает устройство с помощью консультанта, он не будет считать его простым. Нужно, чтобы он выбрал его сам. И был доволен своим выбором.
И тут Очень Мудрый Руководитель дал очень мудрый совет распорядителю торгового зала: поставить трансформерпады так, чтобы подтолкнуть покупателя к самостоятельному выбору. Если у трансформерпада цены L слева стоит трансформерпад, стоящий S, а справа - трансформерпад, стоящий F денежных знаков, при этом L < S и L < F, то покупатель почти наверняка выберет тот, что стоит L, не обращаясь к консультанту. И, без сомнения, уйдет довольным.
Распорядитель торгового зала некоторое время пребывал в благоговейном восторге от столь простого и столь мудрого совета, а затем велел срочно переставить товар так, чтобы в ряду устройств обязательно встречалась хотя бы одна тройка трансформерпадов, в которой средний стоил бы дешевле, чем его соседи слева и справа. И действительно, уже к концу дня стало ясно, что такие "средние" трансформерпады продаются намного лучше.
По заданной последовательности ценников Вы должны определить, какой трансформерпад лучше всего продается. Если в последовательности существует несколько троек, удовлетворяющих описанным выше требованиям, выведите цену наиболее дешевого из "средних". Гарантируется, что хотя бы одна такая тройка в последовательности есть.

Формат входного файла input.txt
Первая строка - целое число N (3 <= N <= 600000) - количество трансформерпадов на витрине
Вторая строка - N натуральных чисел через пробел, каждое число не превосходит 100000, - цены трансформерпадов в порядке их расположения на витрине

Формат выходного файла output.txt
Первая строка - целое число - цена трансформерпада, который лучше всего продается

Пример входного файла - 1
3
25020 10870 13040

Пример выходного файла - 1
10870

Пример входного файла - 2
5
10870 25020 13040 19870 14999

Пример выходного файла - 2
13040



Задача C. Важное поручение (Online)

Задачу добавил: alef

Успешно сдано решений: 17
Ограничения: время на тест - 2с, память - 256 Мб

У Очень Мудрого Руководителя есть дочка, которая учится на компьютерной специальности в местном университете. Надо сказать, что эта замечательная девушка, прекрасная, как цветок раффлезии, с волосами цвета террас Памуккале и глазами цвета топаза, обладает живостью ума и всегда стремится к чему-то новому, не обращая внимание на мелкие преграды. Вот и сейчас, слушая курс "Операционные системы древних", она захотела попробовать поработать на таком же ноутбуке, на котором приходилось работать людям в конце XX века. Но где же найти такую древность, да еще и работающую?
Сначала помощники Очень Мудрого Руководителя предложили изготовить похожий корпус, но поместить туда современную начинку. Но Очень Мудрый Руководитель, наделенный даром предвидения, догадался, что в курсе могут рассказать и об аппаратной базе древних ноутбуков, и понял, какое разочарование ждет его любимую дочь, когда она (а он в этом не сомневался) решит посмотреть, как устроен ноутбук внутри.
На экстренном совещании руководителей всех подразделений начальник отдела разработки интерфейса текстового ввода Василий неосторожно (для себя) вздохнул: "Ну, такое только по музеям искать!"
Помощники Очень Мудрого Руководителя тут же ухватились за эту мысль, и назначили Василия отвественным за поиски. Отложив менее важные дела, Василий вскоре выяснил, что на планете возле Сириуса можно найти ноутбук, в котором из начинки осталась только материнская плата, а также без аккумулятора и блока питания; в звездной системе Антареса можно отыскать самые разные компоненты - и оперативную память, и видеокарту, и звуковую карту - но как раз корпуса у них нет. Что же касается питания ноутбука, то Василию посоветовали обратиться к одному отшельнику, который живет на планете возле Капеллы.
Очень Мудрый Руководитель тут же решил отправить Василия в командировку и обратился к Управлению логистики, чтобы они составили наиболее экономный маршрут. Начальная и конечная точки этого маршрута совпадают - это Земля. Василию надо (в любом порядке) побывать на всех трех планетах. Ваша задача - определить, как это можно сделать быстрее всего. Заметим, что в этом путешествии Василий может несколько раз посетить Землю, но на всех остальных планетах он должен оказаться ровно один раз (во избежание проблем с таможней).

Формат входного файла input.txt
Первая строка содержит три целых числа через пробел - время, за которое Василий может добраться от Земли до Сириуса, Антареса и Капеллы соответственно
Вторая строка содержит три целых числа через пробел - время, за которое Василий может добраться от Сириуса до Земли, Антареса и Капеллы соответственно
Третья строка содержит три целых числа через пробел - время, за которое Василий может добраться от Антареса до Земли, Сириуса и Капеллы соответственно
Четвертая строка содержит три целых числа через пробел - время, за которое Василий может добраться от Капеллы до Земли, Сириуса и Антареса соответственно
Все числа положительны и не превосходят 10^6

Формат выходного файла output.txt
Первая строка - целое число, минимальное время, за которое Василий может привезти на Землю все составляющие ноутбука.

Пример входного файла - 1:
18 17 21
14 40 10
12 33 17
15 34 24

Пример выходного файла - 1:
64


Пример входного файла - 2:
18 11 17
15 82 38
27 13 77
25 14 39

Пример выходного файла - 2:
81



Задача E. Сложная зависимость (Online)

Задачу добавил: alef

Успешно сдано решений: 21
Ограничения: время на тест - 2с, память - 256 Мб

Сотрудник музея Теодор, встретивший Василия, рассказал ему, что в музейном хранилище, расположенном за городом, есть несколько корпусов и материнских плат, и лучше всего поехать туда и выбрать наиболее сохранившиеся экземпляры. Для путешествия за город он предложил Василию пересесть на некое громыхающее и даже слегка дымящее транспортное средство на колесах, работавшее, как показалось Василию, на реактивной тяге. Теодор заметил в глазах Василия удивление и пояснил, что это лучший транспорт для того места, куда они направляются.
Всю поездку Василий мог думать только о том, когда же она закончится. За городом была каменистая пустыня, и этот "мобиль" (Теодор называл его более длинным словом, но Василию запомнилось только окончание) трясло на каждой кочке. Теодор как будто не замечал этого.
Наконец, они подъехали к холмам, и Теодор выскочил из "мобиля".
- Выходи! Это наше хранилище! Очень надежное место! - голос Теодора перекрывался шумом двигателя.
Василий выбрался наружу, и они отправились в хранилище. Внутри большого холма действительно было хорошо оборудованное помещение. Довольно быстро они определились с выбором материнской платы и подходящего корпуса, и вышли наружу.
Пока Теодор запирал замки, Василий рассматривал скудную растительность, покрывавшую холм. На низеньком кустарнике он заметил пару красивых щебечущих пташек и решил сделать снимок (тут надо пояснить, что снимок - это точная копия не только объекта и окружающей среды, но и звуков, и запахов... полный эффект присутствия). Беспрестанно тарахтящий агрегат на колесах этому мешал, и Василий, рассудив, что выключаться двигатель должен довольно просто, нашел-таки и повернул ключ в замке зажигания. Тишина показалась ему полным блаженством. Но спустя секунду она была нарушена криком Теодора "Опять заглох! Ну что же такое!". Теодор подбежал к Василию, схватил его за руку и потащил к странной конструкции, расположенной почти рядом с дверью:
- Сейчас местные полезут!
И действительно, в десятке метров от них возникло человекоподобное существо, небыстрым шагом направлявшееся к двери. Теодор потянул за рукоять странной конструкции, и в голову существа полетел шар, состоящий из какого-то гелеобразного вещества. Попав в "мишень", шар растекся, и существо, всем своим видом выражая огорчение, развернулось и отправилось в другую сторону.
- Мы их "зомби" зовем. Вообще их тут два вида, других мы "колдуны" называем. Ни с теми, ни с другими лучше не связываться. Хранилище нам от колдунов досталось и орудие борьбы - тоже, - пояснил Теодор и рассмеялся. - Швыряемся в них арбузами с помощью этой дынепульты! Зомби реагируют на запах, поэтому мы никогда движок не выключаем - выхлопные газы их не радуют. Но уж когда глохнет - тут надо быстро реагировать. Если до тебя доберутся - просто сжуют. Причем есть вероятность, что дынепульту сжуют тоже. Так что ездить всегда надо вдвоем - если что, один отстреливается, второй "мобиль" заводит. Так что придется тебе стать на время оператором дынепульты, пока я разберусь, почему этот тарантас заглох.
Теодор пояснил, что дынепульта готова выпускать очередной снаряд один раз в 3 секунды. Снаряд попадает в ближайшего зомби и дезориентирует его. От места, где вылезают зомби, до дынепульты, десять с половиной шагов. Снаряд пролетает это расстояние мгновенно.
Зомби появляются в целые моменты времени и за одну единицу времени совершают один шаг. По заданному расписанию появления зомби определите, который из зомби первым доберется до дынепульты.

Формат входного файла input.txt
Первая строка - целое число N (0 <= N <= 10^5) - количество зомби
Вторая строка - целые числа 0 <= A1 < A2 < ... < AN <= 10^9 через пробел - моменты появления зомби.

Формат выходного файла output.txt
Первая строка - целое число J - номер зомби, который первым доберется до дынепульты. Если ни один зомби не доберется до дынепульты, выведите -1.

Пример входного файла - 1:
11
0 1 2 3 4 5 6 7 8 9 10

Пример выходного файла - 1:
7


Пример входного файла - 2:
11
0 2 4 6 8 10 12 14 16 18 20

Пример выходного файла - 2:
-1


Пример входного файла - 3:
20
100 101 102 103 104 105 151 152 154 155 157 158 160 161 163 164 166 167 169 170

Пример выходного файла - 3:
14


Пример входного файла - 4:
30
10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97

Пример выходного файла - 4:
-1

Добавлено через 39 секунд
ребят помогите срочно))

@Exoo

вот так задачи, целые рассказы =)

0