Рассмотрим следующий классификатор точек на плоскости, зависящий от параметра t: точка (x, y) относится к первому классу при t · x + (t − 2) · y ⩾ 0 и ко второму — в противном случае.
При каком наименьшем значении t обе точки (0, 2) и (3, 4) относятся к первому классу?

В узле решающего дерева 20 объектов трёх классов, причём каждый объект относится ровно к одному классу; доли классов равны p1, p2 и p3 (доля класса — это отношение числа объектов этого класса к общему числу объектов в узле). Индекс Джини узла (G = 1 − p1² − p2² − p3²) равен 0.56, а размеры первых двух из классов совпадают.

Найдите численность наибольшего класса.

Три модели решают задачу бинарной классификации и ошибаются независимо друг от друга; точность каждой модели, то есть вероятность правильного ответа, равна x, причём x < 1. Ансамбль из этих трёх моделей отвечает по правилу большинства голосов, то есть ответ ансамбля совпадает с ответом, который дали хотя бы две из трёх моделей. Известно, что вероятность ошибки ансамбля составляет 52 % от вероятности ошибки одной отдельной модели. Найдите x.

В зоопарке на ленивцев установили датчики, которые каждый день оценивают продолжительность их сна. Результаты находятся в файле sloths.csv. Файл содержит четыре столбца:
• sloth_id — идентификатор ленивца;
• enclosure — номер вольера;
• day — номер дня наблюдения;
• sleep_hours — продолжительность сна в этот день в часах.

Таблица содержит не более одной строки для одного ленивца и одного дня. Каждый ленивец в течение всего периода наблюдения находится в одном и том же вольере. Из-за сбоев датчиков некоторые значения sleep_hours могут быть пропущены или оказаться невозможными.

Выполните следующие действия:
1. Оставьте только строки, в которых значение sleep_hours не пропущено и удовлетворяет условию 0 ⩽ sleep_hours ⩽ 24.
2. Для каждого ленивца подсчитайте число дней с корректными измерениями. Оставьте только ленивцев, для которых имеется не менее 10 таких дней.
3. Для каждого оставшегося ленивца найдите среднее значение sleep_hours по всем его корректным измерениям.
4. Для каждого вольера найдите среднее арифметическое значений, полученных на предыдущем шаге для всех оставшихся ленивцев этого вольера. Таким образом, каждый ленивец влияет на результаты по своему вольеру одинаково независимо от числа дней наблюдений.
5. Не учитывайте вольеры, в которых после предыдущих действий осталось менее пяти ленивцев.
6. Найдите вольер с наибольшим средним временем сна. Если таких вольеров несколько, выберите вольер с наименьшим номером.

Запишите число строк, оставшихся после выполнения шага 1.

Запишите номер вольера с наибольшим средним временем сна.

Чему равно среднее время сна в этом вольере? Ответ выразите в часах, округлите до тысячных.

Из симуляции в реальность

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Инженеры обучают робот-пылесос с подкреплением; робот раз за разом проходит эпизоды — последовательности действий, получает за них оценку и понемногу улучшает свою стратегию. Сначала эпизоды прогоняют в симуляторе, а лучшие из них затем проверяют в реальной комнате.

Очередной эпизод записан строкой s длины n из символов U, D, L и R. Робот выполняет команды по очереди слева направо, и каждая сдвигает его ровно на одну клетку: U — вверх, D — вниз, L — влево, R — вправо.

Для проверки нужно испытательное поле — прямоугольник из h строк и w столбцов клеток. Инженеры ставят робота в любую клетку по своему выбору, и он выполняет весь эпизод. Если очередная команда уводит робота за край поля, то он падает и проверка срывается.

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

Чем больше в поле клеток, тем оно дороже. Помогите инженерам выбрать подходящее поле с наименьшим количеством клеток h · w.

Формат входных данных
В первой строке ввода дано одно целое число n — длина эпизода (1 ⩽ n ⩽ 2 · 10⁵).
Во второй строке дана последовательность s из n символов U, D, L и R — команд управления роботом.

Формат выходных данных
Выведите два целых числа h и w — количество строк и количество столбцов подходящего поля с наименьшим количеством клеток. Если таких полей несколько, выведите любое из них.

Система оценивания
Тесты из условия не оцениваются. За каждый пройденный тест остальных групп начисляется 1 балл независимо от других тестов.
Группа 1: 5 баллов, 1 ⩽ n ⩽ 1000
Группа 2: 7 баллов, Без дополнительных ограничений

Замечание
В первом примере робот, поставленный в левую нижнюю клетку поля 2 × 3, сдвигается на две клетки вправо и на одну вверх и остаётся на поле.
В третьем примере робот опускается на две клетки, сдвигается на две вправо и поднимается на четыре, то есть побывает в пяти разных строках и в трёх разных столбцах. Стартовать здесь нужно из третьей сверху клетки первого столбца.

Примеры
Ввод:
3
RRU
Вывод:
2 3

Ввод:
2
UD
Вывод:
2 1

Ввод:
8
DDRRUUUU
Вывод:
5 3

Ввод:
1
L
Вывод:
1 2

Фишки для Реверси. Коррекция бинарных меток

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

При подготовке данных для обучения модели машинного обучения был обнаружен набор объектов с бинарными метками. Каждая метка может принимать одно из двух значений: 0 или 1.
В результате ошибки системы разметки некоторые метки оказались неправильными.
Для исправления данных используется специальная процедура: за одну операцию можно выбрать две различные записи и одновременно изменить обе их метки на противоположные.
Даны две бинарные строки длины n: исходные и требуемые значения меток для n объектов. Символ 1 означает метку одного класса, а символ 0 — метку другого класса.

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

Формат входных данных
В первой строке вводится натуральное число n (1 ⩽ n ⩽ 200000).
Во второй строке вводится строка длины n из нулей и единиц — исходные значения меток.
В третьей строке вводится строка длины n из нулей и единиц — требуемые значения меток.

Формат выходных данных
Если преобразование невозможно, выведите NO SOLUTION.
В противном случае в первой строке выведите количество операций t, не превышающее 200000. В следующих t строках выведите по два неравных номера позиций, метки в которых нужно изменить на противоположные. Позиции нумеруются с 1.
Если существует несколько верных ответов, выведите любой из них.

Примеры
Ввод:
5
10100
00011
Вывод:
2
1 3
4 5

Ввод:
1
0
1
Вывод:
NO SOLUTION