Задача 1. Разделение прямоугольника ≡

Условие

Аня играет в новую настольную игру «Клетчатое королевство».

Рассмотрим прямоугольное клетчатое поле размером a × b.

Необходимо разделить его на m прямоугольников вертикальными или горизонтальными разрезами. Прямоугольники не обязательно должны получиться равными. Необходимо суммарно провести ровно k разрезов.

Каждый разрез представляет собой прямую линию от одного края поля до другого края поля. Разрезы разрешено делать только по границам клеток — линиям сетки.

Выведите, сколько провести горизонтальных (0 ≤ h < a) и сколько вертикальных (0 ≤ v < b) разрезов. Если поле можно разрезать несколькими способами, выведите тот, в котором горизонтальных разрезов меньше. Если поле нельзя разрезать требуемым образом, выведите  − 1.

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

В первой строке дано ровно одно целое число t — количество тестов.

В следующих t строках находится описание тестов: в i-й строке через пробел даны четыре целых числа: a, b, k, m — высота и ширина поля, количество разрезов и количество прямоугольников соответственно.

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

Для каждого теста выведите через пробел ровно два целых числа h и v — количество горизонтальных и количество вертикальных разрезов, если прямоугольное клетчатое поле можно разрезать требуемым образом, в противном случае выведите число  − 1.

Ограничения

1 ≤ t ≤ 100

1 ≤ a, b ≤ 10⁹, 0 ≤ k ≤ 2 ⋅ 10⁹, 1 ≤ m ≤ 10¹⁸, k < m

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

В приведенном примере содержится три теста:

1. В первом тесте поле можно разрезать, как показано на рисунке:

   

2. Во втором тесте поле нельзя разрезать требуемым образом.
3. В третьем тесте поле можно разрезать, как показано на рисунке:

   

Примеры тестов

3
2 2 1 2
1 2 2 3
3 5 5 12

0 1
-1
2 3

Задача 2. Произведение Фибоначчи ≡

Условие

Напомним, что последовательность чисел Фибоначчи определяется следующим образом: F₀ = 1, F₁ = 1, F_n = F_n − 2 + F_n − 1. Последовательность чисел Фибоначчи начинается так: 1, 1, 2, 3, 5, 8, 13, 21, 34, ….

Дано натуральное число n. Требуется посчитать количество способов представить его как произведение чисел Фибоначчи, каждое из которых больше 1.

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

Первая строка ввода содержит целое число t — количество тестов.

Следующие t строк содержат тесты, каждая строка содержит одно целое число n.

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

Для каждого теста вывести одно число — искомое количество способов.

Ограничения

1 ≤ t ≤ 50

2 ≤ n ≤ 10¹⁸

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

В примере:

• число 2 можно представить в виде произведения чисел Фибоначчи единственным способом 2 = 2;
• число 7 нельзя представить в виде произведения чисел Фибоначчи;
• число 8 можно представить двумя способами: 8 = 2 ⋅ 2 ⋅ 2 и 8 = 8;
• число 40 можно представить двумя способами: 40 = 2 ⋅ 2 ⋅ 2 ⋅ 5 и 40 = 5 ⋅ 8.

Примеры тестов

5
2
7
8
40
64

1
0
2
2
3

Задача 3. Робот-пылесос ≡

Условие

Рассмотрим координатную плоскость, которую планируется очищать с использованием робота пылесоса. Робот-пылесос представляет собой квадрат размером k × k со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке (0, 0), а правый верхний, соответственно — в точке (k, k).

Вам дана последовательность из n перемещений робота по плоскости, i-е перемещение характеризуется направлением d_i, принимающим значения N (вверх, увеличение координаты Y), S (вниз, уменьшение координаты Y), W (влево, уменьшение координаты X) или E (вправо, увеличение координаты X), и целым числом a_i — расстоянием, на которое робот перемещается.

Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка считается убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера k × k, на котором находился робот.

По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.

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

В первой строке ввода через пробел даны два целых числа: размер робота k и количество команд n.

В i-й из следующих n строк через пробел даны направление i-го перемещения d_i и его расстояние a_i (d_i — буква N, S, W или E).

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

Выведите суммарную площадь убранной роботом поверхности.

Ограничения

1 ≤ k ≤ 10⁴; 1 ≤ n ≤ 10⁵

1 ≤ a_i ≤ 10⁹

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

Ниже приведены иллюстрации к перемещениям робота согласно примерам из условия. Клетки, которые робот посетил за время своих перемещений, затемнены.

Примеры тестов

1 5
E 2
N 2
W 4
S 4
E 4

17

3 4
W 2
N 1
W 1
N 2

27

Задача 4. Разноцветные точки ≡

Условие

Рассмотрим n точек на плоскости, пронумерованных от 1 до n, обозначим их как P₁, P₂, …, P_n, координаты i-й точки (x_i, y_i).

