Страница: << 2 3 4 5 6 7 8 >> Отображать по:
#3869
Праздничный ужин
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Рядом с офисом компании, в которой работает программист Джон, открылось новое кафе. Директор компании решил провести там новогодний ужин.

Меню праздничного новогоднего ужина в кафе состоит из k типов блюд. Для каждого типа блюда есть несколько вариантов на выбор. Всего есть a1 вариантов для первого типа блюда, a2 вариантов для второго типа блюда, и так далее, ak вариантов для k-го типа блюда. Всего, таким образом, предлагается a1×a2×…×ak различных заказов праздничного ужина.

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

Каждый сотрудник компании запомнил, сколько возможных заказов ужина ему было предложено. Выяснилось, что директору, который выбирал первым, было предложено на выбор n1 = a1×a2×…×ak заказов. Тому, кто выбирал вторым, досталось лишь n2 < n1 заказов, поскольку один из вариантов одного из типов блюд уже не был доступен, и так далее. Джону, который выбирал последним, был предложен выбор лишь из nm заказов. Джон заинтересовался, а какое количество вариантов каждого типа блюд было на выбор у директора компании.

Требуется написать программу, которая по заданным числам k, m и n1, n2, …, nm выяснит, какое количество вариантов каждого типа блюд изначально предлагалось на выбор.

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

Первая строка входного файла содержит два целых числа k и m, разделенных ровно одним пробелом (1 ≤ k ≤ 20, 2 ≤ m ≤ 100). Вторая строка содержит m чисел: n1, n2, …, nm (для всех i от 1 до m выполняется неравенство 1 ≤ ni ≤ 109).

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

Выходной файл должен содержать k чисел: a1, a2, …, ak. Если возможных вариантов решения поставленной задачи несколько, требуется вывести любой. Соседние числа должны быть разделены ровно одним пробелом. Гарантируется, что хотя бы одно решение существует.

Примечание

События в примере могли развиваться, например, следующим образом.

Исходно количество заказов ужина было равно 3×2×2=12. Директор, выбрав свой заказ, указал блюдо первого типа, поэтому второму сотруднику осталось лишь два варианта блюда первого типа. Количество заказов для него сократилось до 2×2×2 = 8. Он также указал на свое блюдо первого типа, и Джон уже мог выбирать лишь из 1×2×2 = 4 заказов ужина.

Примеры
Входные данные
3 3
12 8 4
Выходные данные
3 2 2
#3880
Переливание
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

На досуге вы любите почитать сборники занимательных задач по математике. Недавно вы наткнулись в одном из таких сборников на следующую задачу:

Есть бесконечный резервуар с водой и два пустых сосуда объёмом 5 и 12 литров. Можно наливать воду из резервуара в любой сосуд до его заполнения, переливать воду из —одного сосуда в другой до заполнения второго или опустошения первого (смотря что будет раньше) и выливать воду из сосуда на землю до полного опустошения сосуда. Как таким образом можно отмерить 3 литра?

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

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

Во входном файле находятся три целых числа — \(V_1\), \(V_2\) и \(V\) — объёмы двух сосудов и объем воды, который нужно отмерить. Гарантируется, что \(1\leq V_1,V_2\leq 32767\) и \(0\leq V\leq \max(V_1,V_2)\).

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

В первую строку выходного файла выведите одно число — количество действий в вашем решении. Далее выведите соответствующее количество строк, описывающих действия в вашем решении. Для каждого действия выведите два числа:

  • если это действие — переливание из одного сосуда в другой, то первое число должно быть номером сосуда, откуда надо переливать воду, а второе — номером сосуда, куда переливать;
  • если это действие — набор воды из резервуара, то первое число должно быть нулём, а второе  — номером сосуда, куда наливать;
  • если это действие — выливание воды “на землю”, то первое число должно быть номером сосуда, а второе — нулём.

После выполнения всех операций хотя бы в одном сосуде должна находиться вода в объёме \(V\).

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

Если решений не существует, выведите одно число -1.

Примеры
Входные данные
5 12 3
Выходные данные
10
0 1
1 2
2 1
1 2
0 1
1 0
0 1
1 2
0 1
1 2
#3888
Автомат со сдачей
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда пассажиру надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100-рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же пассажир бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим пассажирам.

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

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

