Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему.
Для отправки на Codeforces создайте файлы с ответами 01.out, 02.out и так далее до 10.out, а затем сожмите их в архив ZIP.
Ира очень любит программирование и математику. Недавно друзья подарили Ире много новых книг — $$$A$$$ книг по математике и $$$B$$$ книг по программированию. Ира выделила отдельную книжную полку для новых книг, на которую их поместится не более $$$K$$$ штук.
Ира выяснила, что в каждой книге по математике содержится $$$X$$$ новых для неё фактов, а в каждой книге по программированию — $$$Y$$$ новых фактов. Стоит отметить, что все факты уникальны, и никакой факт не встречается в наборе книг дважды. Ира хочет выбрать не более $$$K$$$ книг таким образом, чтобы суммарное количество новых фактов в выбранных книгах было как можно больше.
Помогите Ире посчитать, какое максимальное количество новых фактов она сможет узнать, если оставит на полке не более $$$K$$$ книг.
| Номер теста | Балл | A | B | K | X | Y |
| 1 | 10 | $$$3$$$ | $$$5$$$ | $$$7$$$ | $$$4$$$ | $$$2$$$ |
| 2 | 10 | $$$23$$$ | $$$44$$$ | $$$70$$$ | $$$5$$$ | $$$13$$$ |
| 3 | 10 | $$$239$$$ | $$$0$$$ | $$$137$$$ | $$$7$$$ | $$$19$$$ |
| 4 | 10 | $$$1266$$$ | $$$990$$$ | $$$1127$$$ | $$$2265$$$ | $$$8297$$$ |
| 5 | 10 | $$$1492$$$ | $$$1214$$$ | $$$2735$$$ | $$$7322$$$ | $$$2181$$$ |
| 6 | 10 | $$$1964$$$ | $$$1728$$$ | $$$291$$$ | $$$7683$$$ | $$$2769$$$ |
| 7 | 10 | $$$537004$$$ | $$$662408676616$$$ | $$$398351704499$$$ | $$$672621$$$ | $$$742358$$$ |
| 8 | 10 | $$$79629586150$$$ | $$$851573$$$ | $$$79630127068$$$ | $$$422542$$$ | $$$412282$$$ |
| 9 | 10 | $$$977363980149$$$ | $$$126571152766$$$ | $$$57164417018$$$ | $$$305123$$$ | $$$657661$$$ |
| 10 | 10 | $$$129181369874$$$ | $$$273586061399$$$ | $$$318820081665$$$ | $$$739382$$$ | $$$528351$$$ |
Для каждого теста выведите одно число — максимальное количество новых фактов, которое может получить Ира, если оставит не более $$$K$$$ книг.
Каждый тест оценивается независимо в 10 баллов.
Пусть Ире подарили 5 книг по математике и 3 по программированию. В каждой книге по математике встречается 2 новых факта, а в каждой книге по программированию 3. На полку Ира сможет поставить не более 4-х книг.
В таком случае оптимально взять 3 книги по программированию и 1 по математике, чтобы узнать $$$3 \cdot 3 + 1 \cdot 2 = 11$$$ новых фактов.
Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему.
Для отправки на Codeforces создайте файлы с ответами 01.out, 02.out и так далее до 10.out, а затем сожмите их в архив ZIP.
В Москву на продажу плыл на лодке купец и вёз товар: $$$i$$$ граммов икры и $$$m$$$ граммов мёда. В столице на рынке он может продать икру по цене $$$a$$$ рублей за грамм и мёд по цене $$$b$$$ рублей за грамм. На его пути есть участок суши, где лодку нужно тащить волоком от реки Яуза до реки Клязьма. В этом месте расположен пункт сбора мыта.
Мыт возможно уплатить не только деньгами, но и товаром. Так что купец может оставить в качестве уплаты пошлины на таможне одно из трёх:
- $$$v$$$ рублей
- $$$c$$$ граммов икры
- $$$d$$$ граммов мёда
Посчитайте, какое максимальное количество денег сможет заработать купец при оптимальной стратегии, если у него изначально есть хотя бы $$$v$$$ рублей. Гарантируется, что изначально у купца есть товар (икра и мед) на сумму более, чем $$$v$$$ рублей, то есть $$$i \cdot a + m \cdot b \gt v$$$.
| Номер теста | Баллы | i | m | a | b | v | c | d |
| 1 | 10 | 423 | 228 | 100 | 1000 | 12345 | 87 | 96 |
| 2 | 10 | 93 | 669 | 840 | 551 | 9709 | 80 | 46 |
| 3 | 10 | 917 | 990 | 95 | 48 | 100000 | 234 | 213 |
| 4 | 10 | 116 | 101 | 1 | 853 | 13000 | 120 | 15 |
| 5 | 10 | 799 | 777 | 674 | 77 | 99543 | 150 | 800 |
| 6 | 10 | 913 | 571 | 95 | 116 | 99543 | 1000 | 600 |
| 7 | 10 | 90708140 | 71672649 | 96591121 | 48965030 | 75710881 | 70726629 | 56179162 |
| 8 | 10 | 3578250 | 15019858 | 821035 | 680414804 | 932333366 | 397 | 5300041 |
| 9 | 10 | 79129831 | 66938200 | 31901257 | 714332 | 93143011 | 2450143 | 92 |
| 10 | 10 | 104366 | 96593768 | 2450 | 66714534 | 907050700 | 110000 | 58254686 |
Для каждого теста введите в тестирующую систему единственное число — максимально возможную прибыль купца в рублях.
Каждый тест оценивается независимо в 10 баллов.
Например, если $$$i = 5$$$, $$$m = 10$$$, $$$a = 2$$$, $$$b = 3$$$, $$$v = 7$$$, $$$c = 3$$$, $$$d = 3$$$, то купцу выгоднее всего уплатить мыт икрой и в этом случае его прибыль будет равна $$$4$$$ рубля за оставшуюся икру + $$$30$$$ рублей за мед, то есть суммарно $$$34$$$ рубля.
Если $$$i = 5$$$, $$$m = 10$$$, $$$a = 1$$$, $$$b = 3$$$, $$$v = 10$$$, $$$c = 6$$$, $$$d = 3$$$, то купцу выгоднее всего уплатить мыт мёдом и в этом случае его прибыль будет равна $$$5$$$ рублей за икру + $$$21$$$ рубль за оставшийся мёд, то есть суммарно $$$26$$$ рублей. Обратите внимание, что купец не может уплатить мыт икрой, так как у него недостаточно икры для уплаты мыта икрой.
Если $$$i = 5$$$, $$$m = 10$$$, $$$a = 2$$$, $$$b = 3$$$, $$$v = 7$$$, $$$c = 4$$$, $$$d = 3$$$, то купцу выгоднее всего уплатить мыт деньгами и в этом случае его прибыль будет равна $$$10$$$ рублей за икру + $$$30$$$ рублей за мёд - $$$7$$$ рублей в качестве мыта, то есть суммарно $$$33$$$ рубля.
Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему.
Для отправки на Codeforces создайте файлы с ответами 01.out, 02.out и так далее до 10.out, а затем сожмите их в архив ZIP.
Валерий и Геннадий — друзья, они провели весь год в поисках сокровищ. Всего за год им удалось откопать $$$n$$$ сундуков с сокровищами, в каждом из которых находятся монеты. Валерий и Геннадий хотят поровну разделить найденные монеты из каждого сундука между собой. Но есть проблема — в некоторых сундуках количество монет нечетное и в таком случае разделить их поровну нельзя.
Валерий и Геннадий обратились к Вам за помощью. По их мнению, Вы можете выполнять только следующие операции:
- Пересыпать все монеты из $$$i$$$-го сундука в $$$j$$$-й сундук (после чего $$$i$$$-й сундук становится пустым);
- Если все монеты в сундуке можно разделить между Валерием и Геннадием поровну, то вы отдаете равное количество монет каждому из них;
Помогите Валерию и Геннадию и скажите им максимальное количество монет, которое сможет получить каждый из них.
$$$n$$$ — количество сундуков с золотом. $$$n$$$ целых чисел $$$a_i$$$ обозначают количество монет в сундуках.
| Номер теста | Баллы | n | $$$a_1$$$ | $$$a_2$$$ | $$$a_3$$$ | $$$a_4$$$ | $$$a_5$$$ | $$$a_6$$$ | $$$a_7$$$ | $$$a_8$$$ |
| 1 | 10 | 3 | 1 | 1 | 3 | |||||
| 2 | 10 | 3 | 16 | 4 | 10 | |||||
| 3 | 10 | 4 | 4 | 5 | 10 | 10 | ||||
| 4 | 10 | 4 | 3 | 9 | 5 | 5 | ||||
| 5 | 10 | 4 | 6 | 9 | 7 | 1 | ||||
| 6 | 10 | 5 | 18 | 10 | 10 | 14 | 26 | |||
| 7 | 10 | 5 | 13 | 25 | 15 | 23 | 15 | |||
| 8 | 10 | 6 | 50 | 65 | 95 | 50 | 21 | 4 | ||
| 9 | 10 | 7 | 63 | 2 | 19 | 65 | 18 | 78 | 97 | |
| 10 | 10 | 8 | 24 | 29 | 49 | 6 | 24 | 28 | 99 | 22 |
Выведите одно целое число — максимальное количество монет, которое может получить каждый из друзей.
Каждый тест оценивается независимо в 10 баллов.
Рассмотрим пример $$$n=3$$$, количество монет в сундуках: $$$1, 8, 2$$$. Второй сундук можно разделить поровну между друзьями — каждый получит по четыре монеты.
Также можно разделить третий сундук — каждый получит по одной монете.
Но куда бы мы ни переложили золото из первого сундука, мы не сможем разделить монеты поровну, поэтому ответ 4 + 1 = 5 — монет получит каждый из друзей.
В известном дельфинарии ставят шоу с дельфинами. В этом году организаторы решили добавить в шоу новый номер и удивить зрителей математическими навыками дельфинов. Дельфины умеют складывать числа, но делают это специфическим образом — они склеивают два числа. Например, из чисел $$$12$$$ и $$$3$$$ дельфин может получить число $$$123$$$ путём «сложения».
Тренер готовит дельфина к новому номеру и тренирует его — он показывает ему последовательно $$$n$$$ карточек с числами. Для каждого нового числа дельфин должен определить, можно ли его получить «сложением» каких-то двух карточек, которые тренер показывал ранее. Если число на текущей карточке можно получить «сложением» числа с увиденной ранее карточки два раза подряд, то это тоже учитывалось. Как только дельфин видит число, которое можно получить «сложением» увиденных ранее карточек — он издает специальный звук.
Определите, сколько раз за тренировку дельфин издаст специальный звук.
Первая строка содержит одно целое число $$$n\;(1 \leq n \leq 10^6)$$$ — количество показанных карточек.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2,...,a_n (0 \leq a_i \lt 10^6)$$$ — числа на карточках, записанные без ведущих нулей.
Выведите одно целое число — количество раз, которое дельфин издаст специальный звук.
Каждый тест оценивается независимо в 4 балла.
Если Ваше решение корректно работает при $$$n \leq 200 $$$, оно получит не менее 28 баллов.
71 23 123 11 21 1 2311
3
Обратите внимание, что если мы используем карточку с $$$0$$$, то в результате получается число с ведущим нулем. Например, в последовательности {0, 1, 1} ответ для последней карточки будет отрицательным, т.к. $$$01$$$ не совпадает с $$$1$$$.
Рассмотрим пример из условия: пусть были показаны карточки {1, 23, 123, 11, 21, 1, 2311} именно в таком порядке. Тогда, увидев карточку $$$123$$$, дельфин вспомнил, что ранее уже видел карточки $$$1$$$ и $$$23$$$, числа на которых при последовательной записи дают $$$123$$$. Аналогично, увидев $$$11$$$, дельфин смог представить это число как дважды повторенное число с карточки $$$1$$$, а увидев $$$2311$$$, дельфин смог представить это число как последовательную запись $$$23$$$ и $$$11$$$. Итого, дельфин издал специальный звук $$$3$$$ раза.