Страница: 1 Отображать по:
#545
Две стены
  
Источники: [ Командные олимпиады, ВКОШП, 2001, Задача A ]
Задано описание кирпичей, которое состоит из цвета, а также длины кирпича. Из кирпичей построена прямоугольная стена, причем каждый ряд имеет свой цвет. Требуется разделить кирпичи на 2 группы, чтобы из каждой группы можно было построить прямоугольную стену, содержащую ряды тех же цветов, что и исходная.

У Пети есть набор из \(N\) кирпичиков. Каждый кирпичик полностью окрашен в один из \(K\) цветов, \(i\)-й кирпичик имеет размер 1×1×\(L_i\). Петя знает, что он может построить из всех кирпичиков прямоугольную стену толщиной 1 и высотой \(K\), причем первый горизонтальный слой кирпичиков в стене будет первого цвета, второй - второго и т. д. Теперь Петя хочет узнать, может ли он из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите ему выяснить это.

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

В первой строке входных данных задаются числа \(N\) и \(K\) (1 <= \(N\) <= 5000, 1 <= \(K\) <= 100). Следующие \(N\) строк содержат описание Петиных кирпичиков: сначала длина Li, затем номер цвета \(C_i\) (1 <= \(L_i\) <= 100, 1 <= \(C_i\) <= \(K\)). Известно, что у Пети не более 50 кирпичиков каждого цвета.

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

Выведите в первой строке YES, если Петя сможет построить из всех своих кирпичиков две прямоугольные стены высоты \(K\), \(j\)-й слой кирпичиков в каждой из которых будет \(j\)-го цвета, и NO в противном случае. В случае положительного ответа, выведите во второй строке в произвольном порядке номера кирпичиков, из которых следует построить первую стену (кирпичики нумеруются в том порядке, в котором они заданы во входных данных, начиная с 1). Если решений несколько, можно выдать любое из них.

Примеры
Входные данные
3 1
1 1
2 1
3 1
Выходные данные
YES
1
Входные данные
4 2
1 1
1 2
2 1
2 2
Выходные данные
YES
1 2
Входные данные
2 2
1 1
1 2
Выходные данные
NO
#625
Копилка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Задан вес \(E\) пустой копилки и вес \(F\) копилки с монетами. В копилке могут находиться монеты \(N\) видов, для каждого вида известна ценность \(P_i\) и вес \(W_i\) одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Ограничения

\(1 \le E\le F\le 10000\), \(1 \le N \le 500\), \(1\le P_i\le 50000\), \(1\le W_i \le 10000\), все числа целые.

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

В первой строке находятся числа \(E\) и \(F\), во второй - число \(N\), в следующих \(N\) строках - по два числа, \(P_i\) и \(W_i\).

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

Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".

Примеры

Ввод Вывод 
1000 1100
2
1 1
5 2
 
100 250
 
1000 1010
2
6 3
2 2
 
10 16
 
1000 2000
1
10 3
 
This is impossible.
#675
Гомер Симпсон
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Обеденный перерыв Гомера Симпсона составляет \(T\) миллисекунд. Один гамбургер Гомер съедает за \(N\) миллисекунд, один чизбургер - за \(M\). Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая \(T\). При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: \(1 \le M, N, T \le 1 000 000\), все числа целые.

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

В первой строке находятся три числа - \(M\), \(N\) и \(T\), разделённые пробелами.

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

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

Примеры
Входные данные
1 2 1000
Выходные данные
1000
Входные данные
2 1 1000
Выходные данные
1000
#904
Локальная сеть
  

 

Максимальное время работы на одном тесте:

4 секунды

Максимальный объем используемой памяти:

64 мегабайта

Алексей работает системным администратором в локальной домовой сети. Его сеть соединяет множество квартир и располагается в нескольких зданиях.

Сеть постоянно расширяется и Алексею поручено проложить новый участок сети. У него есть схема, на которой указаны все возможные соединения между парами квартир и для каждого соединения он знает длину провода, необходимого для его прокладки. Его цель состоит в том, чтобы все квартиры были подключены к сети (возможно через другие квартиры).

Компания, в которой работает Алексей покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене P5 и P6 рублей за метр. При этом в наличии имеется только Q5 метров кабеля пятой категории и Q6 метров кабеля шестой категории.

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

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

