Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2814. Пещера Полифема
Бинарный поискБыстрая сортировка
Олимпиадные задачи на русском языке
| 29/09/2024 | Очный тур личного первенства по спортивному программированию ( 6) |
| 30/09/2024 | Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (I) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Был в этом стаде баран, меж всех остальных наилучший.
За спину взявшись его, соскользнул я барану под брюхо
И на руках там повис…
Хозяин… глупец, не заметил,
Что привязано было под грудью баранов шерстистых.
Одиссея, песнь 9
Сбежать из пещеры циклопа Полифема – нелегкая задача, ведь вход завален огромным камнем. Циклоп убирает камень только для того, чтобы выпустить своих баранов из пещеры на пастбище снаружи. Одиссею пришла в голову отличная идея: пусть каждый из его спутников спрячется под шкурой какого-нибудь из баранов, тогда циклоп их не заметит. Однако, не любой баран подойдет: некоторые из них слишком малы, чтобы скрыть могучего ахейца. Под каждым бараном должно прятаться не больше одного ахейца, и рост каждого ахейца должен быть не больше, чем размер скрывающего его барана. К счастью для Одиссея, в пещере спрятано еще и немного бараньего корма. Если скормить X порций корма барану, то его размер увеличится на X. Порции можно распределять между одним или несколькими баранами как угодно. Помогите Одиссею понять, какое максимальное количество спутников удастся вывести из пещеры благодаря его идее.
В первой строке ввода указаны три целых числа: N – число баранов, M – число ахейцев, С – количество порций корма (1<=N,M<=10^5, 0<=C<=100). Во второй строке перечислены N целых чисел от 1 до 10^9 включительно – размеры каждого из баранов. Во второй строке перечислены M целых чисел от 1 до 10^9 включительно – рост каждого из ахейцев.
Выведите одно целое число – максимальное количество ахейцев, которые могут одновременно спрятаться под баранами.
Пример ввода 1
4 3 1 7 2 2 1 6 6 3
Пример вывода 1
2
Пример ввода 2
1 3 5 1 10 10 10
Пример вывода 2
0
Пояснение к первому примеру. Первый или второй ахейцы ростом 6 могут спрятаться под первым бараном размера 7 (но не оба одновременно). Ни под каким другим бараном (даже после откармливания 1 порцией корма) спрятаться они не могут. Второму или третьему барану можно скормить единственную доступную порцию корма, тогда он вырастет от размера 2 до размера 3 и сможет скрыть третьего ахейца.
