Задача Army
Військові - серйозні люди. Одного разу прапорщик Пупкін виявив, що солдати в строю розміщені не по росту. Ви можете уявити, який крик він підняв, і як дісталось сержанту Васіну, який був відповідальним за шикування. Щоб не бути розжалуваним у рядові, сержант вирішив показати прапорщику, що було не так вже й багато помилок у шикуванні. Сержант доручив рядовому (до призову - учаснику NetOI) Глюкову порахувати, скількома способами можна вибрати К + 1 солдат, що стоять по росту. Не обов'язково, щоб вони стояли підряд. Сержант бачить, що помилок достатньо, тому запевнив Глюкова, що ця кількість не буде перевищувати 8•1018. Сержант вважає, що це число буде вражаючим, і прапорщик вибачить йому його помилку.
Технічні умови: Програма зчитує з клавіатури число N - кількість солдат у строю (1<= N<=100 000) і число К (0<=К<=10), далі N чисел - номер,який мав би солдат у строю, якби всі стояли на своїх місцях. Всі числа розділені пропусками. У кожного солдата різний зріст, тому є тільки єдиний спосіб вірно розставити солдат.
Програма виводить на екран єдине число - відповідь на поставлену задачу.Приклад.
Введення> 3 2 1 2 3
Виведення> 1
Задача Army
Военные - серьезные люди. Однажды прапорщик Пупкин обнаружил, что солдаты в строю расположены вовсе не по росту. Вы можете представить, какой крик он поднял, и как досталось сержанту Васину, который был ответственным за построение. Чтобы не быть разжалованным в рядовые, сержант решил показать прапорщику, что было не так уж много ошибок в построении. Сержант поручил рядовому (до призыва - участнику NetOI) Глюкову посчитать, сколькими способами можно выбрать К + 1 солдат, стоящих по росту. Не обязательно, чтобы они стояли подряд. Сержант видит, что ошибок предостаточно, поэтому заверил Глюкова, что это количество не будет превосходить 8•1018. Сержант думает, что это число будет впечатляющим, и прапорщик простит ему его ошибку.
Технические условия: Программа считывет с клавиатуры число N — количество солдат в строю (1 <= N <= 100 000) и число К (0 <= К <= 10), далее N чисел - номер, который бы имел солдат в строю, если бы все стояли на своем месте. Все числа разделены пробелами. У каждого солдата разный рост, поэтому есть только единственный способ правильно расставить солдат. Программа выводит на экран единственное число — ответ на поставленную задачу.
Пример.
Ввод> 3 2 1 2 3
Вывод> 1