В первой строке входного файла содержится число N — количество квартир, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10 000).

Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.

Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10 000) .

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

Если все квартиры можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N-1 строк должны содержать описание соединений, представленных двумя числами каждое: Ai и Ci, где Ai — номер соединения в списке возможных соединений (от 1 до M), а Ci задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.

Если все квартиры соединить невозможно выведите слово Impossible.

Пример

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

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

6 7

1 2 7

2 6 5

1 4 8

2 3 5

3 4 5

5 6 6

3 5 3

2 11 3 100

65

1 5

2 6

4 6

5 6

7 5

 

#911
Дизайнерский лифт
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дизайн-студия Артемия Индюкова получила заказ на разработку очень пафосного лифта для нового небоскреба. За работу взялся сам Артемий, отличающейся, кстати, редкой неадекватностью. У него есть идея-фикс: для управления лифтом достаточно четырех кнопок. Кнопки должны быть следующие:
- Поднятся на A этажей вверх
- Поднятся на B этажей вверх
- Поднятся на C этажей вверх
- Спустится на первый этаж
Изначально лифт находится на первом этаже. Пассажир лифта использует первые три кнопки чтобы попасть на тот этаж, на который он хочет. Если пассажир пытается подняться вверх на A, B или C этажей, а такого этажа в здании не существует (т.е. пассажир хочет подняться выше N-го, последнего этажа), то лифт никуда не едет.
Заказчики проекта оказались с юмором и вместе с отказом от футуристичного дизайна решили оценить адекватность Артемия по шкале от 1 до N. Оценка адеватности равна количеству этажей, на которые можно попасть с первого с помощью такого лифта. Помогите им в этом.

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

Первая строка содержит число N – высоту небоскреба (1 <= N <= 500 000).

Вторая строка содержит три числа A, B и C, задающие параметры кнопок (1 <= A, B, C <= 100 000).

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

Выведите единственное число — оценку адекватности Артемия Индюкова.

Примеры
Входные данные
15
4 7 9
Выходные данные
9
#992
Маскарад
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Есть N магазинов, для каждого из них задана цена метра, количество метров необходимых для "оптовой" покупки, цена метра при покупке оптом, а также имеющееся в магазине количество ткани. Необходимо купить L метров за минимальную цену (можно покупать в различных магазинах кусками).

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит "Мы с радостью продадим Вам метр ткани за Pi бурлей, однако если Вы купите не менее Ri метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в Qi бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более Fi метров ткани.

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

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

В первой строке входного файла записаны два целых числа N и L (1≤N≤100, 0≤L≤100). В каждой из последующих N строк находится описание магазина номер i — 4 целых числа Pi, Ri, Qi, Fi (1≤Qi≤Pi≤1000, 1≤Ri≤100, 0≤Fi≤100).

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

Первая строка выходного файла должна содержать единственное число — минимальное необходимое количество бурлей.

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

Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число -1.

Примеры
Входные данные
2 14
7 9 6 10
7 8 6 10
Выходные данные
88
10 4
Входные данные
1 20
1 1 1 1
Выходные данные
-1
#1118
0-1 Рюкзак
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второе строке вводятся N натуральных чисел mi, не превышающих 100.

Во третьей строке вводятся N натуральных чисел сi, не превышающих 100.

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

Выведите наибольшую стоимость рюкзака.

Примеры
Входные данные
1 597
18
16
Выходные данные
16
Входные данные
2 27
30 35
3 9
Выходные данные
0
#1119
0-1 рюкзак: наибольший вес
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке вводятся N натуральных чисел mi, не превышающих 100.

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

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

Примеры
Входные данные
2 3195
38 41
Выходные данные
79
#1120
0-1 рюкзак: точный вес
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Можно ли набрать вес в точности M?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке вводятся N натуральных чисел mi, не превышающих 100.

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

Выведите YES или NO.

Примеры
Входные данные
1 5968
18
Выходные данные
NO
Входные данные
4 102
50 52 54 2
Выходные данные
YES
#1121
0-1 рюкзак: минимум предметов
  

Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второе строке вводятся N натуральных чисел mi, не превышающих 100.

 

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

Выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

Примеры
Входные данные
1 5968
18
Выходные данные
0
#1122
Гирьки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан набор гирь массой m­1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

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

В первой строке вводится натуральное число N, не превышающее 100.

Во второе строке вводятся N натуральных чисел mi, не превышающих 100.

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

