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

А410е

27/12/2018 by Антон Джашимов

Задача

Дана целочисленная матрица $ [a_{ij}], ij=1,\ldots,n.$ Получить $b_{1} \dots b_{n},$ где $b_{i}$ — это $\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}$

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

Первая строка содержит число $n.$ Следующие строки содержат матрицу $n\times n.$

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

Вывести $b_i \; i=1\dots n.$

Тесты

Входные данные	Выходные данные
2 1 2 4 1	2 4
3 1 2 3 4 1 -6 1 -2 -1	3 -8 -6

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

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,maxa,mina;
		n=in.nextInt();
		int a[][];
		a = new int[n][];
    	for (int i = 0 ;i < n ; i++) {
			a[i] = new int [n];
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				a[i][j]=in.nextInt();
			}
		}
		int b[]= new int[n];
		for(int i=0;i<n;++i){
        	maxa=a[i][0]; //Присваиваем максимуму значение первого элемента i-й строки.
        	mina=a[0][i]; //Минимуму присваиваем значение первого элемента i-го столбца.
        	for(int j=0;j<n;++j){
            	maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.
            	mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.
        	}
        	b[i]=maxa*mina;
    	}
    	for(int i=0;i<n;++i){
        	System.out.print(b[i]);
			System.out.print(" ");
    	}
	}
}

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,maxa,mina;

n=in.nextInt();

int a[][];

a = new int[n][];

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

a[i] = new int [n];

}

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

for(int j=0;j<n;j++){

a[i][j]=in.nextInt();

}

int b[]= new int[n];

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

maxa=a[i][0]; //Присваиваем максимуму значение первого элемента i-й строки.

mina=a[0][i]; //Минимуму присваиваем значение первого элемента i-го столбца.

for(int j=0;j<n;++j){

maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.

mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.

}

b[i]=maxa*mina;

}

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

System.out.print(b[i]);

System.out.print(" ");

}

Решение

Очевидно, что из заданной матрицы нужно взять максимальный элемент $i$-й строки и умножить его на минимальный элемент $i$-го столбца. Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем присваивать ей начальное значение первого элемента $i$-й строки. Чтобы при расчете максимума проходя по элементам строки мы не сравнивали каждый $i$-й элемент с первым, присваивать начальное значение максимуму будем в цикле по $i$. Аналогично с минимумом, но начальное значение минимума будет равно первому элементу $i$-го столбца.

Ссылки

Условие задачи
Код решения

e-olymp 7612. Алекс и квадраты оригами

20/12/2018 by Саша Рябова

Задача

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

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

В одной строке два целых числа $h$ и $w$ $(1 \leq h,w\leq 1000)$ — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером $h \times w$ так, чтобы их стороны были параллельны сторонам листа.

Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные	Выходные данные
$100$ $100$	$50.000$
$10$ $80$	$10.000$
$50$ $76$	$25.333$
$60$ $27$	$20.000$
$8$ $3$	$2.667$

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

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		double h = sc.nextDouble();
		double w = sc.nextDouble();
    	double b = Math.max(h, w);
    	double a = Math.min(w, h);
    	double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));
    	System.out.printf("%.4f", c);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner sc = new Scanner(System.in);

double h = sc.nextDouble();

double w = sc.nextDouble();

double b = Math.max(h, w);

double a = Math.min(w, h);

double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));

System.out.printf("%.4f", c);

}

Решение задачи

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за $a$ меньшую сторону листа бумаги, а за $b$ — большую. Если a не больше $\frac{b}{3}$, то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги $a$. В противном случае рассмотрим два варианта:

Если $\frac{a}{2} < \frac{b}{3}$, то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число $\frac{a}{2}$.
Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число $\frac{b}{3}$.

Таким образом, в случае $a > \frac{b}{3}$ ответом будет служить большее из двух чисел $\frac{a}{2}$ и $\frac{b}{3}$. Mинимальное из $\max \left(\frac{a}{2},\frac{b}{3} \right)$ и $a$ число и будет ответом.
Проверим нашу формулу:если $a < \frac{b}{3}$, то $\max \left(\frac{a}{2},\frac{b}{3} \right) = \frac{b}{3}$, и тогда $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = a$. Иначе $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = \max \left(\frac{a}{2},\frac{b}{3}\right)$, что нам и требуется.

Ссылки

Условие задачи на сайте e-olymp
Код решения

e-olymp 7368. Средний балл для фигуристов

09/12/2018 by Валерия Ларикова

Задача

Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n \leqslant 10, 0 < m \leqslant 100)[/latex] для каждого из фигуристов.

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

В одной строке вывести [latex]m[/latex] чисел с точностью до двух десятичных знаков — балл каждого спортсмена.

Тесты

#	Входные данные	Выходные данные
1	5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8	8.33 5.33 9.00 8.50
2	6 3 6 7 6 5 4 3 9 8 5 5 6 5 7 6 4 1 2 2	5.25 7.00 3.50
3	4 5 6 7 8 6 9 8 5 4 7 6 7 5 4 3 9 3 7 8 7 6	7.00 6.50 6.00 4.00 7.00
4	4 4 7 7 2 3 9 8 3 3 5 4 9 7 4 3 2 6	3.00 8.00 6.00 3.50
5	8 5 4 5 6 7 7 4 9 8 3 5 6 6 7 8 5 9 7 6 3 9 3 7 9 7 5 6 4 3 7 7 5 7 9 8 4 6 7 9 9 4	6.60 6.17 6.75 5.00 7.00

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

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

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    double n, m;
    double x, min = 100, max = -100, sum = 0, a = 0, b = 0;
    Scanner in = new Scanner(System.in);
    n = in.nextDouble();
    m = in.nextDouble();
    for (int i = 0; i < m; i++){
      for (int j = 0; j < n; j ++){
        x = in.nextDouble();
        if (max == x) a++;
        if (max < x) {
          if (max != min) sum += a*max;
          a = 1;
          max = x;
        }
        if ( min == x) b++;
        if (min > x) {
          if (max != min) sum += b*min;
          b = 1;
          min = x;
        }
      if (x!= min && x != max) sum += x;
      }
      if(i == m-1) System.out.printf("%.2f", sum / (n - a - b));
      else System.out.printf("%.2f ", sum / (n - a - b));
      sum = a = b = 0;
      min = 100;
      max = -100;
    }
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

double n, m;

double x, min = 100, max = -100, sum = 0, a = 0, b = 0;

Scanner in = new Scanner(System.in);

n = in.nextDouble();

m = in.nextDouble();

for (int i = 0; i < m; i++){

for (int j = 0; j < n; j ++){

x = in.nextDouble();

if (max == x) a++;

if (max < x) {

if (max != min) sum += a*max;

a = 1;

max = x;

}

if ( min == x) b++;

if (min > x) {

if (max != min) sum += b*min;

b = 1;

min = x;

}

if (x!= min && x != max) sum += x;

}

if(i == m-1) System.out.printf("%.2f", sum / (n - a - b));

else System.out.printf("%.2f ", sum / (n - a - b));

sum = a = b = 0;

min = 100;

max = -100;

}

Решение задачи

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x,[/latex] и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n — a — b.[/latex] А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\displaystyle\frac{sum}{n — a — b}[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone