e-olymp 4020. Культ-орки на лестнице

21/09/2020 by Мария Жаркая

Задача

В Летней Кинематографической Школе пришло время обеда и эльф Коля поспешил в столовую. Однако для того, чтобы попасть в столовую, Коле нужно подняться по длинной лестнице, а на каждой её ступеньке в это время суток стоит по культ-орку. Каждый культ-орк разрешает Коле пройти по своей ступеньке только после того, как Коля запишется на мероприятие, которое этот культ-орк организует. При этом никакие два культ-орка не проводят одно и то же мероприятие, и все мероприятия проходят в разное время.

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

Входные данные:

В первой строке вводятся два числа $n$ и $k$ $(1 \leqslant n \leqslant 10000, 0 \leqslant k \leqslant 20)$, $n$ — количество ступенек на лестнице, $k$ — максимальное количество ступенек, через которые Коля может перепрыгнуть за один прыжок (то есть, например, на первом шаге Коля может прыгнуть на $(k + 1)$-ую или более низкие ступеньки). Во второй строке вводятся $n$ чисел: $i$-ое число указывает на длительность в минутах того мероприятия, которое проведёт культ-орк, стоящий на $i$-ой ступеньке. Каждое мероприятие не может длиться более $24$ часов. Ступеньки нумеруются снизу вверх, ступенькой номер $n$ считается весь этаж столовой.

Выходные данные:

Выведите одно число — минимальное количество минут, которое Коле придётся распланировать.

Тесты

№	Входные данные	Выходные данные
1	5 2 7 3 9 2 11	14
2	6 1 59 32 4 21 5 1	42
3	10 3 40 55 85 29 158 105 115 281 320 10	144
4	15 4 67 20 85 12 345 9 234 115 190 47 5 17 23 89 130	156
5	4 0 100 20 31 49	200

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); int k = in.nextInt();
		// массивы для времени каждого мероприятия и потраченного времени;
		int[] stairs= new int[n + 1]; int[] time= new int[n + 1]; 
		for(int i = 1; i < n + 1; ++i) {
			stairs[i] = in.nextInt(); 
			if (i <= k + 1) time[i] = stairs[i];
		}
		time[0] = 0; 
		for(int i = 2; i <= n; ++i) {
			if (i > k + 1) time[i] = time[i - 1] + stairs[i]; //начальный минимум;
			for(int j = 2; j <= k+1; ++j) {
				// выбор минимально затраченного времени;
				if (i - j >= 0) time[i] =  Math.min(time[i - j] + stairs[i], time[i]); 
			}
		}
	System.out.println(time[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(); int k = in.nextInt();

// массивы для времени каждого мероприятия и потраченного времени;

int[] stairs= new int[n + 1]; int[] time= new int[n + 1];

for(int i = 1; i < n + 1; ++i) {

stairs[i] = in.nextInt();

if (i <= k + 1) time[i] = stairs[i];

}

time[0] = 0;

for(int i = 2; i <= n; ++i) {

if (i > k + 1) time[i] = time[i - 1] + stairs[i]; //начальный минимум;

for(int j = 2; j <= k+1; ++j) {

// выбор минимально затраченного времени;

if (i - j >= 0) time[i] = Math.min(time[i - j] + stairs[i], time[i]);

}

System.out.println(time[n]);

}

Решение

Для каждой ступеньки будем считать минимальное время, которое она отнимет у эльфа, учитывая сколько ступенек можно пропустить (от $0$ до $k + 1$). То есть будем прыгать со ступенек пониже (если это возможно) и сравнивать значения на каждой. Под значением подразумевается сумма уже найденного значения на более низкой ступеньке и времени, которое отнимет мероприятие $i$-ой ступеньки. Таким образом мы узнаем, какие ступеньки выгодно перепрыгнуть. $0$-я ступенька займет $0$ минут, так как эльф не потратит время. Изначально за минимум на ступеньках до $k + 1$ включительно можно взять время мероприятия соответствующей ступеньки, для остальных — сумму значения предыдущей ступеньки и времени мероприятия данной ступеньки. В случае, если эти значения не минимальные, они заменятся на подходящие.
Ответом будет значение на последней ступеньке, так как к ней будет проложен путь, который «займет» минимум времени эльфа на развлечения.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

e-olymp 806. Платформы — 3

21/09/2020 by Мария Жаркая

Задача

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_{2} — y_{1}|^2$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3|y_{3} -y_{1}|^2$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней).

Входные данные

Первая строка содержит количество платформ $n$ $(2 \leqslant n \leqslant 10^5)$, вторая — $n$ целых чисел, значения которых не превышают по модулю $4000$ — высоты платформ.

Выходные данные

Выведите единственное целое число — искомую величину энергии.

Тесты

№	Входные данные	Выходные данные
1	4 1 2 3 30	731
2	4 0 1 6 8	40
3	8 1 15 16 23 42 10 84 5	828
4	7 57 54 -55 -34 21 88 -100	55189
5	7 -4000 4000 -4000 4000 -4000 4000 -4000	0

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); long j, sj, bj; // цены прыжка, суперприема и 3-го типа прыжка
		int[] platforms = new int [n]; 
		long[] energy = new long[n]; // создаем массивы для платформ и энергии
		for (int i = 0; i < n; ++i) platforms[i] = in.nextInt(); //считываем высоты платформ
		energy[0] = 0; 
		for (int i = 1; i < n; ++i) {
			// обычный прыжок
			j = (platforms[i] - platforms[i-1]) * (platforms[i] - platforms[i-1]);
			// 3-й тип прыжка
			if (i != n-1) bj = (platforms[i] - platforms[i+1]) * (platforms[i] - platforms[i+1]) + 
			3 * (platforms[i+1] - platforms[i-1]) * (platforms[i+1] - platforms[i-1]);
			else bj = j;
			// суперприём
			if (i == 1) sj = Math.max(j, bj);
			else sj = 3 * (platforms[i] - platforms[i-2]) * (platforms[i] - platforms[i-2]);
			if (i == n-1) bj = Math.max(j, sj);
			//количество энергии на i-й платформе
			if (i == 1) energy[i] = Math.min(energy[i-1] + bj, energy[i-1] + j);
			else energy[i] = Math.min(energy[i-1] + bj, Math.min(energy[i-1] + j, energy[i-2] + sj));
		}
		System.out.println(energy[n-1]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(); long j, sj, bj; // цены прыжка, суперприема и 3-го типа прыжка

int[] platforms = new int [n];

long[] energy = new long[n]; // создаем массивы для платформ и энергии

for (int i = 0; i < n; ++i) platforms[i] = in.nextInt(); //считываем высоты платформ

energy[0] = 0;

for (int i = 1; i < n; ++i) {

// обычный прыжок

j = (platforms[i] - platforms[i-1]) * (platforms[i] - platforms[i-1]);

// 3-й тип прыжка

if (i != n-1) bj = (platforms[i] - platforms[i+1]) * (platforms[i] - platforms[i+1]) +

3 * (platforms[i+1] - platforms[i-1]) * (platforms[i+1] - platforms[i-1]);

else bj = j;

// суперприём

if (i == 1) sj = Math.max(j, bj);

else sj = 3 * (platforms[i] - platforms[i-2]) * (platforms[i] - platforms[i-2]);

if (i == n-1) bj = Math.max(j, sj);

//количество энергии на i-й платформе

if (i == 1) energy[i] = Math.min(energy[i-1] + bj, energy[i-1] + j);

else energy[i] = Math.min(energy[i-1] + bj, Math.min(energy[i-1] + j, energy[i-2] + sj));

}

System.out.println(energy[n-1]);

}

