WWW.BOOK.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные ресурсы
 


«XI Городская олимпиада школьников по информатике им. В. Д. Лелюха Нижний Новгород, 31 января 2015 г. Задача 1. 23 февраля Имя ...»

XI Городская олимпиада школьников по информатике им. В. Д. Лелюха

Нижний Новгород, 31 января 2015 г.

Задача 1. 23 февраля

Имя входного файла: 23feb.in

Имя выходного файла: 23feb.out

Ограничение по времени: 0.5 секунд

Ограничение по памяти: 256 мегабайт

Сегодня 23 Февраля, поэтому Малыш решил устроить парад своих солдатиков. Он уже достал их

из коробки, расположил в одну линию и теперь хочет построить их по росту в порядке невозрастания

слева направо.

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

Малышу совершенно не обязательно построить солдатиков за минимально возможное количество перестановок, но ему обязательно нужно это сделать не более чем за 23 000 перестановок, иначе он не успеет до сна.

Помогите Малышу справиться с этой ответственной задачей.

Формат входных данных В первой строке входного файла указано целое число N (2 N 100) — количество солдатиков у Малыша. Во второй строке через пробел указаны N положительных целых чисел, каждое из которых не превосходит 2000. K-ое число во второй строке задает рост K-ого солдатика в исходном построении. Солдатики нумеруются числами от 1 до N слева направо.

Формат выходных данных Если расположить солдатиков требуемым образом невозможно, то в выходной файл требуется вывести единственное слово «NO» без кавычек.

Если построение осуществимо, то в первой строке выведите единственное слово «YES» без кавычек, а во второй строке выведите требуемое количество действий K (0 K 23 000). Далее нужно вывести K строк, каждая из которых должна содержать два числа X и Y, означающих, что Малышу нужно поменять местами солдатиков, стоящих сейчас на X-ом и Y -ом местах.

Если есть несколько решений, выведите любое. Обратите внимание, что минимизировать число действий не требуется, главное — чтобы их было не больше 23 000.

Примеры 23feb.in 23feb.out 10 YES 2 NO Примечание Решения, работающие при N 8, будут набирать 50 баллов.

Страница 1 из 8 XI Городская олимпиада школьников по информатике им. В. Д. Лелюха Нижний Новгород, 31 января 2015 г.

Задача 2. Оптимальное расписание Имя входного файла: buses.

in Имя выходного файла: buses.out Ограничение по времени: 0.5 секунд Ограничение по памяти: 256 мегабайт Как вы помните, ваш друг работает главным диспетчером в одной из компаний, владеющей сетью маршрутных такси. Недавно директор поставил перед ним задачу оптимизировать расписание маршруток на некотором маршруте.

Экономический отдел предоставил вашему другу прогноз пассажиропотока на следующие n часов. Теперь необходимо составить расписание маршруток, а именно для каждого часа определить, выйдет маршрутка на линию в этот час или нет. Известно, что если в i-ый час на маршрут выйдет маршрутка, то она принесет прибыль ai рублей, при этом ai может быть как положительным, так и нулевым или отрицательным. Также, в связи с ограниченным размером автопарка и в соответствии с требованиями департамента транспорта, маршрутки должны работать примерно 2/3 всего времени. Более формально, для любого i (1 i n) величина twork tskip b= должна лежать в пределах от k до k включительно. Здесь twork — количество часов до i-ого включительно, в которые маршрутки выходили на линию, а tskip — количество часов до i-ого включительно, в которые маршрутки не выходили на линию.

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





Формат входных данных

В первой строке входных данных находится количество часов n, на которые необходимо составить расписание, и число k (1 n 105, 1 k 10). На второй строке находятся n чисел:

прогнозируемая прибыль для каждого часа ai (|ai | 109 ).

Все числа во входном файле целые.

Формат выходных данных Выведите одно число — максимальную суммарную прибыль в рублях.

Примеры buses.in buses.out 2 1 3 4 -5 2 1 3 4 -5 5 5 -10 5 5

–  –  –

Примечание В первом примере оптимально выпустить маршрутки на линию в первый, третий и четвертый часы, таким образом, прибыль составит 2 + 3 + 4 = 9 рублей.

Величины twork, tskip и b после каждого часа представлены в таблице:

–  –  –

Решение, в котором маршрутки выходят на линию в первый, второй, третий и четвертый часы, неправильно, потому что в таком случае уже после третьего часа twork = 3, tskip = 0, а значит, b = 1.5, что недопустимо по условию задачи.

Однако, для второго примера это решение допустимо, так как максимальное значение b равно 2, что удовлетворяет ограничению. Это решение и является оптимальным.

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

Решения, правильно работающие при n 20, оцениваются не менее чем в 20 баллов.

Решения, правильно работающие при n 1000, оцениваются не менее чем в 50 баллов.

