| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 9 | 6 | 3 | 50.000% |
На доске выписано две последовательности из $n$ различных целых чисел: $A = [a_1, a_2, \ldots, a_n]$ и $B = [b_1, b_2, \ldots, b_n]$.
Составим из них $n^2$ дробей вида $a_i / b_j,ドル сократим каждую дробь и отсортируем их по неубыванию.
Задано число $q$ и $q$ целых чисел $c_1, c_2, \ldots, c_q$. Для каждого $j$ следует выдать $c_j$-ю в неубывающем порядке дробь из получившихся.
На первой строке ввода находятся числа $n$ и $q$ (1ドル \le n \le 10^5,ドル 1ドル \le q \le 10^5,ドル $q \le n^2$).
Дополнительно выполняется неравенство $n\cdot q \le 10^5$.
На второй строке ввода находятся $n$ различных целых чисел $a_1, a_2, \ldots, a_n$ (1ドル \le a_i \le 10^6$).
На третьей строке ввода находятся $n$ различных целых чисел $b_1, b_2, \ldots, b_n$ (1ドル \le b_i \le 10^6$).
На четвертой строке ввода находятся $q$ различных целых чисел $c_1, c_2, \ldots, c_q$ (1ドル \le c_i \le n^2$).
Выведите $q$ строк. На $j$-й строке выведите $c_j$-ю по неубыванию дробь среди получившихся. Дробь $p/q$ следует выводить в формате <<p q>>, дробь должна быть несократимой.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 14 | $n \le 50$ |
| 2 | 13 | $n \le 500$ |
| 3 | 15 | $q \le 100,ドル $c_i \le 100$ |
| 4 | 21 | $c_i \le 10^5$ |
| 5 | 37 |
4 8 3 4 1 2 2 3 4 5 1 16 2 4 5 6 10 15
1 5 2 1 1 4 2 5 1 2 1 2 4 5 3 2
В примере дроби исходно равны: $$\left[ \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \frac{3}{5}, \frac{4}{2}, \frac{4}{3}, \frac{4}{4}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \frac{2}{5} \right],$$ после сокращения $$\left[ \frac{3}{2}, \frac{1}{1}, \frac{3}{4}, \frac{3}{5}, \frac{2}{1}, \frac{4}{3}, \frac{1}{1}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{1}, \frac{2}{3}, \frac{1}{2}, \frac{2}{5} \right],$$ после сортировки $$\left[ \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}, \frac{1}{1}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{2}{1} \right].$$
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2022 6번