қазақша
русскийNurlan Zhusupov
Задача №1.
Задача F. Обещаю, последняя задача с деревом :)
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
Дано подвешенное бинарное дерево изначально состоящее из одной вершины с номером 1. Вам предстоит обработать $M$ запросов следующих типов :
- $Grow$ $V$. К каждому листу $leaf$ в поддереве вершины $V$ дописать две новые вершины с номерами $2 \cdot leaf$ и $2 \cdot leaf+1$.
- $Sum$ $V,$ нужно подсчитать сумму номеров вершин в поддерево вершины $V$ по модулю $10^9+7$.
Формат входного файла
Первая строка входного файла содержит целое число $M$ $(1 \leq M \leq 2 \cdot 10^5)$ — количество запросов.
В последующих $M$ строках содержится описания операций. Каждая операция описывается строкой $Op$ $V$, где $Op$ — тип операции ($Grow$ либо $Sum$), а $V$ — номер вершины для которой она выполняется.
Формат выходного файла
Для каждой операции типа $Sum$ в выходной файл на отдельной строке необходимо вывести соответствующую сумму. Выводите операции в том же порядке в котором они идут во входном файле.
Система оценки
Данная задача содержит семь подзадач:
- $1 \leq M \leq 20$. Оценивается в $15$ баллов.
- $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Grow$ $V$. Оценивается в $10$ баллов.
- $1 \leq M \leq 2 \cdot 10^5$, $V = 1$ во всех запросах $Sum$ $V$. Оценивается в $10$ баллов.
- $1 \leq M \leq 10^3$. Оценивается в $15$ баллов.
- $1 \leq M \leq 2 \cdot 10^5$, гарантируется что все запросы $Sum$ идут строго после всех запросов $Grow$. Оценивается в $15$ баллов.
- $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^6$. Оценивается в $15$ баллов.
- $1 \leq M \leq 2 \cdot 10^5$, $1 \le V \le 10^9$. Оценивается в $20$ баллов.
Пример:
Вход 5 Grow 1 Grow 1 Grow 2 Sum 1 Sum 4Ответ
66 21( Nurlan Zhusupov )
комментарий/решение олимпиада
Задача №2.
Задача F. Формат времени
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Вам даны два момента времени, причем гарантируется что они оба находятся в течении одних суток и первый из них находится строго раньше второго. По данной информации определите, использовался ли для их записи 12 часовой или 24 часовой формат. Напомним, что в 12 часовом формате часы записываются целыми числами с 1 до 12, в то время, как в 24 часовом нумерация начинается с 0 до 23 включительно. Для лучшего понимания ознакомьтесь с тестовыми примерами.
Формат входного файла
В первой и второй строках находятся первых и второй момент времени соответственно.
Времена заданы в формате HH:MM (00 $\leq$ HH $\leq$ 23, 00 $\leq$ MM $\leq$ 59)
Формат выходного файла
В зависимости от того в каком, 12 или 24 часовом, формате может быть записано данное время, выведите ``12-hour clock'' или ``24-hour clock'' соответственно.
В случае неоднозначности выведите - ``both''. При выводе кавычки выводить не нужно.
Примеры:
Вход 11:00 23:50Ответ
24-hour clockВход
09:20 03:30Ответ
12-hour clockВход
06:00 12:00Ответ
bothВход
00:00 01:00Ответ
24-hour clock( Nurlan Zhusupov )
комментарий/решение(3) олимпиада
Задача №3.
Задача B. Machine Vision
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
\includegraphics[width=0.25\textwidth,natwidth=360,natheight=300,height=100pt]{abbey_road.png} НурлашКО для своего нового стартапа потребовалось получать текст по фотографии. Так как он только на стадии прототипа, его друг предложил использовать готовое решение предоставляемое платформой Muugle Cloud Vision API. Однако, возникла небольшая проблема в работе с этой платформой. В ответ на отправленную фотографию возвращался не текст, а отдельные слова и их локации в виде прямоугольников. Помогите НурлашКО переупорядочить слова и получить осмысленный текст. Более формально. Вам будет дано $N$ прямоугольников со сторонами параллельными осям координат и слова соответствующие каждому из них. Прямоугольник $B$ является соседом $A$ тогда и только тогда когда площадь пересечения их проекций на ось ординат положительна и $B$ ближайший, слева или справа от $A$, среди всех таких. Строчкой называется максимальное по включению подмножество прямоугольников где от каждого прямоугольника можно добраться до любого другого, возможно переходя по соседям. Высота строчки определяется высотой самого высокого прямоугольника в ней. Выведите все строчки предварительно упорядочив их по высоте в порядке убывания. В самой строчке для каждого прямоугольника выведите соответствующую ему слово в порядке от самого левого к правому. Гарантируется что если $A$ является соседом $B$, то и $B$ является соседом $A$. Соседи для прямоугольника, если таковые есть, всегда определяются однозначно. Смотрите замечание к тестовому примеру для лучшего понимания.
Формат входного файла
Первая строка входного файла содержит единственное целое положительное число $N(1 <=q N <=q 2*10^5)$ — количество прямоугольников.
Каждая из следующих $N$ строке содержит строчку из маленьких латинских букв и цифр $s_i (1 <=q |s_i| <=q 100000)$ и четыре целых числа $xl_i$, $yb_i$, $xr_i$, $yt_i$ $(1 <=q xl_i, yb_i, xr_i, yt_i <=q 10^9)$ — слово соответствующее прямоугольнику, координаты левого нижнего и правого верхнего угла соответственно.
Гарантируется что сумма длин всех $s_i$ не превосходит $2*10^5$. Также гарантируется что никакие два прямоугольника не пересекаются и не вкладываются, но могут касаться.
Формат выходного файла
Выведите ответ на задачу в соответствии с форматом описанным в условии. Каждую строчку следует выводить в отдельной строке. Слова следует разделять единичным пробелом.
Система оценки
Данная задача содержит две подзадачи:
- $1 <=q N <=q 2000$. Оценивается в $30$ баллов.
- $1 <=q N <=q 200000$. Оценивается в $70$ баллов.
Пример:
Вход 7 1 9 1 10 3 New 5 3 11 5 Happy 1 2 4 4 2 4 0 5 2 9 10 0 11 2 Year 11 2 15 4 0 6 1 7 3Ответ
Happy New Year 2 0 1 9
Замечание
\includegraphics[width=0.5\textwidth,natwidth=610,natheight=450]{example2.png}
Обратите внимание, что прямоугольники с цифрами $2$ и $0$ не могут быть соседями для прямоугольника со словом $Happy$. В первом случае площадь проекций $Happy$ и $2$ на ординату равна нулю. Во втором случае хоть и площадь пересечения равна единице, но прямоугольник $New$ находится ближе, в тоже время имея положительную площадь пересечения и именно он будет соседом $Happy$.
Расстояние между двумя прямоугольниками $A$ и $B$ - это кратчайшее среди всех попарных расстояний от множества точек ограниченных прямоугольником $A$ до множества точек ограниченного прямоугольником $B$.
(
Nurlan Zhusupov
)
комментарий/решение(1) олимпиада
Задача №4.
Задача B. Machine Vision
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
\includegraphics[width=0.25\textwidth,natwidth=360,natheight=300,height=100pt]{abbey_road.png} НурлашКО для своего нового стартапа потребовалось получать текст по фотографии. Так как он только на стадии прототипа, его друг предложил использовать готовое решение предоставляемое платформой Muugle Cloud Vision API. Однако, возникла небольшая проблема в работе с этой платформой. В ответ на отправленную фотографию возвращался не текст, а отдельные слова и их локации в виде прямоугольников. Помогите НурлашКО переупорядочить слова и получить осмысленный текст. Более формально. Вам будет дано $N$ прямоугольников со сторонами параллельными осям координат и слова соответствующие каждому из них. Прямоугольник $B$ является соседом $A$ тогда и только тогда когда площадь пересечения их проекций на ось ординат положительна и $B$ ближайший, слева или справа от $A$, среди всех таких. Строчкой называется максимальное по включению подмножество прямоугольников где от каждого прямоугольника можно добраться до любого другого, возможно переходя по соседям. Высота строчки определяется высотой самого высокого прямоугольника в ней. Выведите все строчки предварительно упорядочив их по высоте в порядке убывания. В самой строчке для каждого прямоугольника выведите соответствующую ему слово в порядке от самого левого к правому. Гарантируется что если $A$ является соседом $B$, то и $B$ является соседом $A$. Соседи для прямоугольника, если таковые есть, всегда определяются однозначно. Смотрите замечание к тестовому примеру для лучшего понимания.
Формат входного файла
Первая строка входного файла содержит единственное целое положительное число $N(1 <=q N <=q 2*10^5)$ — количество прямоугольников.
Каждая из следующих $N$ строке содержит строчку из маленьких латинских букв и цифр $s_i (1 <=q |s_i| <=q 100000)$ и четыре целых числа $xl_i$, $yb_i$, $xr_i$, $yt_i$ $(1 <=q xl_i, yb_i, xr_i, yt_i <=q 10^9)$ — слово соответствующее прямоугольнику, координаты левого нижнего и правого верхнего угла соответственно.
Гарантируется что сумма длин всех $s_i$ не превосходит $2*10^5$. Также гарантируется что никакие два прямоугольника не пересекаются и не вкладываются, но могут касаться.
Формат выходного файла
Выведите ответ на задачу в соответствии с форматом описанным в условии. Каждую строчку следует выводить в отдельной строке. Слова следует разделять единичным пробелом.
Система оценки
Данная задача содержит две подзадачи:
- $1 <=q N <=q 2000$. Оценивается в $30$ баллов.
- $1 <=q N <=q 200000$. Оценивается в $70$ баллов.
Пример:
Вход 7 1 9 1 10 3 New 5 3 11 5 Happy 1 2 4 4 2 4 0 5 2 9 10 0 11 2 Year 11 2 15 4 0 6 1 7 3Ответ
Happy New Year 2 0 1 9
Замечание
\includegraphics[width=0.5\textwidth,natwidth=610,natheight=450]{example2.png}
Обратите внимание, что прямоугольники с цифрами $2$ и $0$ не могут быть соседями для прямоугольника со словом $Happy$. В первом случае площадь проекций $Happy$ и $2$ на ординату равна нулю. Во втором случае хоть и площадь пересечения равна единице, но прямоугольник $New$ находится ближе, в тоже время имея положительную площадь пересечения и именно он будет соседом $Happy$.
Расстояние между двумя прямоугольниками $A$ и $B$ - это кратчайшее среди всех попарных расстояний от множества точек ограниченных прямоугольником $A$ до множества точек ограниченного прямоугольником $B$.
(
Nurlan Zhusupov
)
комментарий/решение(1) олимпиада