#3348

Сумма (AB)

Темы: [Генерация по номеру] [Разбиения]

Рассматриваются все разбиения натурального числа \(N\) на сумму \(К\) неотрицательных слагаемых (\(1 \leq N \leq 32\), \(2 \leq K \leq 32\)). Суммы, отличающиеся только порядком слагаемых, считаем различными. Упорядочим все разбиения по убыванию первого слагаемого, а при равных первых слагаемых – по убыванию второго слагаемого, а при равных первых и вторых слагаемых – по убыванию третьего слагаемого и т. д. Пронумеруем их. Например, при \(N=4\), \(К=3\) имеем:

Номер	1 слагаемое	2 слагаемое	3 слагаемое
1	4	0	0
2	3	1	0
3	3	0	1
4	2	2	0
5	2	1	1
6	2	0	2
7	1	3	0
8	1	2	1
9	1	1	2
10	1	0	3
11	0	4	0
12	0	3	1
13	0	2	2
14	0	1	3
15	0	0	4

Напишите программу, которая находит разбиение по номеру либо номер по разбиению.

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

В первой строке входного файла записана последовательность чисел. Если первое число \(0\), то необходимо найти разбиение по номеру, а если \(1\), то номер по разбиению. В первом случае далее в файле записано количество слагаемых, сумма и номер разбиения. Во втором случае далее в файле записано количество слагаемых \(K\) и затем разбиение (\(K\) неотрицательных чисел, сумма которых \(N\)). Все числа разделены пробелами.

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

Выведите в выходной файл разбиение либо номер.

Примеры

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

0 3 4 9

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

1 1 2

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

1 3 0 1 3

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

#3349

Мины (AB)

Темы: [Многоугольники. Выпуклые оболочки]

Миротворцы ООН в одной из горячих точек планеты обезвреживали минное поле следующим образом. Имея карту, на которой каждая мина задана своими декартовыми координатами, они, обратив внимание на то, что никакие 3 мины не лежат на одной прямой, протянули специальный шнур от мины к мине так, чтобы он образовал выпуклый многоугольник минимального периметра, при этом все остальные мины оказались внутри многоугольника. Обезвредив соединенные мины, они вновь протянули шнур по тому же принципу, и опять обезвредили соединенные шнуром мины. Так продолжалось до тех пор, пока очередной шнур оказалось невозможным протянуть, руководствуясь изложенными правилами. Сколько мин осталось обезвредить и сколько раз саперам приходилось протягивать шнур?

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

В первой строке входного файла записано целое число \(N\) (\(3 \leq N \leq 1000\)) – количество мин. Во второй строке записано \(2\times N\) целых чисел (\(N\) пар \(x_i\), \(y_i\)), описывающих координаты каждой мины (\(-32000 \leq x_i, y_i \leq 32000\)).

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

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

Примеры

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

9
0 0 0 8 6 8 6 0 1 1 1 7 5 7 5 1 3 2

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

1 2

#3350

Машинки (AB)

Темы: [Куча]

Петя, которому три года, очень любит играть с машинками. Всего у Пети N различных машинок, которые хранятся на полке шкафа так высоко, что он сам не может до них дотянуться. Одновременно на полу комнаты может находиться не более K машинок. Петя играет с одной из машинок на полу и если он хочет поиграть с другой машинкой, которая также находится на полу, то дотягивается до нее сам. Если же машинка находится на полке, то он обращается за помощью к маме. Мама может достать для Пети машинку с полки и одновременно с этим поставить на полку любую машинку с пола. Мама очень хорошо знает своего ребенка и может предугадать последовательность, в которой Петя захочет играть с машинками. При этом, чтобы не мешать Петиной игре, она хочет совершить как можно меньше операций по подъему машинки с пола, каждый раз правильно выбирая машинку, которую следует убрать на полку. Ваша задача состоит в том, чтобы определить минимальное количество операций. Перед тем, как Петя начал играть, все машинки стоят на полке.

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

В первой строке содержаться три числа \(N\), \(K\) и \(P\) (\(1 \leq K \leq N \leq 100000\), \(1 \leq P \leq 500000\)). В следующих \(P\) строках записаны номера машинок в том порядке, в котором Петя захочет играть с ними.

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

Выведите единственное число: минимальное количество операций, которое надо совершить Петиной маме.

Примечание к примеру тестов

Операция 1: снять машинку 1
Операция 2: снять машинку 2
Операция 3: поднять машинку 2 и снять машинку 3
Операция 4: поднять машинку 3 или 1 и снять машинку 2

