Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 471 472 473 474 475 476 477 >> Отображать по:
#112125
Коррозия металла
  
ограничение по времени на тест
0.25 second;
ограничение по памяти на тест
256 megabytes

Для хранения двух агрессивных жидкостей \(A\) и \(B\) используется емкость с многослойной перегородкой, которая изготавливается из имеющихся \(N\) листов. Для каждого листа \(i\) (\(i\) = 1, ..., \(N\)) известно время его растворения жидкостью \(A\) - \(a_i\) и жидкостью \(B\) - \(b_i\). Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.

В первой строке входного файла записано число \(N\) (1 ≤ \(N\) ≤ 256). В каждой из последующих N строк содержатся два положительных вещественных числа \(a_i\) и \(b_i\), разделенные пробелом.

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

В первую строку выходного файла записать время растворения перегородки с точностью до 3 цифр после десятичной точки. В следующую строку файла записать номера листов в порядке их расположения от жидкости A к жидкости B, разделяя числа пробелами.

Примеры
Входные данные
4
1 2
1 2
0.5 1.5
7 3.5
Выходные данные
6.00000000
4 2 1 3
#112128
Аппликатура
  
ограничение по времени на тест
0.25 second;
ограничение по памяти на тест
256 megabytes

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

Пронумеруем пальцы пианиста слева направо натуральными числами от 1 до P, клавиши инструмента также пронумеруем слева направо натуральными числами от 1 до K. Тогда запись звуков мелодии можно представить в виде последовательности N номеров клавиш, которые следует нажимать для ее исполнения, где N — длина мелодии.

Пусть для каждой пары пальцев с номерами i и j заданы целые числа aij и bij, такие, что если палец i нажимает клавишу X, то следующей клавишей пальцем j может быть нажата лишь клавиша из диапазона [X + aij, X + bij]. Этот набор чисел aij, bij, 1 ≤ i ≤ P, 1 ≤ j ≤ P, зависит от особенностей пианиста и его исполнительской техники. Заметим, что не каждая мелодия может быть сыграна конкретным пианистом при указанных выше ограничениях.

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

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

В первой строке входного файла содержится число P — количество пальцев у пианиста (1 ≤ P ≤ 20). Во второй строке записано число K  —  количество клавиш у инструмента (1 ≤ K ≤ 10000). В третьей строке указаны целые числа a11b11a12b12...a1Pb1Pa21b21a22b22...a2Pb2P...aP1bP1aP2bP2...aPPbPP, разделенные пробелами ( - K ≤ aij ≤ bij ≤ K). В четвертой строке находится число N — длина мелодии (1 ≤ N ≤ 1000). Пятая строка содержит N чисел X1X2...XN — последовательность разделенных пробелами номеров клавиш для исполнения мелодии.

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

В первой строке выходного файла должно содержаться либо число L — количество перекладываний пальцев в оптимальной аппликатуре, либо число  - 1 при невозможности сыграть мелодию. Вторая строка при наличии решения должна содержать N чисел Y1...YN — последовательность разделенных пробелами номеров пальцев при исполнении мелодии.

Примеры
Входные данные
3
10
0 0 -2 -2 -5 1 2 3 8 10 0 1 2 10 -2 -2 -1 -1
9
4 5 7 7 7 6 8 7 5
Выходные данные
3
1 3 1 1 3 3 1 3 2
#112335
Автомат с игрушками
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes
В развлекательном центре \(Е\)-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть n узлов, которые пронумерованы числами от 1 до \(n\). При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая — направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок — в левую.

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

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

Панкрату понравилась игрушка, которая находится в узле с номером \(v\).

Требуется написать программу, которая определяет, сколько монет должен бросить в автомат Панкрат, чтобы получить игрушку из узла \(v\).

Формат входного файла

В первой строке входного файла задано число \(n\) — количество узлов в лабиринте. В последующих n строках заданы описания всех узлов, в \(k\)-й из этих строк описан узел с номером \(k\).

Описание k-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k\) < \(a_k\) <= \(n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k\) = \(u_k\) = 0. Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k\) < \(b_k\) <= \(n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k\) = \(w_k\) = 0.