Рассмотрим следующий процесс. Выберем номер начальной точки i и номер следующей за ней точки j (i ≠ j), а также целое число t. После этого номер прицельной точки k вычисляется по следующему алгоритму. Рассмотрим вектор overrightarrowP_i P_j, направленный из точки P_i в точку P_j. Упорядочим все точки, кроме j-й, по углу, отсчитывая против часовой стрелки от направления вектора, равного overrightarrowP_i P_j, отложенного из точки j. При равенстве угла будем упорядочивать точки по возрастанию расстояния до точки j. В качестве точки k выбирается точка, являющаяся t-й в данном порядке при нумерации с единицы. Далее точка j становится начальной, а точка k — следующей за ней, после чего, пользуясь тем же алгоритмом, вычисляется номер прицельной точки. Этот процесс повторяется до бесконечности.

Для лучшего понимания процесса рассмотрим следующий пример. Пусть имеются 6 точек, изображенных на рисунке 1, а t = 4. Пусть номер начальной точки равен 1, а номер следующей за ней точки равен 2. Отложим вектор overrightarrowP₁ P₂ от точки P₂ и отсортируем все точки, кроме точки P₂, по углу, отсчитывая против часовой стрелки от направления данного вектора. На рисунке 2 отложенный вектор обозначен пунктирной линией, а также для удобства проведены векторы из точки P₂ во все остальные точки.

Точки будут упорядочены следующим образом: P₃, P₅, P₁, P₆, P₄. Таким образом, номер прицельной точки равен 6. Далее точка 2 становится начальной, а точка 6 — следующей.

На рисунке 3 изображен процесс для начальной точки 2 и следующей точки 6. Точки будут упорядочены следующим образом: P₄, P₃, P₂, P₁, P₅. Обратите внимание, что точка P₁ в этом списке находится раньше, чем точка P₅, так как расстояние от точки P₁ до точки P₆ меньше, чем расстояние от точки P₅ до точки P₆. Прицельная точка будет иметь номер 1.

На рисунке 4 изображен процесс для начальной точки 6 и следующей точки 1. Обратите внимание, что в данном случае вектор overrightarrowP₆ P₁, отложенный из точки P₁ совпадает с вектором overrightarrowP₁ P₅, отложенным из точки P₁. Эти векторы изображены сплошной линией. Точки будут упорядочены следующим образом: P₅, P₆, P₄, P₂, P₃. Прицельная точка будет иметь номер 2. Таким образом, далее процесс начнется для начальной точки 1 и следующей точки 2 и зациклится.

Покрасим каждую из n точек в один из трех цветов. Цвет i-й точки определяется следующим образом:

• Пусть существует такая точка j, что, выбрав точку i в качестве начальной, а точку j в качестве следующей, в результате описанного процесса точка i побывает начальной бесконечное количество раз. В этом случае точка i будет покрашена в зеленый цвет.
• Пусть точка i не была покрашена в зеленый цвет и существует такая точка j, что, выбрав точку i в качестве начальной, а точку j в качестве следующей, в результате описанного процесса точка i побывает начальной еще хотя бы один раз. В этом случае точка i будет покрашена в синий цвет.
• Пусть точка i не была покрашена ни в зеленый, ни в синий цвет. В этом случае точка i будет покрашена в красный цвет.

Для каждой точки определите, в какой цвет ее нужно покрасить.

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

Первая строка содержит два целых числа n и t.

Каждая из следующих n строк содержит два целых числа x_i и y_i. Гарантируется, что никакие две точки не совпадают.

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

Выведите строку, состоящую из n символов: i-й символ строки должен обозначать цвет i-й точки. Для зеленой точки выведите букву~«G», для синей точки — букву~«B», а для красной точки — букву~«R».

Ограничения

2 ≤ n ≤ 1 000, 1 ≤ t ≤ n − 1

 − 10⁹ ≤ x_i, y_i ≤ 10⁹

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

Рассмотрим некоторые точки из первого примера.

Точка P₁ окрашены в зеленый цвет, потому что можно выбрать точку P₂ в качестве следующей, и процесс посетит точку P₁ бесконечное количество раз. Данный пример был рассмотрен выше в условии задачи.

Можно показать, что точка P₃ не является зеленой, однако она является синей, так как можно выбрать точку 1 в качестве следующей, точка 3 окажется начальной еще хотя бы один раз. Процесс для начальной точки 1 и следующей точки 3 проиллюстрирован на рисунках 5, 6 и 7 ниже.

Для начальной точки 3 и следующей точки 1 точки будут упорядочены следующим образом: P₆, P₄, P₂, P₃, P₅. Точка с номером 3 становится прицельной. Далее для начальной точки 1 и следующей точки 3 точки будут упорядочены следующим образом: P₅, P₁, P₂, P₆, P₄. Точка с номером 6 становится прицельной. Наконец, для начальной точки 3 и следующей точки 6 точки будут упорядочены следующим образом: P₄, P₃, P₂, P₁, P₅. Точка с номером 1 становится прицельной. Далее процесс продолжится с начальной точкой 6 и следующей точкой 1. Из примера, описанного выше в условии задачи, мы знаем, что процесс зациклится, посещая точки с номерами 6, 1 и 2.

Во втором примере из условия легко показать, что если одна из точек является начальной, а другая — следующей, то прицельной станет точка, которая являлась начальной. Поэтому обе точки будут окрашены в зеленый цвет.

Примеры тестов

6 4
-1 -1
1 -2
4 -2
2 -4
2 3
-4 -5

GGBBRG

2 1
1 1
2 2

GG