Задача A. Прогрессии ≡

Условие

Жители страны Прогрессляндии слишком буквально поняли лозунг своего великого правителя "Больше прогрессий - хороших и разных" и решили сосчитать, сколько всего прогрессий они могут придумать. К нашему великому счастью, они знают только целочисленные строго возрастающие арифметические прогрессии в диапазоне от 0 до N, причем прогрессия обязательно должна начинаться со священного числа 0 и иметь хотя бы два элемента.

К сожалению, они недостаточно прогрессивны, чтобы решить эту проблему. Помогите им.

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

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

Ограничения

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

3

5

Задача B. Упаковка конфет ≡

Условие

Кондитерская фабрика изготовила партию конфет N различных сортов. В партию входит a_i конфет i-го сорта.

Конфеты упаковываются в коробки двух видов: обычные и ассорти. В каждой из обычных коробок после упаковки должно оказаться ровно M конфет какого-нибудь одного сорта, а в каждой коробке ассорти — ровно N конфет, по одной каждого сорта.

Требуется определить максимально возможное значение M. Например, если изготовлено 15, 19 и 55 конфет трёх разных сортов, то их следует упаковывать в обычные коробки по 4 штуки, после чего останутся конфеты для 3 коробок ассорти.

Рекомендуется рассмотреть частичные решения

• N = 2

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

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

Ограничения

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

2 
4 9

5

3
7 7 7

7

Задача C. Наименьший общий делитель ≡

Условие

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

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

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

Ограничения

1 ≤ A, B ≤ 2³¹ − 1

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

10 20

2

13 17

1

Problem D. Group by GCD ≡

Statement

Given N positive integers, divide them in two disjoint non-empty groups in such a way that the greatest common divisor of each group is greater than 1.

Input file format

Output file format

Constraints

Sample tests

2
3 5

3 0 5

4
2 2 6 8

2 6 2 0 8

3
3 4 5

-1

Задача E. Перестановки с НОД ≡

Условие

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} — нет.

Перестановка {p₁, p₂, …, p_n} будет лексикографически меньше перестановки {q₁, q₂, …, q_n}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого p_j = q_j при j < i и p_i < q_i.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой — множество {9, 3, 6, 8}.

Примечание

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

Входной файла содержит целые числа числа — n m k, за которыми следуют n различных натуральных чисел s_i.

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

Выходной файл должен содержать m-ую k-перестановку заданного множества или −1, если такой нет.

Ограничения

1 ≤ n ≤ 16

1 ≤ m, k, s_i ≤ 10⁹

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

4 1 2
6 8 3 9

3 9 6 8

4 4 2
6 8 3 9

9 3 6 8

4 5 2
6 8 3 9

-1

Задача F. Расстановка ферзей ≡

Условие

Требуется расставить N ферзей на шахматной доске размером N × N

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

Во входном файле находится единственное число — N

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

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

Ограничения

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

4

2 4 1 3

Задача G. Вектор ≡

Условие

Дан целочисленный вектор P₁, P₂, …, P_N. Над любым вектором, состоящим из двух и более элементов, определим операцию сжатия, состоящую в замене произвольной пары соседних элементов на их сумму. Например, вектор 1 2 3 в результате сжатия может превратиться в вектор 3 3 либо 1 5.

Требуется путем последовательного применения операции сжатия получить из исходного вектора вектор максимально возможной длины, все элементы которого не меньше A и не больше B.

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

Входной файл содержит тройку чисел N A B, за которой следует N чисел P₁, P₂, …, P_N.

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

Выходной файл должен содержать длину результирующего вектора, за которой следуют его элементы. Если решений не существует, вывести единственное число 0. Если решений несколько, вывести любое из них.

Ограничения

Все числа во входном файле целые.

1 ≤ N ≤ 1000, 0 ≤ A, B, p_i ≤ 10⁶.

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

7 3 6
3 1 1 1 2 2 2

3
5 3 4

7 3 3
3 1 1 1 2 2 2

0

6 20 50
29 5 19 37 43 5

4
29 24 37 48

Problem H. Evacuation Plan ≡

Statement

Flatland government is building a new highway that will be used to transport weapons from its main weapon plant to the frontline in order to support the undergoing military operation against its neighbor country Edgeland. Highway is a straight line and there are n construction teams working at some points on it.

During last days the threat of a nuclear attack from Edgeland has significantly increased. Therefore the construction office has decided to develop an evacuation plan for the construction teams in case of a nuclear attack. There are m shelters located near the constructed highway. This evacuation plan must assign each team to a shelter that it should use in case of an attack.

Each shelter entrance must be securely locked from the inside to prevent any damage to the shelter itself. So, for each shelter there must be some team that goes to this shelter in case of an attack. The office must also supply fuel to each team, so that it can drive to its assigned shelter in case of an attack. The amount of fuel that is needed is proportional to the distance from the team's location to the assigned shelter. To minimize evacuation costs, the office would like to create a plan that minimizes the total fuel needed.

Your task is to help them develop such a plan.

Input file format

The first line of the input file contains n — the number of construction teams (1 ≤ n ≤ 4000). The second line contains n integer numbers — the locations of the teams. Each team's location is a positive integer not exceeding 10⁹, all team locations are different.

The third line of the input file contains m — the number of shelters (1 ≤ m ≤ n). The fourth line contains m integer numbers — the locations of the shelters. Each shelter's location is a positive integer not exceeding 10⁹, all shelter locations are different.

The amount of fuel that needs to be supplied to a team at location x that goes to a shelter at location y is equal to |x − y|.

Output file format

The first line of the output file must contain z — the total amount of fuel needed. The second line must contain n integer numbers: for each team output the number of the shelter that it should be assigned to. Shelters are numbered from 1 to m in the order they are listed in the input file.

Sample tests

3
1 2 3
2
2 10

8
1 1 2