Решение

Чтобы решить задачу, мы создадим массив $energy$, где будем хранить минимальную энергию, которую герой потратит для прыжка на очередную $i$-ю платформу. Для этого необходимо для каждой платформы, начиная со второй, рассмотреть три вида прыжка:

прыжок с предыдущей $i — 1$ платформы.
суперприём, то есть прыжок c $i — 2$ платформы.
3-й вид: суперприём с $i — 1$ платформы на $i + 1$ и прыжок назад на $i$.

«Цены» за обычный прыжок и суперприём мы можем найти из формул данных в условии, с 3-м же сложнее — результатом будет сумма «цены» суперприёма $3(y_{i+1} — y_{i-1})^2$ и «цены» прыжка назад $(y_{i} — y_{i+1})^2$.

Для понимания схемы можно рассмотреть в качестве примера второй тест.
Синим обозначен 3-ий тип. Красными цифрами — весь путь.

второй тест

Каждый из 3-х путей даст своё значение энергии, равное сумме «цены» прыжка на $i$-ю платформу и значения в той, из которой герой совершил прыжок. Наименьшей энергией для этой платформы будет минимум из этих трех значений.
На второй платформе $(i = 1)$ в случае суперприёма мы выходим за границы массива и получаем независимое значение, поэтому эффективнее будет в качестве «цены» выбирать максимум из двух других уже найденных значений. Аналогично на последней $(i = n — 1)$ и 3-м типе прыжка, максимум будет невыгодным и соответственно не будет выбран как минимум в $energy_{i}$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

java@Cat

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

Author Archives: Мария Жаркая

e-olymp 4020. Культ-орки на лестнице

Задача

Входные данные:

Выходные данные:

Тесты

Код программы

Решение

Ссылки

e-olymp 806. Платформы — 3

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки