Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Сладкие забавы

(Время: 1 сек. Память: 16 Мб Сложность: 50%)

Маленькие сладкоежки Сережа и Юля очень любят конфеты. Родители детей это знают, и потому у них не возникает вопросов о том, что ребятишкам дарить в день рождения.

А тут подвернулся особый случай – обоим ребятишкам исполняется по 10 лет, и потому родители подсказали приглашенным гостям, чему дети больше всего обрадуются на их общем юбилее.

Гостей в день рождения собралось достаточно много – N человек. Гость, пришедший i-м по счету, подарил детям коробку, содержащую Ai конфет. Коробки конфет были как совсем маленькие, так и невероятно большие. Коробки были с прозрачными крышками и было видно, сколько там конфет.

Чтобы все было честно, дети решили поделить коробки так, чтобы каждому досталось не менее K конфет. Однако дети обнаружили, что сделать это можно многими способами. Ваша задача – определить количество различных способов честного дележа конфет, учитывая, что коробки не вскрываются и конфеты поштучно не делятся, и каждая коробка должна достаться только одному из ребятишек. Два варианта деления конфет считаются различными, если существует коробка конфет, которая в данных вариантах принадлежит разным детям.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и K соответственно (1 ≤ N ≤ 50; 1 ≤ K ≤ 10000). Числа в строке разделены одиночным пробелом.

Вторая строка содержит N натуральных чисел Ai (1 ≤ i ≤ N, 1 ≤ Ai ≤ 109), разделенных одиночными пробелами, где число Ai – это количество конфет в коробке, подаренной гостем, пришедшим i-м по счету.

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

Единственная строка выходного файла OUTPUT.TXT должна содержать одно целое число — количество способов честно поделить конфеты между детьми.

Примеры

INPUT.TXTOUTPUT.TXT
14 3
1 2 3 2
8
25 67
10 22 30 41 50
6
33 6
4 1 5
0

Пояснение

Для первого примера варианты разбиения (номера коробок, доставшихся, например, Сереже): 3, 1 2, 1 3, 1 4, 2 3, 2 4, 3 4, 1 2 4.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483