В этом году проходил BSUIR Open XIV, мне было очень приятно съездить в Минск и на само соревнование. Но еще больше мне понравилась задачу, которую я туда предложил. В целом я не видел эту идею раньше, но она кажется достаточно простой, чтобы появиться раньше на каких-нибудь соревнованиях. Так что если вы знаете, где раньше встречалась это идея, то поделитесь, пожалуйста.
Задача. (*BSUIR OPEN XIV*) Дано клеточное поле $$$100 \times 100$$$, в котором между некоторыми клетками проведены стены, также стены проведены по границе поля. Луч запускается из центра клетки $$$(r,c)$$$ в направлении $$$(x,y)$$$. Требуется определить, в какой клетке он окажется, пройдя расстояние $$$\sqrt{x^2+y^2}$$$, если луч отражается от стен. Решение.
Взглянем на вектор $$$(x,y)$$$ и посмотрим, в каком порядке он пересекает вертикальные и горизонтальные линии сетки. В точке $$$(0,0)$$$ пересечение с линиями сетки учитывать не будем, но будем учитывать пересечения в точке $$$(x,y)$$$, причем по формальным причинам мы будем считать, что сначала происходит пересечение с вертикальной прямой.
Последовательность пересечений можно записать в виде строки:
Rобозначает пересечение вертикальной линии сетки (перемещение на клетку вправо)Uобозначает пересечение горизонтальной линии сетки.
Тогда каждому вектору $$$(x,y)$$$ можно сопоставить строку $$$s(x, y)$$$, содержащую последовательность этих пересечений. Например, $$$s(4,3) = RURURRU$$$. Предположим, что $$$x \ge y$$$, это означает, что вектор "пологий", и перед каждым пересечением горизонтальной линии происходит пересечение вертикальной, а именно, перед $$$k$$$-м символом U стоит
подряд идущих символов R. Таким образом, перед каждым символом U стоит блок, состоящий как минимум из $$$floor(x/y)$$$ символов R, эти блоки вместе с символами U можно сжать в один символ, например:
$ s(4,3) = #RURURRU = (#RU)(#RU)#R#(RU) -> s(1,3)= #UURU $
Таким образом, можно предположить, что если $$$s(x, y, R, U)$$$~-- это строка $$$s(x,y)$$$, где на месте символов R и U стоят строки $$$R$$$ и $$$U$$$, то верно равенство:
