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 )
комментарий/решение олимпиада