Страница: 1 2 >> Отображать по:

#2517

Темы: [Одномерные массивы] [Комбинаторика]

Источники: [ Командные олимпиады, ВКОШП, 2009, Задача H ]

Разбиения числа $n$ на слагаемые — это набор целых положительных чисел, сумма которых равна $n$. При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми, поэтому можно считать, что слагаемые в разбиении упорядочены по неубыванию.

Например, существует 7 разбиений числа 5 на слагаемые:

5 = 1 + 1 + 1 + 1 + 1

5 = 1 + 1 + 1 + 2

5 = 1 + 1 + 3

5 = 1 + 2 + 2

5 = 1 + 4

5 = 2 + 3

5 = 5

В приведенном примере разбиения упорядочены лексикографически — сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче вам потребуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение.

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

Входной файл содержит одну строку — разбиение числа $n$ на слагаемые ($1 \le n \le 100 000$). Слагаемые в разбиении следуют в неубывающем порядке.

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

Выведите в выходной файл одну строку — разбиение числа $n$ на слагаемые, следующее в лексикографическом порядке после приведенного во входном файле. Если во входном файле приведено последнее разбиение числа $n$ на слагаемые, выведите «No solution».

Примеры

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

5=1+1+3

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

5=1+2+2

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

5=5

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

No solution

#2899

Вычеркивание двух

Темы: [Комбинаторика]

Задана строка S, состоящая из маленьких букв латинского алфавита. Сколько различных строк можно получить при помощи вычеркивания ровно двух символов из S?

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

Входной файл содержит строку S, записанную в первой и единственной строке файла. Длина строки S от 2 до 100000 символов включительно. Строка S содержит только маленькие буквы латинского алфавита.

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

Выходной файл должен содержать одно целое число, равное количеству различных строк, которые можно получить при помощи вычеркивания ровно двух символов из S

Примеры

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

abbccc

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

#111824

Спасти котенка

Темы: [Комбинаторика] [Динамическое программирование]

Источники: [ Командные олимпиады, ВКОШП, 2012, Задача F ]

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

Поле для выполнения задания представляет собой прямоугольник размером $n \times m$ метров, разбитый на квадраты единичной площади. В одном из квадратов исходно находится Артур, в некотором другом квадрате находится котенок. Кроме того, один из квадратов содержит лифт, встав на который вместе с котенком, Артур успешно выполняет задание.

За один шаг Артур может перемещаться на любой квадрат, имеющий общую сторону с тем, на котором он стоит. После этого квадрат, на котором перед этим шагом стоял Артур, исчезает и больше на него вставать нельзя. Таким образом исчезают в том числе и квадрат, на котором исходно стоял Артур, и квадрат с котенком. Цель Артура - дойти до котенка, взять его и затем дойти до лифта. При этом очки за выполнение задания, зависят от числа шагов, которое сделает Артур, поэтому ему необходимо сделать минимальное число шагов.

Выяснив, сколько шагов ему придется сделать, Артур заинтересовался, сколько существует различных способов дойти до котенка, а затем с ним до лифта, сделав в сумме минимальное число шагов. Помогите ему это выяснить. Это число может быть довольно большим, поэтому Артур просит найти его по модулю $10^9+7$.

Формат входного файла

Первая строка входного файла содержит два натуральных числа $n$ и $m$ - размеры поля для выполнения задания ($2 \le n, m \le 100$).

Вторая строка содержит два целых числа $x_A$ и $y_A$ - координаты квадрата, на котором исходно находится Артур ($1 \le x_A \le n$, $1 \le y_A \le m$). Третья строка содержит два целых числа $x_K$ и $y_K$ - координаты квадрата, на котором сидит котенок ($1 \le x_K \le n$, $1 \le y_K \le m$). Четвертая строка содержит два целых числа $x_E$ и $y_E$ - координаты квадрата, на котором находится лифт ($1 \le x_E \le n$, $1 \le y_E \le m$). Эти три квадрата попарно различны.

Формат выходного файла

В единственной строке выходного файла выведите одно число - число способов дойти до котенка и затем до лифта, не наступая на один квадрат два раза, совершив при этом минимальное количество шагов. Число необходимо вывести по модулю $10^9+7$.

Пояснения к примеру

$\text{[math]}$

Два способа для поля, приведенного в примере.

Примеры

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

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

#113299

Все слова

Темы: [Комбинаторика] [Целые числа]

Вася придумал свой собственный алфавит, в котором $N$ символов. Теперь он хочет составить c с помощью этого алфавита все слова, состоящие ровно из $K$ букв, причём ни одно слово не может начинаться с первой буквы алфавита и не может заканчиваться на последнюю букву алфавита. Помогите Васе определить, сколько он сможет составить таких слов.

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

Входная строка содержит два числа, разделённых пробелом: число символов в алфавите $N$ и длину слов $K$ ($0$ < $N, K$ <= $10$).

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

Программа должна вывести единственное число - количество слов длиной $K$ в алфавите мощностью $N$, таких что ни одно слово не начинается с первой буквы алфавита и не заканчивается на последнюю букву алфавита.

Примеры

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

4 1

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

#113514

Неподвижные точки

Темы: [Комбинаторика]

Назовём неподвижной точкой перестановки такой индекс i , что a _i = i . Посчитайте число перестановок длины n , в которых нет неподвижных точек. Так как это число может быть воистину огромным, выведите его по модулю 10 ⁹ + 7 .

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

В единственной строке входного файла задано целое число n ( 1 ≤ n ≤ 10 ⁷ ) — количество элементов в перестановке.

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

В единственной строке выведите количество перестановок из n элементов без неподвижных точек, взятое по модулю 10 ⁹ + 7 .

Система оценки

n ≤ 10 — 30 баллов.

n ≤ 5000 — 40 баллов.

n ≤ 10 ⁶ — 20 баллов.

n ≤ 10 ⁵ — 10 баллов.

Примеры

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

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

Страница: 1 2 >> Отображать по:

Выбрано

Отменить

Добавить в контест