На вход программе дается целое число n — количество запланированных звонков (1 ≤ n ≤ 2·105). На следующей строке вводятся через пробел n целых чисел Pi, обозначающие прибыли от звонков (0 ≤ Pi ≤ 1 000). Затем вводятся n+1 целых чисел Aj, обозначающие, сколько звонков можно будет провести после подзарядки (0 ≤ Aj ≤ 106).
Выходные данные
Выведите два числа, первое — это максимальная выгода, которую может получить бизнесмен, второе — количество пропущенных первых звонков, при котором она получается (0, если выгоднее всего не заряжать телефон вовсе).
Примеры тестов
входные данные
5
1 2 0 4 1
2 0 8 3 5 6
выходные данные
5 3
Примечание
Рассмотрим пример из условия: n = 5, P1 = 1, P2 = 2, P3 = 0, P4 = 4, P5 = 1, A0 = 2, A1 = 0, A2 = 8, A3 = 3, A4 = 5, A5 = 6.
Если бизнесмен не будет заряжать телефон, то результат будет равен P1 + P2 = 1 + 2 = 3 рубля. Если предприниматель будет заряжать телефон вместо первого звонка, то он не сможет позвонить ни разу, так как A1 = 0. Если вместо первых двух звонков, то результат составит P3 + P4 + P5 = 0 + 4 + 1 = 5 рублей. Если вместо первых трех, то P4 + P5 = 4 + 1 = 5. Если вместо четырёх звонков, то P5 = 1 рубль. Наконец, если бизнесмен будет заряжать телефон вместо всех n = 5 звонков, то он заведомо ничего не получит. Таким образом, два лучших варианта — это заряжать либо вместо 2 первых звонков, либо вместо 3, в обоих случаях получаем 5 рублей прибыли. По условию, из них мы выбираем выбираем вариант с 3 пропущенными звонками.
Объяснение:
ответ: 3
Объяснение:
Тот факт, что код удовлетворяет условию Фано, означает, что ни одно кодовое слово не является началом другого (например, т.к. для кодирования буквы А используется цифра 0, то никакое другое кодовое слово не может начинаться с нуля, ведь тогда кодовое слово для А будет началом другого кодового слова).
Итак, кодовые слова для букв Б, В и Г не могут начинаться с нуля. Так как код двоичный, все они начинаются с единицы. Наша задача — найти три последовательности, которые начинаются с единицы и при этом имеют наименьшее возможное число символов (цифр).
Закодировать какую-либо букву одним символом, единицей, мы не можем, потому что в этом случае уже не удастся закодировать другие буквы (из-за условия Фано; к тому же, буква, закодированная одной единицей, была бы началом кодового слова для Б (110), что опять не удовлетворяет условию Фано).
Если использовать кодовые слова длиной в 2 символа, получится закодировать только две буквы, ведь таких кодовых слова всего два: 11 и 10. Составить третье кодовое слово не позволит условие Фано.
Если используем кодовые слова длиной в 3 символа, сможем закодировать все буквы, например, присвоить букве Г кодовое слово 111, а букве Б, как и сказано в условии, кодовое слово 110, и тогда свободные слова ещё останутся. Но в этом случае остаётся ещё одно кодовое слово из двух символов, не являющееся началом другого, — 10 (т.к. А = 0, Б = 110, Г = 111). Присвоим это кодовое слово оставшейся букве В.
Итак, присвоить всем трём буквам (кроме А) кодовые слова длиной 2 символа невозможно, а если все три кодовых слова будут длиной в 3 символа, то их последовательность не будет иметь наименьшее число символов (как нужно в задании), поэтому вариант, когда одна буква закодирована двумя символами, а две оставшиеся — тремя, даёт при сложении числа символов последовательность наименьшей длины.
Получается, что длины кодовых слов букв:
А — 1 символ (0)
Б — 3 символа (110)
В — 2 символа (10)
Г — 3 символа (111)
При кодировании последовательности из этих букв (например, АБВГ, порядок в данном случае не важен) каждая буква заменяется её кодовым словом.
Значит, число символов в последовательности равно общему количеству символов во всех четырёх кодовых словах и составляет
1 + 3 + 2 + 3 = 9 (символов).
ответ: 3
