Задача

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [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

Первый вариант кода программы

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");
		}
	}
}

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");

}

Второй вариант кода программы

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");
		}
	}
}

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

Facebook
X
Shares

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

e-olymp 72. Дорога домой