Примеры

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

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

#3351

Конденсация графа (A)

Темы: [Обход в глубину]

Вам задан связный ориентированный граф с \(N\) вершинами и \(M\) ребрами (\(1 \leq N \leq 20000\), \(1 \leq M \leq 200000\)). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк содержит описание ребра – два целых числа из диапазона от 1 до \(N\) – номера начала и конца ребра.

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

На первой строке выведите число \(K\) – количество компонент сильной связности в заданном графе. На следующей строке выведите \(N\) чисел – для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Примеры

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

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

4
3 3 4 3 3 2 1 1 3 2

#3352

Дерево разбора (A)

Темы: [Разбор выражений]

Арифметические выражения, использующие сложение, вычитание, умножение, деление и возведение в степень определяются следующей грамматикой:
<выражение> -> <слагаемое> | <выражение> + <слагаемое> | <выражение> - <слагаемое>
<слагаемое> -> <множитель> | <слагаемое> \(\times\) <множитель> | <слагаемое> / <множитель>
<множитель> -> <элемент> | <элемент> ^ <множитель>
<элемент> -> <переменная> | (<выражение>)
<переменная> -> a | b | ... | z
Сложение, вычитание, умножение и деление левоассоциативны, а возведение в степень правоассоциативно. Для арифметического выражения определено его дерево разбора. Это двоичное дерево, в котором внутренние узлы соответствуют бинарным операциям, а листья соответствуют переменным. Дерево строится рекурсивно.

Дерево для переменной — это дерево из одной вершины, в которой записана эта переменная.

Дерево для элемента, являющегося выражением в скобках, — это дерево для самого выражения.

Дерево для множителя, являющегося элементом, — это дерево для этого элемента. Дерево для множителя вида «элемент e, возведенный в степень “множитель f”» — это дерево, в котором в корне записана операция ‘^’, левое поддерево корня — дерево для элемента e, правое поддерево корня — дерево для множителя f.

Деревья для множителя и слагаемого определяются аналогично, с тем лишь различием, что соответствующие операции лево-ассоциативные.

Вам дано арифметическое выражение, выведите его дерево разбора.

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

Во входном файле содержится корректное арифметическое выражение, состоящее не более чем из 400 символов.

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

В выходной файл выведите дерево разбора. Дерево разбора для переменной должно быть размера \(1\times 1\) и содержать эту переменную. Дерево, в корне которого записана операция, с поддеревьями \(T_1\) и \(T_2\), которые имеют размеры \(h_1\times w_1\) и \(h_2 \times w_2\) соответственно, должно быть размера \((max [h_1; h_2] + 2) \times (w_1 + w_2 + 5)\). Подробнее о формате вывода можно узнать, изучив пример выходного файла (см. ниже). Следует использовать следующие вспомогательные символы: минус ‘-’ (код ASCII 45), точка ‘.’ (код ASCII 46), вертикальная черта ‘|’ (код ASCII 124), квадратные скобки ‘[’ и ‘]’ (коды ASCII 91 and 93).

Примеры

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

(a+b+c)*(d-a)

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

         .----[*]----.   
         |           |   
   .----[+]-.     .-[-]-.
   |        |     |     |
.-[+]-.     c     d     a
|     |                  
a     b

Страница: << 329 330 331 332 333 334 335 >> Отображать по:

Номер	1 слагаемое	2 слагаемое	3 слагаемое
1	4	0	0
2	3	1	0
3	3	0	1
4	2	2	0
5	2	1	1
6	2	0	2
7	1	3	0
8	1	2	1
9	1	1	2
10	1	0	3
11	0	4	0
12	0	3	1
13	0	2	2
14	0	1	3
15	0	0	4

Номер	1 слагаемое	2 слагаемое	3 слагаемое
1	4	0	0
2	3	1	0
3	3	0	1
4	2	2	0
5	2	1	1
6	2	0	2
7	1	3	0
8	1	2	1
9	1	1	2
10	1	0	3
11	0	4	0
12	0	3	1
13	0	2	2
14	0	1	3
15	0	0	4

Номер	1 слагаемое	2 слагаемое	3 слагаемое
1	4	0	0
2	3	1	0
3	3	0	1
4	2	2	0
5	2	1	1
6	2	0	2
7	1	3	0
8	1	2	1
9	1	1	2
10	1	0	3
11	0	4	0
12	0	3	1
13	0	2	2
14	0	1	3
15	0	0	4