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
4
2
0
2.Вход: 
3
6 2 8
8 8 4
2
2
3
Ответ: 
2
2
Система оценки:
Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:
( Alan Amanov )
комментарий/решение олимпиада
Задача №2. (Башни) У Алана есть $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
4
2
0
2.Вход: 
3
6 2 8
8 8 4
2
2
3
Ответ: 
2
2
Система оценки:
Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:
( 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
Ответ
3
( 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
Ответ
3
( Alan Amanov )
комментарий/решение(7) олимпиада