Задача A. Слияние последовательностей ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008
Входной файл: merge.in   Ограничение времени:2 сек
Выходной файл: merge.out   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

Автомат получает на вход две ленты чисел, длинами N и M соответственно, и выдает одну, длиной N+M. Автомат работает по следующему принципу:

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

Например, если исходно были последовательности (1,2,3) и (1,3,4), то результатом работы автомата может быть одна из следующих последовательностей: (1,1,2,3,3,4), (1,1,2,3,4,3), (1,1,3,2,3,4), (1,1,3,2,4,3), (1,1,3,4,2,3), (1,2,1,3,4,3), (1,2,1,3,3,4), (1,2,3,1,3,4), (1,3,1,2,3,4), (1,3,1,2,4,3), (1,3,1,4,2,3), (1,3,4,1,2,3).

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

В первой строке будут даны два целых числа N и M. Во второй строке записаны N различных целых чисел — числа на первой ленте. В третьей строке записаны M различных целых чисел — числа на второй ленте.

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

Выведите единственное целое число — количество различных последовательностей.

Ограничения

1≤ N≤ 100

1≤ M≤ 100

Числа по модулю не превосходят 106.

Примеры тестов

№ Входной файл (merge.in) Выходной файл (merge.out)
1 
3 3
1 2 3
1 3 4
 
12

Задача B. Перестановки ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008
Входной файл: permutation.in   Ограничение времени:2 сек
Выходной файл: permutation.out   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

Вася выписал на доске в каком-то порядке все числа от 1 по N, каждое число ровно по одному разу. Количество чисел оказалось довольно большим, поэтому Вася не может окинуть взглядом все числа. Однако ему надо всё-таки представлять эту последовательность, поэтому он написал программу, которая отвечает на вопрос — сколько среди чисел, стоящих на позициях с x по y, по величине лежат в интервале от k до l. Сделайте то же самое.

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

В первой строке лежит два натуральных числа — N — количество чисел, которые выписал Вася и M количество вопросов, которые Вася хочет задать программе. Во второй строке дано N чисел — последовательность чисел, выписанных Васей. Далее в M строках находятся описания вопросов. Каждая строка содержит четыре целых числа x y k l.

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

Выведите M строк, каждая должна содержать единственное число — ответ на Васин вопрос.

Ограничения

1 ≤ N ≤ 105

1 ≤ M ≤ 105

1 ≤ x ≤ y ≤ N

1 ≤ k ≤ l ≤ N

Примеры тестов

№ Входной файл (permutation.in) Выходной файл (permutation.out)
1 
4 2
1 2 3 4
1 2 2 3
1 3 1 3
 
1
3

Задача C. Упаковка схемы ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008
Входной файл: schema.in   Ограничение времени:2 сек
Выходной файл: schema.out   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

Схема состоит из нескольких узлов и соединений между ними. Для сохранности соединений схемы некоторые узлы помещают в отдельные коробки. Те соединения, которые полностью попадают в одну коробку, называются защищенными. В зависимости от нагрузки и важности, соединения изготавливают из различных сплавов, а, следовательно, их стоимость различна. Ваша задача — распределить узлы по k коробкам так, чтобы суммарная стоимость всех незащищенных соединений была минимальна. Каждая коробка должна содержать хотя бы один узел.

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

В первой строке входного файла записано три числа n, m, k — количество узлов, количество соединений и количество коробок соответственно. Далее в m строках записано описание соединений. Соединение задается тремя целыми числами x, y, z. Это означает, что узел x соединен с узлом y, а стоимость соединения z. Каждая пара узлов соединена не более, чем одним соединением.

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

В выходной файл выведите n чисел. i-ое число означает номер коробки, в которую помещена i-ая вершина. Коробки нумеруются числами от 1 до k. В каждой коробке должен быть хотя бы один узел. Суммарная стоимость всех незащищенных соединений должна быть минимальна. Если существует несколько вариантов правильного ответа, выведите любой.

Ограничения

1 ≤ n ≤ 14

1 ≤ m ≤ n(n − 1)/2

1 ≤ k ≤ n

1 ≤ x, y ≤ n

x ≠ y

1 ≤ z ≤ 107>

Примеры тестов

№ Входной файл (schema.in) Выходной файл (schema.out)
1 
3 3 2
1 2 100
2 3 200
3 1 300
 
1 2 1
0.030s 0.004s 11