В последней строке задано целое число \(v\) (1 <= \(v\) <= \(n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

Гарантируется, что во все узлы, кроме первого, входит ровно одна трубка

Формат выходного файла

Выходной файл должен содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле \(v\). Если получить выбранную игрушку невозможно, выведите число −1.

Система оценки

Данная задача содержит две подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 1

1 <= \(n\) <= 100

1 <= \(u_k\); \(w_k\) <= 300

Подзадача оценивается в 50 баллов.

Подзадача 2

1 <= \(n\) <= \(10^5\)

1 <= \(u_k\); \(w_k\) <= \(10^9\)

Подзадача оценивается в 50 баллов.

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

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

Примеры
Входные данные
7
2 1 3 2
0 0 6 3
4 1 5 1
0 0 0 0
7 2 0 0
0 0 0 0
0 0 0 0
5
Выходные данные
3
Входные данные
4
0 0 2 1
4 1 3 1
0 0 0 0
0 0 0 0
3
Выходные данные
-1
#112445
Звёздные ламы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

Да пребудет с тобой лама!


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

«Каждому штурмовику по ламе — лучшему другу элитного воина Галактической Империи!».

Поскольку Дарт Сидиус и Дарт Вейдер фактически уже помирают со скуки на Звезде Смерти, они взялись самостоятельно разработать костюмы для всех лам. На каждом костюме должно быть натуральное число цветных ленточек, причём, так как штурмовики хотят подчеркнуть свою уникальность, не должно быть трёх костюмов с одинаковым числом цветных ленточек. Также после создания костюма с каким-то количеством ленточек, ни Дарт Сидиус, ни Дарт Вейдер не будут создавать костюм с бо́льшим числом ленточек, считая это излишним расточительством.

Дарт Сидиус и Дарт Вейдер создают костюмы по очереди, начинает, естественно, Император. Дарт Сидиус утверждает, что сможет создавать костюмы для лам вечно, однако у Энакина возникло подозрение, что рано или поздно кто-то из них не сможет сделать очередной костюм. Он обратился к вам с тем, чтобы вы помогли ему добиться того, что последний костюм будет сделан именно им.

Формат взаимодействия с тестирующей системой

При каждом ходе Императора на вход подаётся одно целое число — количество ленточек на новом костюме ламы. Гарантируется, что все ходы корректны и что число ленточек на первом косюме не превосходит \(10^5\).

Для каждого хода Дарта Вейдера выведите одно число — количество ленточек на костюме ламы, который должен сделать Дарт Вейдер.
Если Император не может сделать ход, он сходит с ума, а на вход подаётся строка «I am your lama!», после чего ваша программа должна завершиться.

Пример
Ввод
10
4
1
I am your lama!
Вывод
7
2
1
Примечания

Контесты помимо неотъемлемой развлекательной части должны также иметь и познавательную часть. Поэтому сообщаем вам, что Дарта Вейдера зовут Энакин Скайуокер, он был взят в ученики джедаем Оби-Ваном Кеноби, который впоследствии и погиб от рук перешедшего на тёмную силу бывшего рыцаря-джедая Энакина. Сделал будущий Дарт Вейдер это под влиянием Тёмного владыки ситхов, будущего Императора Первой Галактической Империи Палпатина, которого также зовут Дарт Сидиус.
Составители контеста приносят свои извинения за возможные спойлеры, содержащиеся в условии задачи.

В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

#112446
Бороться и искать, найти и не сдаваться!
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
128 megabytes

Не превращай людей в героев, Джон, героев нет.
А даже будь они — я из другой оперы

Шерлок


Джим Мориарти решил сыграть с Шерлоком Холмсом в небольшую игру. Накануне он похитил миссис Хадсон и заточил её в одной из лабораторий военной базы «Баскервиль», на которой проводят сверхсекретные эксперименты.

Все лаборатории «Баскервиля» пронумерованы числами от \(1\) до \(N\), причём в каждой лаборатории, номер которой меньше, чем номер лаборатории, в которой заключена миссис Хадсон, злодей-консультант оставил записку, в которой написано «Green beard» («Зелёная борода»). А в каждой лаборатории, номер которой больше, чем номер лаборатории, в которой заключена миссис Хадсон, он оставил записку, в которой написано «A woman» («Та женщина»).

К сожалению, дедукция, внутренняя интуиция и даже везение покинули Шерлока Холмса после совершённого им преступления, поэтому он обратился к вам за помощью. Он просит вас отыскать миссис Хадсон как можно быстрее. Помогите ему, проверив не более 60-ти лабораторий, иначе Лестрейд прибудет на базу «Баскервиль» раньше, чем Шерлок спасёт миссис Хадсон.

Формат взаимодействия с тестирующей системой

При запуске решения на вход подаётся единственное целое число \(N\) — количество лабораторий на военной базе «Баскервиль» \((1 \leq N \leq 10^{18})\).

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

Иначе вам удалось найти миссис Хадсон, и вам будет введена строка «Mrs. Hudson is here». После этого ваша программа должна завершиться.

Примеры
Ввод
1
Mrs. Hudson is here
Вывод
1
Ввод
100
A woman
Green beard
A woman
Mrs. Hudson is here
Вывод
100
1
99
2
Примечания

В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

Страница: << 471 472 473 474 475 476 477 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест