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$ )
Yшінші жолда

$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$ )
Yшінші жолда

$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 second

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

256 megabytes

Алан

$A$ нөмірлі әлемінде өмір сүреді. Нұрдаулет

$B$ нөмірлі әлемінде өмір сүреді. Егер

$A$ әлемінде бір жол екінші жолдың префиксі болса, сол екі жол бірдей деп есептелінеді. Нұрдаулетте

$n$ жол бар, ол Аланға бірдей болып көрінетін реттелмеген

$i, j$ жұптарының санын білгісі келеді. Нұрдаулетке осыны анықтауға көмектесіңіз.

$|s|$ арқылы

$s$ жолының ұзындығын белгілейік.

$s$ жолы

$t$ жолының префиксі болуы үшін,

$|s| <= |t|$ болуы және

$s$ жолы

$t$ жолынан алынған бірінші

$|s|$ символға тең болуы қажет.

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

Бірінші жолда жалғыз сан

$n (1 <= n <= 100000)$ берілген — жолдардың саны. Келесі

$n$ жолдың әрқайсысында

$s_i$ жолы берілген. Берілген жолдардың ұзындықтарының қосындысы

$500000$ -нан аспайтындығына кепілдік беріледі.

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

Бір сан — есептің жауабын шығарыңыз.

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

Тесттердің 40 пайызында

$n <= 100$ . Тесттердің 20 пайызында, барлық жолдардың ұзындықтары бірдей.

Пример:

\exmpfile{example.01}{example.01.a}% ( Alan Amanov )
комментарий/решение(7) олимпиада

Есеп №4.

Есеп E. Екі әлем тоғысында

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

1 second

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

256 megabytes

Алан

$A$ нөмірлі әлемінде өмір сүреді. Нұрдаулет

$B$ нөмірлі әлемінде өмір сүреді. Егер

$A$ әлемінде бір жол екінші жолдың префиксі болса, сол екі жол бірдей деп есептелінеді. Нұрдаулетте

$n$ жол бар, ол Аланға бірдей болып көрінетін реттелмеген

$i, j$ жұптарының санын білгісі келеді. Нұрдаулетке осыны анықтауға көмектесіңіз.

$|s|$ арқылы

$s$ жолының ұзындығын белгілейік.

$s$ жолы

$t$ жолының префиксі болуы үшін,

$|s| <= |t|$ болуы және

$s$ жолы

$t$ жолынан алынған бірінші

$|s|$ символға тең болуы қажет.

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

Бірінші жолда жалғыз сан

$n (1 <= n <= 100000)$ берілген — жолдардың саны. Келесі

$n$ жолдың әрқайсысында

$s_i$ жолы берілген. Берілген жолдардың ұзындықтарының қосындысы

$500000$ -нан аспайтындығына кепілдік беріледі.

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

Бір сан — есептің жауабын шығарыңыз.

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

Тесттердің 40 пайызында

$n <= 100$ . Тесттердің 20 пайызында, барлық жолдардың ұзындықтары бірдей.

Пример:

\exmpfile{example.01}{example.01.a}% ( Alan Amanov )
комментарий/решение(7) олимпиада