В первой строке входного файла находится одно натуральное число \(N\) — количество покупок в автомате, которые были совершены в ходе испытания (\(1\leq N\leq 50\,000\)). Во второй строке находятся \(N\) натуральных чисел, каждое из которых равно номиналу монеты или купюры, которую использовал очередной покупатель для оплаты; каждый номинал может принимать одно из четырёх значений: 5, 10, 50 или 100.

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

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

Примечание

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

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

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

Примеры
Входные данные
3
10 5 100
Выходные данные
19
Входные данные
3
5 5 10
Выходные данные
0
Входные данные
4
50 5 5 5
Выходные данные
9
#3893
Переливание духов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

... но нужен ли на самом деле кому-нибудь 6\(1\over7\)-пунктовый шрифт, который на три четверти — шрифт Baskerville, и на четверть — Helvetica?

Дональд Э. Кнут. Идея Мета-фонта1

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

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

Считайте, что Оля не пролила ни одной капли, а также что она тщательно встряхивала флаконы после каждого переливания. Учтите, что в маминых флаконах порой не видно, есть ли там жидкость, и потому Оля иногда могла пытаться переливать духи из пустого флакона (в результате, естественно, ничего не переливалось). Вы можете также считать, что после каждого переливания в каждом флаконе каждый тип духов либо полностью отсутствует, либо содержится в объеме не меньшем чем \(10^{-10}\).

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

На первой строке входного файла находятся два числа \(N\) и \(M\) — количество флаконов и число типов маминых любимых духов соответственно (\(2 \leq N \leq 100\); \(1 \leq M \leq 100\)). Далее следуют \(N\) строк, на \(i\)-ой из которых находятся два числа — тип \(L_i\) и объем \(V_i\) духов, находившихся изначально в \(i\)-ом флаконе (\(1\leq L_i \leq M\); \(0 \leq V_i \leq 1000\)). Возможно, что в нескольких флаконах находились духи одного и того же типа; возможно, что какого-то типа вообще не было на полке.

Далее во входном файле следует строка с числом \(K\) — количеством совершённых переливаний (\(1 \leq K \leq 1000\)). За ней следуют \(K\) строк, на \(k\)-ой из которых находятся три числа \(S_k\), \(T_k\) и \(A_k\) — номера флаконов, откуда и куда переливала Оля при \(k\)-ом переливании, и количество перелитой жидкости (в процентах от количества жидкости в \(S_k\)-ом флаконе перед переливанием). Гарантируется, что \(1\leq S_k,T_k\leq N\), что \(S_k\neq T_k\), и что \(0\leq A_k\leq 100\). Все числа во входном файле целые.

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

В выходной файл выведите \(M\) чисел — процентное содержание всех видов духов (от первого до \(M\)-ого) в первом флаконе после последнего переливания. Выводите результат с точностью не меньше двух знаков после запятой. Гарантируется, что после последнего переливания первый флакон оказался непустым.

Примечание

1... but does anybody really need a 6\(1\over7\)-point font that is one fourth of the way between Baskerville and Helvetica? — Donald E. Knuth, The Concept of a Meta-Font

Примеры
Входные данные
3 2
1 100
2 200
1 500
2
3 2 20
2 1 50
Выходные данные
60.00 40.00
#111473
Кубики
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Мальчик Вася очень любит строить башни из кубиков. К сожалению, во время последней игры он увлёкся и потерял все кубики, кроме двух. Однако Вася не стал унывать и придумал новое развлечение. Заметив, что на каждой грани кубиков написано по одной цифре, он научился выкладывать двузначные числа из оставшихся игрушек. Вскоре мальчику стало интересно, сколько идущих подряд чисел, начиная с единицы, он сможет выложить с помощью двух кубиков. Помогите Васе найти ответ — такое максимальное число K, что все числа от 1 до K включительно можно получить, используя два оставшихся кубика.

Поскольку в игре используются оба кубика, числа, меньшие 10, Вася выкладывает с ведущими нулями (так, единицу можно получить, выбрав грань первого кубика с цифрой 0 и второго — с цифрой 1). Помните, что Вася умный мальчик: он знает, что перевернутый кубик с цифрой 6 позволяет получить цифру 9, и наоборот.

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

На вход подаются две строки, каждая из которых содержит 6 цифр, написанных на гранях соответствующего кубика.

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

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

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

Входные данные
0 1 2 3 4 5
0 6 7 8 9 2
Выходные данные
10
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест