eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Рейтинги ресторанов

Рейтинги ресторанов

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Знаменитый веб сайт разработал новую рейтинговую систему для ресторанов. Каждому ресторану даст свою оценку один из n (1n15) критиков, оценка представляет собой неотрицательное целое число (чем оно больше тем лучше). Некоторые критики являются более влиятельными чем другие.

Рестораны в каждом городе ранжируются следующим образом. Сначала следует просуммировать рейтинги, присвоенные всеми критиками ресторану. Ресторан с большей общей суммой всегда лучше ресторана с меньшей суммой. Если несколько ресторанов получили одинаковую сумму рейтинга, то их следует ранжировать на основе рейтинга критика 1. Если и теперь рейтинги ресторанов одинаковы, то ранжируем их по рейтингу критика 2 и т.д.

Владелец ресторана получил рейтинг своего ресторана, и ему любопытно какое место он занимает в городе. Ему не известны рейтинги других ресторанов в городе, поэтому он хочет вычислить наибольшее количество различных рейтингов, не больших полученного его рестораном. Напишите программу, которая ответит на этот вопрос.

Входные данные

Состоит из нескольких тестов, каждый из которых задается в одной строке. Каждая строка содержит число n, за которым следуют n целых чисел - рейтинги n критиков (именно в таком порядке). Общая сумма рейтингов для каждого ресторана не превосходит 30. Последняя строка содержит n = 0 и не обрабатывается.

Выходные данные

Для каждого теста вывести в отдельной строке количество различных рейтингов, не больших заданного. Выводимое число всегда помещается в 64-битовое знаковое целое.

Пример

Входные данные #1
1 3
2 4 3
5 4 3 2 1 4
0
Выходные данные #1
4
33
10810
Источник 2014 ACM North America - Rocky Mountain, Problem I