Страница 3 из 8 XI Городская олимпиада школьников по информатике им. В. Д. Лелюха Нижний Новгород, 31 января 2015 г.

Задача 3. Часы с кукушкой Имя входного файла: cuckoo.

in Имя выходного файла: cuckoo.out Ограничение по времени: 0.5 секунд Ограничение по памяти: 64 мегабайта У Васи на кухне висят часы с кукушкой. Часы устроены так: в каждый ровный час кукушка кукует столько раз, сколько сейчас часов (от 1 до 12), например, ровно в 7:00 кукушка кукует 7 раз.

Кроме того, в 30 минут каждого часа (в 0:30, 1:30, 2:30 и т.д.) кукушка кукует ровно один раз.

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

Считайте, что кукушка кукует очень быстро. Например, даже в 11:00 она успевает прокуковать 11 раз быстрее, чем за одну минуту, т.е. к моменту 11:01 кукушка уже закончила куковать.

Формат входных данных Входные данные содержат четыре целых числа H1, M1, H2 и M2 — время ухода (H1 часов M1 минут) и время возвращения (H2 часов M2 минут) Васи. Гарантируется, что 0 H1,2 12 и что 0 M1,2 60. Гарантируется, что момент ухода Васи следует до момента его возвращения (т.е. или H1 H2, или H1 = H2, но M1 M2 ), и что кукушка не кукует ни в момент ухода, ни в момент возвращения (т.е. что M1,2 = 0 и M1,2 = 30).

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

Формат выходных данных Выведите одно число — сколько раз кукушка куковала за время отсутствия Васи.

Примеры cuckoo.in cuckoo.out Примечание В первом примере кукушка кукует один раз — в момент времени 2:30.

Во втором примере кукушка кукует три раза в момент времени 3:00, один раз в момент времени 3:30, и еще четыре раза в момент времени 4:00 — итого 8 раз.

В третьем примере кукушка не куковала ни разу.

–  –  –

Задача 4. Угадайка Имя входного файла: module.

in Имя выходного файла: module.out Ограничение по времени: 0.5 секунд Ограничение по памяти: 256 мегабайт Вася прошел на уроке математики в школе операцию деления с остатком. Чтобы закрепить пройденный материал, он решил потренироваться в выполнении этого действия. Придя домой, Вася попросил маму назвать N произвольных натуральных чисел Xi (1 i N ), не превосходящих

109. Затем он придумал некоторое натуральное число M, не превосходящее наибольшего из Xi, и вычислил остатки Yi от деления всех чисел на него.

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

Помогите Васе найти все возможные значения M, удовлетворяющие всем соотношениям.

Несмотря на то, что и Вася, и его друг Леша — прилежные и умные ученики, они могли ошибиться в вычислениях, и ни одного подходящего M может не существовать.

Формат входных данных В первой строке находится одно натуральное число N — количество чисел, с которыми Вася проводил операцию деления (1 N 1000).

Далее следуют N строк, в i-ой из которых находятся два целых числа Xi, Yi, разделенные пробелом (1 Xi 109, 0 Yi Xi ).

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

Во второй строке должны находиться K чисел, разделенные пробелами — все возможные значения M. Числа можно выводить в произвольном порядке.

Примеры module.in module.out Примечание В первом примере существует единственное число M = 5. Остаток от деления 9 на 5 есть 4, а остаток от деления 6 на 5 есть 1.

Во втором примере в качестве M можно взять 3 и 6.

Решения, работающие при Xi 200 000, будут набирать 30 баллов.

–  –  –

Задача 6. Площадь Пажитнова Имя входного файла: tetris.

in Имя выходного файла: tetris.out Ограничение по времени: 0.5 секунд Ограничение по памяти: 256 мегабайт В прошлом году всемирно известной игре Тетрис исполнилось 30 лет. В Берляндии очень любят Тетрис, и поэтому решили назвать одну из городских площадей в столице в честь изобретателя игры, Алексея Леонидовича Пажитнова. Дизайн площади, разумеется, должен напоминать всем о Тетрисе. Поэтому она будет замощена плитками в виде фигурок игры.

Как известно, фигурки Тетриса состоят из четырех «клеток». Берляндский завод тротуарной плитки может выпускать плитку в виде любых фигурок Тетриса. Размер каждой «клетки» такой плитки составляет 1 1 метр. Все возможные фигурки Тетриса представлены на рисунке ниже.

Площадь Пажитнова имеет вид прямоугольника длиной N и шириной M метров. Для упрощения замощения она вся расчерчена на «клетки» размером 1 1 метр, то есть представляет собой сетку. При замощении «клетки» плитки должны совпадать с «клетками» площади. Плитки можно использовать только целиком, они не должны перекрываться или выступать за пределы площади, но их можно поворачивать на углы, кратные 90. Разумеется, плитки должны покрывать площадь полностью. Размерами промежутков между плитками, покрывающими соседние «клетки», можно пренебречь.

