Кризисный бизнес
(Время: 1 сек. Память: 16 Мб Сложность: 20%)
Петр Васильевич Колошин никогда не был пугливым человеком и всегда отличался спокойствием и прозорливостью, особенно в сфере мировых политических и экономических процессов. Однако, не смотря ни на что, Петр Васильевича очень недооценил последствия мирового финансового кризиса и как следствие был уволен пару недель назад с должности сетевого администратора одной большой и серьезной организации.
Не смотря ни на что, Петр Васильевич не отчаялся и решил начать свое дело. Тщательно проанализировав бизнес-климат в своем регионе, Петр Васильевич пришел к выводу, что наиболее целесообразным будет открыть новый таксопарк. Первое с чего решил начать новоиспеченный бизнесмен – это закупить автомобили. За все время работы Петр Васильевичу удалось накопить сумму S, которую он готов потратить на закупку машин.
В городе, в котором живет Петр Васильевич, есть только один автосалон. Известно, что в этом автосалоне выставлено на продажу N автомобилей, причем установлено, что стоимость i-го автомобиля равняется Ai. Вашей задачей является помочь еще неопытному бизнесмену Петр Васильевичу приобрести максимальное количество автомобилей, потратив сумму не более S.
Входные данные
В первой строке входного файла INPUT. TXT находится два целых положительных числа разделенные одиночным пробелом – это числа N( 1 ≤ N ≤ 100) и S ( 1 ≤ S ≤ 109) соответственно.
Вторая строка содержит ровно N чисел Ai (1 ≤ Ai ≤ 109) , которые описывают стоимость соответствующих автомобилей. Все числа в строке разделены одиночными пробелами.
Выходные данные
В выходной файл OUTPUT. TXT выведите одно целое число – максимальное количество автомобилей, которые сможет приобрести Петр Иванович на сумму не более чем S.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 5 30 | 3 |
2 | 6 18 | 4 |
Свадьба
(Время: 1 сек. Память: 16 Мб Сложность: 32%)
Одна предприимчивая и очень симпатичная дамочка с прелестнейшим именем Горгона решила заработать себе денег на роскошную жизнь. N молодых людей так влюблены в нее, что предложили руку и сердце. К несчастью для них, Горгона видит в них только мешок с деньгами. Она планирует выйти замуж и почти сразу же развестись с некоторыми из молодых людей ради денежной выгоды. Все, что ей нужно, это подзаработать как можно больше денег (и уж, конечно, остаться незамужней). По законам этой прекрасной страны при разводе каждый из супругов получает половину всего имущества.
Вы планируете опубликовать статью, в которой опишете всю подлость и меркантильность этой особы. Для того чтобы статья получилась особенно красочной, нужно указать максимальную сумму денег, которую сможет получить Горгона.
Входные данные
В первой строке входного файла INPUT. TXT записано целое число N — количество молодых людей, без памяти влюбленных в Горгону (1 < N <= 40). Далее следует N чисел — сумма денег на счету каждого молодого человека. В последней строке записано целое число А — сумма денег на счету Горгоны. Суммы денег на счету — целые неотрицательные числа, не превосходящие 109.
Выходные данные
В выходной файл OUTPUT. TXT выведите единственное число — максимальную сумму денег, которой сможет обладать Горгона после своей махинации. Ответ выводите с точностью до шести знаков ровно в формате без мантиссы.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 2 | 7.500000 |
2 | 3 |
Интернет-олимпиады
(Время: 1 сек. Память: 16 Мб Сложность: 28%)
Многим известно о проекте «Интернет-олимпиады по информатике», расположенном в сети Интернет по адресу http://neerc. ifmo. ru/school/io/, где проводятся онлайн-олимпиады для школьников в двух номинациях: базовой и усложненной. Ваша задача состоит в том, чтобы написать программу, обрабатывающую результаты Интернет-олимпиады, то есть определяющую: какие команды в какой номинации будут участвовать в следующей олимпиаде.
Правила перехода команд из одной номинации в другую таковы. Задачи усложненной номинации решают следующие команды:
- участвовавшие в предыдущей олимпиаде в усложненной номинации и решившие хотя бы одну задачу; участвовавшие в предыдущей олимпиаде в базовой номинации, решившие хотя бы одну задачу, и при этом решившие либо столько же задач, сколько команда-победитель, либо строго больше задач, чем команда, занявшая медианное место среди команд, решивших хотя бы одну задачу (место с номером k/2, где k - число команд, участвовавших в базовой номинации, решивших хотя бы одну задачу, округление производится вниз).
Все остальные команды участвуют в следующей олимпиаде в базовой номинации. В этой задаче мы считаем, что никакие новые команды не региструются для участия в следующей олимпиаде.
Напомним также, что при подведении итогов одной олимпиады команды сортируются по убывании количества решенных задач, а при равенстве количества решенных задач - по возрастанию штрафного времени.
Входные данные
Первая строка входного файла INPUT. TXT содержит два целых числа: n и m - соответственно, количество команд, участвовавших в базовой и усложненной номинациях (1 ≤ n, m ≤ 1000).
После этого идут n строк, описывающих результаты команд, участвовавших в базовой номинации. Каждая из этих строк содержит три целых числа, разделенных пробелами, - id, s, t - соответственно, уникальный идентификатор команды, количество решенных задач и штрафное время. Количество решенных задач - целое число от 0 до 12, а штрафное время - целое число от 0 до 20000. Идентификатор команды - это целое число от 1 до 2000.
После этого идут m строк, описывающих результаты усложненной номинации в таком же формате.
Выходные данные
В первой строке выходного файла OUTPUT. TXT выведите число k команд, которые допускаются до участия в усложненной номинации в следующей олимпиаде. Вторая строка должна содержать k целых чисел - идентификаторы этих команд в возрастающем порядке.
Пример
№ | INPUT. TXT | OUTPUT. TXT |
1 | 6 3 | 4 |