Выведите YES или NO.

Примеры
Входные данные
1
17
Выходные данные
NO
Входные данные
2
19 19
Выходные данные
YES
#1225
Склад
  

На роботизированном складе имеется N отсеков, в которые робот может размещать грузы. Отсек с номером i имеет вместимость ci. Груз с номером i имеет размер si, поступает на склад в момент времени ai и забирается со склада в момент времени di.

Когда груз с номером i поступает на склад, робот сначала пытается найти отсек, в котором достаточно свободного места для размещения этого груза. Свободное место в пустом отсеке совпадает с его вместимостью. Если в отсеке с вместимостью c находится несколько грузов с суммарным размером d, то свободное место в этом отсеке равно c – d.

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

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

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

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

Первая строка содержит два целых числа: N — количество отсеков, и M — количество грузов (1 ≤ N ≤ 10, 1 ≤ M ≤100). Вторая строка содержит N целых чисел ci, определяющих вместимости отсеков (1 ≤ ci ≤ 109). Последующие M строк описывают грузы: каждый груз описывается тремя целыми числами: своим размером si, временем поступления на склад ai и временем, когда его забирают со склада di (1 ≤ si ≤ 109, 1 ≤ ai < di ≤ 1000, все времена во входном файле различны, грузы упорядочены по возрастанию времени поступления на склад). Все числа в строках разделены пробелом.

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

Выведите последовательность действий робота в том порядке, в котором они выполняются. Следуйте формату, приведенному в примере.

Возможны следующие сообщения:

put cargo X to cell Y — положить груз с номером X в отсек с номером Y;

move cargo X from cell Y to cell Z — переложить груз с номером X из отсека с номером Y в отсек с номером Z;

take cargo X from cell Y — достать груз с номером X из отсека с номером Y.

cargo X cannot be stored — если груз с номером X разместить невозможно.

Примеры
Входные данные
1 2
3
2 1 2
4 3 4
Выходные данные
put cargo 1 to cell 1
take cargo 1 from cell 1
cargo 2 cannot be stored
#1277
Несчастливые номера
  

Обычно автобусный билет с номером, состоящим из 6 цифр, считается счастливым, если сумма первых трех цифр его номера была равна сумме трех последних. Школьник Вася очень любил получать счастливые билеты, однако это случалось не так часто. Поэтому для себя он изменил определение счастливого билета. Счастливым он считал тот номер, сумма некоторых цифр которого равнялась сумме оставшихся цифр. В его представлении билет с номером 561743 счастливый, так как 5 + 1 + 4 + 3 = 6 + 7.

Вася вырос, но по привычке в номерах различных документов пытается найти признаки счастливого номера ☺. Для этого он расширил свое определение счастливого номера на n-значные номера лицевых счетов и других документов, состоящих из цифр от 0 до k (1 ≤ k ≤ 9). Номер документа он называет счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся. Остальные номера для него несчастливые. К сожалению, несмотря на расширенное понимание “счастья”, несчастливых номеров остается еще много...

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

Входной файл unlucky.in содержит описание нескольких видов номеров. Каждый вид номеров определяется значениями n и k. Для данного входного файла вы должны создать соответствующий ему выходной файл и отправить его на проверку жюри.

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

Входной файл содержит несколько пар значений n и k, каждая пара записана в отдельной строке.

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

Для каждой пары значений n и k входного файла выведите в соответствующей строке выходного файла искомое количество несчастливых билетов или 0, если такое число вам получить не удалось. Количество строк во входном и выходном файлах должно совпадать.

Примечание

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

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

  • Presentation Error — если файл не соответствует формату вывода. В этом случае файл не принимается на проверку.
  • Accepted — если файл формату вывода соответствует. В этом случае файл принимается на проверку. Проверка правильности ответов в выходном файле осуществляется только после окончания тура.
Содержание файла unlucky.in:
4 1
7 1
3 2
6 2
22 2
7 9
8 7
9 6
8 8
12 9
20 9
20 3
17 5
16 7
15 9
19 5
26 9
100 3
99 4
50 5
#1374
Снова ка-штаны
  
Требуется найти набор, остаток от деления которого на размер рюкзака минимален.