Например, площадь длиной 3 и шириной 4 метра можно покрыть тремя плитками, как показано на рисунке ниже.

Напишите программу, которая поможет берляндцам найти подходящее покрытие.

–  –  –

Формат входных данных В первой и единственной строке записаны два натуральных числа N и M (1 N, M 100), разделенные пробелом — длина и ширина площади соответственно.

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

Если замощение существует, то выведите его, начиная со второй строки. А именно, считайте, что плитки, используемые в замощении, занумерованы натуральными числами от 1 до K. Выведите N строк по M чисел, разделенных пробелами, в каждой. Эти числа должны соответствовать номерам плиток, покрывающим соответствующие «клетки» площади.

Если существует несколько замощений с минимальным количеством плиток, то выведите любое из них.

Примеры tetris.in tetris.out 33 -1 Примечание Первый пример соответствует картинке из условия.




Похожие работы:

«Раздел 1. Общие положения Настоящий Коллективный договор (далее — Договор) является правовым актом, регулирующим социально-трудовые отношения в федеральном государственном автономном образовательном учреждении высшего образования "Балтийский федеральный университет имени Иммануила...»

«1. Сначала научитесь играть по правилам, потом придумывайте свои На танцевальные вечера трудящиеся должны приходить в легкой одежде и обуви. Танцевать в рабочей и спортивной одежде запрещается. Танцевать в искаженном виде запрещается. Танцующий должен исполнять танец прав...»

«"Сысуев, Бондарь, Храпуцкий" юридическая фирма/адвокатское бюро Юридическая фирма "Сысуев, Бондарь, Храпуцкий" Сысуев Тимур Бондарь Александр Храпуцкий Александр Валерьевич Юрьевич Федорович О компании "Сысуев, Бондарь, Храпуцкий" юридическая...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФИЛОЛОГИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра связей с общественностью ПРАВОВОЕ ОБЕСПЕЧЕНИЕ СВЯЗЕЙ С ОБЩЕСТВЕННОСТЬЮ ПРОГРАММА И УЧЕБНО-МЕТОДИЧЕСКИЕ УКАЗ...»

«Воробьва Елена Александровна ПРАВОВОЕ РЕГУЛИРОВАНИЕ СДЕЛОК, ТРЕБУЮЩИХ СОГЛАСИЯ, ПО ГРАЖДАНСКОМУ ЗАКОНОДАТЕЛЬСТВУ РОССИЙСКОЙ ФЕДЕРАЦИИ Специальность 12.00.03 гражданское право; предпринимательское право; семейное право; международное частное право Диссертация на соискание ученой степен...»

«СРОЧНЫЙ ВКЛАД С ПРАВОМ УВЕЛИЧЕНИЯ И УМЕНЬШЕНИЯ СУММЫ Вид вклада: срочный Минимальная сумма вклада: 1 000 000 драмов РА, 5 000 долларов США, 5 000 евро, 400 000 российских рублей При данном виде вклада изымаемая сумма не может превышать 30 (Тридцать) процентов от с...»

«189 ЗЕЛИНСКАЯ Н.А. д.ю.н., профессор кафедры международного права и международных отношений Национального университета "Одесская национальная юридическая академия", ДРЁМИНАВОЛОК Н.В. главный научный сотрудник НИИ Национальной академии прокуратуры Украины, LL.M, к.ю.н. КОНЦЕПЦИЯ ПРЕСТУПЛЕНИЙ ПО ОБЩЕМУ МЕЖДУНАРОДНОМУ ПРАВУ В КОНТЕКСТЕ ПРОБЛЕ...»

«Православие и современность. Электронная библиотека. БИБЛИЯ. ВЕТХИЙ ЗАВЕТ. ЛЕВИТ. Глава 1 И воззвал Господь к Моисею и сказал ему из скинии собрания, говоря: 2 объяви сынам Израил...»

«ОКАЗАНИЕ БЕСПЛАТНОЙ ЮРИДИЧЕСКОЙ ПОМОЩИ Консультация практикующего юриста Проблемы применения норм о подозрительных сделках по признаку неравноценного встречного исполнения обязательств Д ействующий Федеральный закон от 26 октября 2002 г. № 127-ФЗ "...»

«I. ОБЩИЕ ПОЛОЖЕНИЯ Актуальность: Анестезиологи-реаниматологи, работая в условиях моральной и юридической ответственности за жизнь пациента, относятся к группе самого высокого медикоюридического риска. В рутинной практике им приходится ставить ди...»








 
2017 www.book.lib-i.ru - «Бесплатная электронная библиотека - электронные ресурсы»

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