Задача B. Первый день стажировки
Задачу добавил: alef
Успешно сдано решений: 564
Будущий программист Кеша попал на летнюю стажировку в ту компанию, в которую и хотел. Один из сотрудников компании устроил стажёрам небольшую экскурсию по офису, а по её завершении привёл их на кухню, чтобы угостить кофе.
На кухне внимание Кеши привлекли n вазочек с печеньем, стоящие в линию на длинном столе. В каждой вазочке было печенье какого-то одного сорта, и ни в каких двух вазочках не было одинакового печенья. Кеша никак не мог решить, какое же печенье он хочет попробовать. И потому стал действовать следующим образом.
Он налил себе в кружку кофе и взял одно печенье из самой левой вазочки. Съев это печенье, Кеша стал размышлять, на сколько баллов он оценил бы вкус этого печенья по шкале, содержащей 1000 баллов. Затем Кеша взял одно печенье из следующей вазочки. И это печенье Кеше понравилось больше предыдущего. После этого Кеша попробовал печенье из третьей по счёту вазочки. А вот оно понравилось Кеше значительно меньше второго. Поэтому Кеша вернулся ко второй вазочке и съел ещё одно печенье из неё. Далее Кеша отправился к четвёртой вазочке...
Опишем процесс более формально.
Пробуя печенье, Кеша оценивает его вкус в баллах.
Пусть Кеша съел печенье из вазочки #j и выставил ему оценку bj. Пусть предыдущее печенье, которое он съел, имеет оценку bk (k < j).
Если только что съеденное печенье ему нравится не меньше, чем то печенье, которое он съел предыдущим, т.е. если bk ≤ bj, Кеша сразу переходит к вазочке #(j + 1).
Если же печенье понравилось Кеше меньше, чем то печенье, которое он съел предыдущим, т.е. bj < bk, Кеша сначала вернётся к той вазочке, откуда он брал предыдущее печенье, съест ещё одно печенье из этой вазочки, и уже после этого перейдёт к вазочке #(j + 1) (если таковая существует).
Ваша задача — определить, сколько всего печений съест Кеша и из какой вазочки он съест больше всего печений.
В первой строке содержится целое число n (1 ≤ n ≤ 1000) — количество вазочек на столе.
Во второй строке содержатся целые числа b1, b2, ..., bn (0 ≤ bj ≤ 1000, j = 1, 2, ..., n) — оценки вкуса печенья в баллах.
В первой строке выведите два числа: суммарное количество печений, которое съест Кеша, и номер вазочки, из которой он съест больше всего печений.
Если таких вазочек несколько, выведите наибольший из номеров.
Подзадача 1 (до 25 баллов)
Никакие две оценки вкуса не совпадают.
Баллы начисляются за каждый пройденный тест.
Подзадача 2 (до 75 баллов)
Оценки вкуса могут принимать любые допустимые значения.
Баллы начисляются за каждый пройденный тест.
По запросу сообщается результат проверки на каждом тесте.
6
5 2 3 8 7 6
10 4
7
4 3 5 4 5 7 6
10 6
Обратите внимание, что второй пример не удовлетворяет условиям Подзадачи 1. Однако, чтобы быть принятой на окончательную проверку, Ваша программа должна выводить верный ответ на все тесты из условия.
Поясним приведённые примеры.
В первом примере Кеша съедает печенье из первой вазочки и оценивает его на 5. Печенье из второй вазочки ему нравится меньше (оценка 2), поэтому он вернётся к первой вазочке и съест из неё ещё одно печенье (итого уже 3).
Затем он съест печенье из третьей вазочки, но, по его мнению, оно тоже менее вкусное, чем в первой (оценка 3). Так что он снова вернётся к первой вазочке и съест оттуда третье печенье (а всего съеденных к этому моменту будет 5).
Печенье в четвёртой вазочке понравится Кеше больше, чем любое из предыдущих: он оценит его на 8. Но печенье в пятой вазочке он оценит только на 7, и потому съест ещё одно печенье из четвёртой вазочки. Печенье в шестой вазочке Кеша оценит на 6 и снова отправится к четвёртой вазочке.
Кеша съест третье печенье из четвёртой вазочки и на этом остановится: больше вазочек нет. Таким образом, Кеша съест 10 печений, причём из первой и четвёртой вазочек он съест по 3 печенья. Так как нужно выводить наибольший из номеров вазочек, ответом будут числа 10 и 4.
В втором примере Кеша действует следующим образом.
Сначала он съедает одно печенье из первой вазочки и оценивает его на 4.
Затем он съедает печенье из второй вазочки и, оценив его на 3, возвращается к первой вазочке и съедает ещё одно печенье из первой вазочки. Заметим, что на текущий момент Кеша суммарно съел 3 печенья, из них 2 — из первой вазочки.
Печенье в третьей вазочке Кеша оценивает на 5, поэтому сразу переходит к четвёртой вазочке.
Печенье в четвёртой вазочке Кеша оценивает на 4, и это побуждает его вновь вернуться к третьей вазочке и съесть ещё одно печенье из неё. На этот момент Кеша съел 6 печений, 2 из них были из первой вазочки, 2 — из третьей.
В пятой вазочке Кеша обнаруживает печенье, сопоставимое с печеньем в третьей вазочке. Поэтому он съедает одно печенье из пятой вазочки и переходит к шестой вазочке.
Печенье из шестой вазочки Кеша оценивает на 7, так что Кеша отправляется к седьмой вазочке.
К его сожалению, в седьмой вазочке печенье менее вкусное, нежели в шестой, поэтому он съедает ещё одно печенье из шестой вазочки. Вазочки закончились, а Кеша суммарно съел 10 печений.
При этом Кеша съел по два печенья из первой, третьей и шестой вазочек. Поскольку нужно вывести наибольший номер вазочки, следует выводить именно 6.