В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K1, K2, …, KN штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:

  • на каждой лапе была надета хотя бы одна штанина (гарантируется, что это всегда возможно),
  • количество штанин, надетых на самую «утепленную» лапу, должно как можно меньше отличаться от количества штанин, надетых на самую легко одетую лапу (когда количество штанов, одетых на разные лапы, сильно отличается, Зверь испытывает дискомфорт),
  • в отличие от задачи B Петя не обязан надеть на Зверя все имеющиеся штаны — какие-то из них можно оставить дома.

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

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

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

Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M). Сумма всех Ki не меньше, чем M.

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

Выведите M строк, в i-ой строке должно быть выведено количество штанин, надетых на i-ю лапу. Если искомых ответов несколько, то выведите любой из них.

Комментарии к примерам тестов

1. Первые штаны надеты на лапу 1;
вторые штаны не используем;
третьи штаны надеты на лапы 2, 3 и 4.
Таким образом, на всех лапах по 1 штанине.

2. Первые штаны надеты на лапы 1, 2 и 3;
вторые штаны надеты на лапы 1 и 4.
Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.

Примеры
Входные данные
4 3
1 2 3
Выходные данные
1
1
1
1
Входные данные
4 2
3 2
Выходные данные
2
1
1
1
#1623
Пицца
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит B рублей.

