Задача
Бедный Иа
Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]\left \langle 1,1 \right \rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.
Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]\left \langle 0,0 \right \rangle[/latex], а его дом расположен в точке [latex]\left \langle x_{h},y_{h} \right \rangle[/latex], и направление движения он менял [latex]k[/latex] раз.
Входные данные
В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0\leq n,k,t,v\leq 100)[/latex]
. Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5\leq x_{h}, y_{h}\leq 10^5)[/latex]
.
Выходные данные
Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.
Тесты
|
Входные данные
|
Выходные данные |
| [latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex]
[latex]5[/latex] [latex]7[/latex] |
Good night Ia |
| [latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex]
[latex]15[/latex] [latex]15[/latex] |
Good night Ia |
| [latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex]
[latex]105[/latex] [latex]-105[/latex] |
Poor Ia |
| [latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex]
[latex]40[/latex] [latex]-20[/latex] |
Good night Ia |
| [latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]
[latex]-24[/latex] [latex]0[/latex] |
Poor Ia |
| [latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]
[latex]-23[/latex] [latex]0[/latex] |
Good night Ia |
Первый вариант кода программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import java.io.BufferedReader; import java.io.InputStreamReader; class Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params1 = bufferedReader.readLine().split(" "); String[] params2 = bufferedReader.readLine().split(" "); int n, k, t, v, hx, hy, x = 0, y = 0; n = Integer.parseInt(params1[0]); k = Integer.parseInt(params1[1]); t = Integer.parseInt(params1[2]); v = Integer.parseInt(params1[3]); hx = Integer.parseInt(params2[0]); hy = Integer.parseInt(params2[1]); for (int i = 0; i = (x - hx) * (x - hx) + (y - hy) * (y - hy)){ System.out.print("Good night Ia"); } else { System.out.print("Poor Ia"); } } } |
Второй вариант кода программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.io.BufferedReader; import java.io.InputStreamReader; class Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params1 = bufferedReader.readLine().split(" "); String[] params2 = bufferedReader.readLine().split(" "); int n, k, t, v, hx, hy; n = Integer.parseInt(params1[0]); k = Integer.parseInt(params1[1]); t = Integer.parseInt(params1[2]); v = Integer.parseInt(params1[3]); hx = Integer.parseInt(params2[0]); hy = Integer.parseInt(params2[1]); int s1, s2, s3, s4, m1, m2, m3, m4; m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4; m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4; m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4; m4 = (k + 1) / 4; s1 = (1 + (m1 - 1) * 2 * n) * m1; s2 = (1 + n + 2 * n * (m2 - 1)) * m2; s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3; s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4; int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4; if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){ System.out.print("Good night Ia"); } else { System.out.print("Poor Ia"); } } } |
Решение задачи
Вариант 1
Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]\sum\limits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:
[latex]f(x,y) = \begin{cases} \left \langle1 + xy, 1 + xy\right \rangle & \textit{if } x\vdots 4 = 0 \\\\ \left \langle1 + xy, (-1) \cdot (1 + xy)\right \rangle & \textit{if } x\vdots 4 = 1 \\\\ \left \langle(-1) \cdot (1 + xy), (-1) \cdot (1 + xy)\right \rangle & \textit{if } x\vdots 4 = 2 \\\\ \left \langle(-1) \cdot (1 + xy), 1 + xy\right \rangle & \textit{if } x\vdots 4 = 3 \end{cases}[/latex]
То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]\sum\limits_{i=0}^k f(i, n)[/latex] — это вектор [latex]\left \langle a,b \right \rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]\left \langle a,b \right \rangle[/latex] и вектора [latex]\left \langle x_{h},y_{h} \right \rangle[/latex]:
$$\sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$
И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]\left \langle 0,0 \right \rangle[/latex] и [latex]\left \langle 1,1 \right \rangle[/latex], то есть — [latex]\sqrt{2}[/latex].
$$ \sqrt{2} tv$$
Итого, выводим Good night Ia, если [latex]2t^2v^2 \geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.
Вариант 2
Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = \displaystyle\frac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$
Для направления на северо-восток:
$$a_1 = 1, d = 4n \Rightarrow S_{1}=\frac{1 + 1 +4n(m_1-1)}{2}\Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=1$ иначе, $m_1=\displaystyle\frac{k+1}{4}$
Для направления на юго-восток:
$$a_2 = 1+n, d = 4n \Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=2$ иначе, $m_2=\displaystyle\frac{k+1}{4}$
Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n \Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=3$ иначе, $m_3=\displaystyle\frac{k+1}{4}$
Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n \Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=4$ иначе, $m_4=\displaystyle\frac{k+1}{4}$
Тогда, для вычисления координат [latex]\left \langle x,y \right \rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.
Ссылки
Условие задачи на e-olymp
Код решения первого варианта на ideone.com
Код решения второго варианта на ideone.com
Заданы размеры прямоугольной двери $a$, $b$ и размеры шкафа, который имеет форму прямоугольного параллелепипеда $x$, $y$, $z$. Можно ли пронести шкаф сквозь дверь, если проносить его разрешается так, чтобы каждое ребро шкафа было параллельно или перпендикулярно стороне двери.