Alan Amanov

Задача №1. (Башни) У Алана есть

$n$ башен, у каждой из которых есть параметр

$a_i$ - числитель рук и параметр

$b_i$ - знаменатель рук. В

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

$[\frac{a_i}{b_i}]$ или дробное количество рук -

$\frac{a_i}{b_i}$ . Для

$i$ -го дела, которые он задумал, Алану необходимо суммарно ровно

$x_i$ рук. Для каждого из этих дел Алан берет все

$n$ башен, то есть суммарная \textit{рукость} всех башен должна равняться

$x_i$ . Помогите Алану найти количество способов сделать это, для каждого из

$q$ легких дел.

Формат входных данных:

В первой строке дается целое положительное число

$n$ (

$1 \le n \le 40$ ).
Во второй строке дается

$n$ целых положительных чисел

$a_1, a_2, .., a_n$ (

$1 \le a_i \le 100000$ )
В третьей строке дается

$n$ целых положительных чисел

$b_1, b_2, .., b_n$ (

$1 \le b_i \le 100000$ )
В следующей дается целое положительное число

$q$ (

$1 \le q \le 100000$ ) - количество запросов.
В следующих

$q$ строках находится по одному целому числу

$x$ - запросы из условия (

$1 \le x \le 4000000$ )

Формат выходных данных:

Выведите

$q$ целых числе по одному в каждой строке - количество способов получить ровно

$x_i$ целых рук.

Примеры:

1.Вход:

5
14 10 12 6 15
8 8 9 9 15
4
4
5
6
7

Ответ:

2.Вход:

Ответ:

2
2

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

Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:

20 теста: $(1 \le n \le 10, 1 \le q \le 5)$
31 тестов: $(1 \le n,q \le 20)$
49 тестов: $(1 \le n \le 40, 1 \le q \le 10^5)$

( Alan Amanov )
комментарий/решение олимпиада

Задача №2. (Башни) У Алана есть

$n$ башен, у каждой из которых есть параметр

$a_i$ - числитель рук и параметр

$b_i$ - знаменатель рук. В

$[\frac{a_i}{b_i}]$ или дробное количество рук -

$\frac{a_i}{b_i}$ . Для

$i$ -го дела, которые он задумал, Алану необходимо суммарно ровно

$x_i$ рук. Для каждого из этих дел Алан берет все

$n$ башен, то есть суммарная \textit{рукость} всех башен должна равняться

$x_i$ . Помогите Алану найти количество способов сделать это, для каждого из

$q$ легких дел.

Формат входных данных:

В первой строке дается целое положительное число

$n$ (

$1 \le n \le 40$ ).
Во второй строке дается

$n$ целых положительных чисел

$a_1, a_2, .., a_n$ (

$1 \le a_i \le 100000$ )
В третьей строке дается

$n$ целых положительных чисел

$b_1, b_2, .., b_n$ (

$1 \le b_i \le 100000$ )
В следующей дается целое положительное число

$q$ (

$1 \le q \le 100000$ ) - количество запросов.
В следующих

$q$ строках находится по одному целому числу

$x$ - запросы из условия (

$1 \le x \le 4000000$ )

Формат выходных данных:

Выведите

$q$ целых числе по одному в каждой строке - количество способов получить ровно

$x_i$ целых рук.

Примеры:

1.Вход:

5
14 10 12 6 15
8 8 9 9 15
4
4
5
6
7

Ответ:

2.Вход:

Ответ:

2
2

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

Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:

20 теста: $(1 \le n \le 10, 1 \le q \le 5)$
31 тестов: $(1 \le n,q \le 20)$
49 тестов: $(1 \le n \le 40, 1 \le q \le 10^5)$

( Alan Amanov )
комментарий/решение олимпиада

Задача №3.

Задача E. Меж двух миров

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Алан живет в мире под номером

$A$ . Нурдаулет живет в мире под номером

$B$ . В мире

$A$ , если одна строка является префиксом другой, то они считаются одинаковыми. У Нурдаулета есть

$n$ строк, он хочет узнать количество неупорядоченных пар

$i, j$ таких, что Алану они покажется одинаковыми. Помогите Нурдаулету с задачей. Обозначим

$|s|$ как длину строки

$s$ . Строка

$s$ является префиксом строки

$t$ , если

$|s| <= |t|$ и строка

$s$ равна строке, образованной из первых

$|s|$ символов строки

$t$ .

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

В первой строке дается единственное число

$n (1 <= n <= 100000)$ — количество строк. В следующих

$n$ строках дается по одной строке

$s_i$ . Гарантируется, что суммарная длина строк не превышает

$500000$ .

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

Выведите единственное число — ответ на задачу.

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

В 40 процентах тестов

$n <= 100$ . В 20 процентах тестов, длины всех строк равны.

Пример:

Вход

3
ab
abc
ab

Ответ

( Alan Amanov )
комментарий/решение(7) олимпиада

Задача №4.

Задача E. Меж двух миров

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Алан живет в мире под номером

$A$ . Нурдаулет живет в мире под номером

$B$ . В мире

$A$ , если одна строка является префиксом другой, то они считаются одинаковыми. У Нурдаулета есть

$n$ строк, он хочет узнать количество неупорядоченных пар

$i, j$ таких, что Алану они покажется одинаковыми. Помогите Нурдаулету с задачей. Обозначим

$|s|$ как длину строки

$s$ . Строка

$s$ является префиксом строки

$t$ , если

$|s| <= |t|$ и строка

$s$ равна строке, образованной из первых

$|s|$ символов строки

$t$ .

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

В первой строке дается единственное число

$n (1 <= n <= 100000)$ — количество строк. В следующих

$n$ строках дается по одной строке

$s_i$ . Гарантируется, что суммарная длина строк не превышает

$500000$ .

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

Выведите единственное число — ответ на задачу.

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

В 40 процентах тестов

$n <= 100$ . В 20 процентах тестов, длины всех строк равны.

Пример:

Вход

3
ab
abc
ab

Ответ

( Alan Amanov )
комментарий/решение(7) олимпиада