Вы уже выбрали товар, стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1\), ..., \(d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ.

Как потратить меньше всего денег и получить на дом уже выбранный товар в \(A\) рублей?

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

Сначала вводятся числа \(A\), \(B\), \(C\), \(N\), а затем \(N\) чисел \(d_1\), ..., \(d_N\).

Все числа целые, 1 ≤ \(A\) ≤ 1000, 1 ≤ \(B\) ≤ 1000, 1 ≤ \(C\) ≤ 1000, 0 ≤ \(N\) ≤ 1000, 1 ≤ \(d_i\) ≤ 1 000 000.

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

Выведите сначала суммарное количество денег, которое придется потратить. Если при этом вы планируете сделать дополнительный заказ c расчетом на бесплатную доставку, то далее выведите количество этих товаров и их номера в возрастающем порядке. Если же Вы будете оплачивать доставку сами, то далее выведите одно число –1 (минус один).

Примеры
Входные данные
10 17 25
5
2 7 5 3 7
Выходные данные
26
3 1 2 5
#1633
Пицца
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит \(B\) рублей. Вы уже выбрали товара стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1, ..., d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ. Как потратить меньше всего денег и получить на дом уже выбранный товар стоимостью \(A\) рублей?

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

Вводятся сначала числа \(A, B, C, N,\) а затем \(N\) чисел \(d_1, ..., d_N\). Все числа целые, \(1 \le A \le 1000, 1 \le B ≤ 1000, 1 \le C \le 1000, 0 \le N \le 1000, 1 \le di \le 1 000 000\).

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

Выведите единственное число – суммарное количество денег, которое придется потратить.

Примечание
В первом примере экономнее всего докупить 1, 2 и 5 товары. Во втором ничего докупать не надо, ведь доставка уже стала бесплатной. В третьем дешевле всего заплатить за доставку самому.
Примеры
Входные данные
10 17 25
5
2 7 5 3 7
Выходные данные
26
Входные данные
100 1 50
5
5 2 4 3 1
Выходные данные
100
Входные данные
10 14 25
5
2 7 5 3 7
Выходные данные
24
#1982
Петино путешествие
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

С этими мыслями Петя решил прогуляться до продуктового магазина – купить в дорогу немного еды. Из всего ассортимента ему подходило M видов товара (количество товаров каждого вида неограниченно), стоимость i-го равна ai рублей bi копеек. И тут его осенило. Если покупать товары в правильной последовательности, то он довольно быстро сможет скопить так нужные ему N копеечных монет!

Процесс покупки в магазине устроен следующим образом. Петя может заказать любой набор из подходящих ему товаров (каждого товара Петя может взять сколько угодно единиц). После чего он платит за них и получает сдачу минимальным числом купюр и монет (любых монет и купюр в кассе также с избытком). Это означает, например, что если ему должны сдать 11 рублей и 98 копеек сдачи, то он получит купюру в 10 рублей, монеты в 1 рубль, 50 копеек, 4 монеты в 10 копеек, одну монету в 5 копеек и три копеечных монеты. При этом он волен вносить любую сумму (лишь бы она была не меньше требуемой для оплаты) и платить любым набором купюр и монет, имеющихся у него в распоряжении.

После этого Петя может ещё раз подойти к кассе, сделать заказ, расплатиться имеющимися наличными (можно использовать и полученные до этого со сдачей) и так далее сколько угодно раз.

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

Комментарий для нероссийских участников олимпиады.

В России используются монеты и купюры достоинством 1, 5, 10, 50 копеек и 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. 1 рубль равен 100 копейкам.

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

Сначала вводятся целые числа N и M (0 ≤ N ≤ 108, 0 ≤ M ≤ 100) — количество городов, которые собирается посетить Петя, и количество подходящих ему видов товара. Далее идут M пар чисел ai, bi, обозначающих стоимость товара соответствующего типа (0 ≤ ai ≤ 100, 0 ≤ bi ≤ 99). Стоимость товара всегда больше нуля.

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

Если требуемое количество копеечных монет получить невозможно, выведите –1. Иначе выведите минимальную сумму, которую должен потратить Петя на покупку товаров, чтобы получить N однокопеечных монет.  Сумма должна быть выведена как два целых числа, задающих рубли и копейки (второе число обязано быть от 0 до 99).

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

Примеры
Входные данные
3 1
0 2
Выходные данные
0 2
Входные данные
4 2
1 2
0 4
Выходные данные
0 16
Входные данные
1 3
0 1
0 4
0 6
Выходные данные
0 1
#3088
Золотые слитки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Даны N золотых слитков известных масс. Определите, какую наибольшую массу золота можно унести, если вместимость рюкзака не превышает S.

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

Программа получает на вход целое число S — вместимость рюкзака, не превосходящее 10000 и количество слитков N, не превосходящее 300. Далее следует N целых неотрицательных чисел, не превосходящих 100000 — веса слитков.

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

Программа должна вывести единственное целое число — максимально возможных вес золота, который поместится в данный рюкзак.

Примеры
Входные данные
10 3
5 7 4
Выходные данные
9
#3089
Рюкзак
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

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

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке вводятся N натуральных чисел mi, не превышающих 100.

Во третьей строке вводятся N натуральных чисел сi, не превышающих 100.

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

Выведите одно целое число: наибольшую возможную стоимость рюкзака.

Примеры
Входные данные
4 6
2 4 1 2
7 2 5 1
Выходные данные
13
#3090
Рюкзак с восстановлением ответа (C)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно.

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

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке вводятся N натуральных чисел mi, не превышающих 100.

В третьей строке вводятся N натуральных чисел сi, не превышающих 100.

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

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

Примеры
Входные данные
4 6
2 4 1 2
7 2 5 1
Выходные данные
1
3
4
#3091
Минимум предметов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

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

Первая строка входных данных содержит натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке находится N натуральных чисел mi, не превышающих 100.

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

Выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

Примеры
Входные данные
4 6
4 2 3 1
Выходные данные
2
#3092
Гирьки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан набор гирек массой m1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

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

Первая строка входных данных содержит натуральное число N, не превышающее 100. Далее идет N натуральных чисел mi, не превышающих 100.

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

Программа должна вывести YES, если гирьки можно разложить на две кучки равной массы или NO в противном случае.

Примеры
Входные данные
4
4 2 3 1
Выходные данные
YES
#3093
Гирьки: кучки одного размера
  

Дан набор гирек массой m1, …, mN. Разделите этот набор на две кучки равной массы, содержащие равное число гирек.

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

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

Первая строка входных данных содержит натуральное число N, не превышающее 100. Далее идет N натуральных чисел mi, не превышающих 100.

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

Необходимо вывести в первой строчке номера гирек (числа от 1 до N), входящие в первую кучку, во второй строчке — номера гирек во второй кучке. Если задача не имеет решения, выведите строку No solution.

Примеры
Входные данные
4
4 2 3 1
Выходные данные
2 3 
1 4
#3094
Гирьки: три кучки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Дан набор гирек массой m1, …, mN. Можно ли их разложить на три кучки равной массы?

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

Первая строка входных данных содержит натуральное число N, не превышающее 60. Далее идет N натуральных чисел mi, не превышающих 60.

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

Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

Примеры
Входные данные
5
4 2 3 1 5
Выходные данные
5 
1 4 
2 3
#3095
Гирьки: четыре кучки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан набор гирек массой m1, …, mN. Можно ли их разделить на четыре кучки равной массы?

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

Первая строка входных данных содержит натуральное число N, не превышающее 14. Далее идет N натуральных чисел mi, не превышающих 100.

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

Программа должна вывести номера гирек для каждого из наборов в четыре строки или строчку No solution, если решения не существует.

Примеры
Входные данные
8
10 20 30 40 50 60 70 80
Выходные данные
1 8 
2 7 
3 6 
4 5
#3096
Гирьки: три кучки одного размера
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан набор гирек массой m1, …, mN. Разделите его на три кучки равной масссы, содержащие равное число гирек.

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

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

Первая строка входных данных содержит натуральное число N, не превышающее 18. Далее идет N натуральных чисел mi, не превышающих 100.

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

Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

Примеры
Входные данные
6
10 20 30 40 50 60
Выходные данные
1 6 
2 5 
3 4
#3097
Сдача - 1
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.

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

Программа получает на вход сумму S. Далее идет число N затем P1, P2, ..., PN. Далее идет число M, затем Q1, Q2, ..., QM. Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавцу и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номинаkа покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдачу. Номиналы банкнот разделяйте пробелом.

Если они не могут рассчитаться, выведите строку Impossible.

Примеры
Входные данные
10
3
3 9 14
2
6 2
Выходные данные
-2 +9 +3
Входные данные
100
3
74 35 8
2
19 6
Выходные данные
Impossible
#3098
Сдача - 2
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.

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

Программа получает на вход сумму S. Далее идет число N затем P1, P2, ..., PN. Далее идет число M, затем Q1, Q2, ..., QM.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если продавец сможет рассчитаться с покупателем, выведите наименьшее количество банкнот, которое придется отдать продавцу на сдачу.

Если они не могут рассчитаться, выведите число -1.

Примеры
Входные данные
10
4
3 3 9 3
2
6 2
Выходные данные
1
Входные данные
100
3
74 35 8
2
19 6
Выходные данные
-1
#3143
Перевес багажа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

У Пети в чемодане лежат N предметов, каждый предмет имеет свой вес Wi килограмм и ценность Ai рублей, причем оказалось так, что для любого предмета выполняется следующее неравенство:

W1 + W2 + … + Wi-1 ≤ Wi

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

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

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

В первой строке задаётся количество предметов в багаже у Пети N (1 ≤ N ≤ 50) и какой у Пети перевес чемодана в килограммах M (1 ≤ M ≤ 1018). Во второй строке задаются N целых неотрицательных чисел – вес всех вещей Wi, сумма чисел не превышает 1018. В третьей строке заданы N целых неотрицательных чисел – ценность всех вещей Ai , все числа не превышают 109.

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

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

Ввод
Вывод
4 15
5 10 15 30
1 5 3 6
3
3 2
1 2 4
7 6 5
5
#111256
Простая арифметика
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Задана последовательность цифр. Определите, можно ли расставить между некоторыми из них знаки "+" и "-", так чтобы получилось заданное число \(M\), но никакие промежуточные вычисления не превосходили по модулю \(10000\).

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

Входные данные содержат две строки: в первой строке - натуральное число \(M\)≤\(20000\), во второй строке - последовательность цифр. Длина входной последовательности не превышает \(200\) символов.

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

Выведите одно слово YES или NO в зависимости от того, есть решение у задачи или нет.

Примеры
Входные данные
2009
20009
Выходные данные
YES
Входные данные
10
000000050049000
Выходные данные
YES
#111735
Делимость
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Рассмотрим произвольную последовательность целых чисел. Между числами можно расставить знаки арифметических операций + или – , и таким образом получать некоторые выражения, которые принимают различные значения. Например, если взять последовательность: 17, 5,  - 21, 15, то можно получить восемь различных выражений:

Назовем последовательность делящейся на натуральное K, если + и – могут быть расставлены так, что итоговое значение выражения будет делиться на K. В приведенном примере последовательность делится на 7  (17 + 5 +  - 21 - 15 =  - 14), но не делится на 5.

17

+

5

+

-21

+

15

=

16

17

+

5

+

-21

-

15

=

-14

17

+

5

-

-21

+

15

=

58

17

+

5

-

-21

-

15

=

28

17

-

5

+

-21

+

15

=

6

17

-

5

+

-21

-

15

=

-24

17

-

5

-

-21

+

15

=

48

17

-

5

-

-21

-

15

=

18

Ваша задача — написать программу, определяющую делимость последовательности на целое число.

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

Первая строка содержит два натуральных числа N и K(1 ≤ N ≤ 10000, 2 ≤ K ≤ 100), разделенные пробелом. Вторая строка состоит из N целых чисел, разделенных пробелами. Все числа не превосходят 10000 по модулю.

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

Выведите в выходной файл "Divisible", если данная последовательность делится на K или "Not divisible", в противном случае.

Примеры
Входные данные
4 7
17 5 -21 15
Выходные данные
Divisible
Входные данные
4 5
17 5 -21 15
Выходные данные
Not divisible
#112551
Призы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Андрей Сергеевич работает воспитателем в детском саду. Недавно он придумал новую веселую игру, для участия в которой все дети разбились на n команд. В качестве призов для участников игры Андрей Сергеевич подготовил d конфет.

По итогам игры оказалось, что в команде, занявшей i -е место, ровно x i участников.

Теперь перед Андреем Сергеевичем стоит непростая задача: надо распределить конфеты. При этом должны выполняться следующие условия:

  • Все участники одной команды должны получить поровну конфет: пусть участники команды, занявшей i -е место получат по a i конфет;
  • Каждый ребенок должен получить хотя бы одну конфету: a i > 0 ;
  • Участники команды, занявшей более высокое место, должны получить больше конфет: если i < j , то a i > a j
  • Все конфеты должны быть распределены: a 1 x 1 + a 2 x 2 + ... a nx n = d
Помогите Андрею Сергеевичу раздать детям конфеты, или сообщите,что это невозможно.

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

Первая строка содержит два целых числа n и d ( 1 ≤ n ≤ 100 , 1 ≤ d ≤ 10 6 ). Вторая строка содержит n целых чисел x 1 , ..., x n ( 1 ≤ x i ≤ 100 для всех i от 1 до n ).

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

Если разделить конфеты возможно, то в первой строке выведите YES , а во второй выведите n целых чисел: a 1 , a 2 , ..., a n . Если разделить конфеты указанным способом нельзя, выведите NO .

Примеры
Входные данные
2 100
2 1
Выходные данные
YES
49 2
Входные данные
2 6
2 1
Выходные данные
NO
#112561
Весы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4 n - 1 грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

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

В единственной строке содержаться 2 целых числа m и n (1 ≤ n , m ≤ 10 9 ) .

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

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

Примеры
Входные данные
1 5
Выходные данные
1
Входные данные
5 7
Выходные данные
4
#113467
Распродажа
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c i , время его завоза в магазин a i и время его вывоза из магазина b i .

У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m j , время s j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.

Помогите Иннокентию определить, какие из его планов можно выполнить.

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

В первой строке входных данных содержится число N — общее количество товаров в магазине ( 1 ≤ N ≤ 500 ). Далее содержатся описания товаров, каждый товар описывается тремя целыми числами c i , a i , b i , обозначающими стоимость товара, время его завоза и время его вывоза из магазина ( 1 ≤ c i ≤ 1 000 , 1 ≤ a i < b i ≤ 10 9 ).

Далее содержится число M — количество планов Иннокентия ( 1 ≤ M ≤ 500 000 ). Каждый план описывается тремя целыми числами m j , k j , s j , обозначающими время прихода Иннокентия в магазин, сумму денег, которую он готов потратить в этом плане и длительность его пребывания в магазине ( 1 ≤ m j ≤ 10 9 , 1 ≤ k j ≤ 100 000 , 0 ≤ s j ≤ 10 9 ).

Помните, что это только планы, т. е. ситуация в магазине не меняется вне зависимости от того, может ли Иннокентий осуществить план или нет.

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

Для каждого плана в отдельной строке выведите « YES », если Иннокентий может его осуществить, и « NO » в противном случае.

Примечание

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

  • Тест 1. Тест из условия, оценивается в ноль баллов.
  • Тесты 2–7. В тестах этой группы M ≤ 10 , a i , b i , m j , s j ≤ 20 000 , k j ≤ 1 000 . Эта группа оценивается в 30 баллов.
  • Тесты 8–11. В тестах этой группы N ≤ 200 , M ≤ 200 , k j ≤ 5 000 . Эта группа оценивается в 30 баллов.
  • Тесты 12–23. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.

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