e-olimp 8536. Заповнення смуги $3 \times n$

02/12/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

import java.util.Scanner;

class Main {
	public static void main (String[] args) {
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	    int[] F = new int[51];
	    F[0] = 0;
	    F[1] = 1;
	    F[2] = 1;
	    F[3] = 2;
	    F[4] = 3;
	    for(int i = 5; i <= n; i++) {
	       F[i] = F[i-2] + F[i-3] + F[i-4];
	    }
	    System.out.println(F[n]);
	}
}

import java.util.Scanner;

class Main {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] F = new int[51];

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

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

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

import java.util.Scanner;

public class Main {
	public static int[] F = new int[51];
	public static int numberOfWays(int n){
		F[0] = 0;
		F[1] = 1;
		F[2] = 1;
		F[3] = 2;
		F[4] = 3;
	    if(F[n] > 0) {
    		return F[n];
		} else {
    		F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
		}
		return F[n];
	}
	public static void main (String[] args){
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	    System.out.println(numberOfWays(n));
	}
}

import java.util.Scanner;

public class Main {

public static int[] F = new int[51];

public static int numberOfWays(int n){

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

if(F[n] > 0) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

public static void main (String[] args){

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

System.out.println(numberOfWays(n));

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

e-olymp 798. Платформы

02/12/2020 by Анна Цивинская

Условие

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

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

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

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

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

В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

Тесты

№	Ввод	Вывод
1	4 1 2 3 30	29 4 1 2 3 4
2	2 7 23	16 2 1 2
3	5 0 1 0 1 0	0 3 1 3 5

Код

import java.util.Scanner;

class Main{
	public static void main (String[] args) {
		final int MAX = 100001;
		Scanner sc = new Scanner(System.in);
        int amount_of_pltf = sc.nextInt();
        int[] energy, platforms,  list_of_pltf;
        int[] heights = new int[MAX];
        for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();
        
        energy = new int[MAX];
        platforms = new int[MAX];
        energy[1] = 0;
    	energy[2] = Math.abs(heights[2] - heights[1]);
    	platforms[1] = -1;
    	platforms[2] = 1;
    	
    	//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
	    for (int j = 3; j <= amount_of_pltf; j++){
	        if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){
	            energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);
	            platforms[j] = j - 1;
	        } else {
	            energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);
	            platforms[j] = j - 2;
	        }
	    }
	    
	    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
	    int final_amount = 0;
	    list_of_pltf = new int[MAX];
	    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
	    
    	System.out.println(energy[amount_of_pltf] + "\n" + final_amount);
	    for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");
	}
}

import java.util.Scanner;

class Main{

public static void main (String[] args) {

final int MAX = 100001;

Scanner sc = new Scanner(System.in);

int amount_of_pltf = sc.nextInt();

int[] energy, platforms, list_of_pltf;

int[] heights = new int[MAX];

for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();

energy = new int[MAX];

platforms = new int[MAX];

energy[1] = 0;

energy[2] = Math.abs(heights[2] - heights[1]);

platforms[1] = -1;

platforms[2] = 1;

//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)

for (int j = 3; j <= amount_of_pltf; j++){

if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){

energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);

platforms[j] = j - 1;

} else {

energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);

platforms[j] = j - 2;

}

//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.

int final_amount = 0;

list_of_pltf = new int[MAX];

for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;

System.out.println(energy[amount_of_pltf] + "\n" + final_amount);

for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");

}

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

Параллельно подсчету энергии необходимо нумеровать платформы, на которые мы прыгнули. Опять же, если «суперпрыжок» с первой на третью оказался выгоднее, чем «обычные» прыжки с первой до третей, то третья платформа окажется второй по счету, на которую мы прыгнули. Продолжая эти рассуждения мы подсчитываем нужные нам платформы.

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки

e-olymp 1704. Умная черепашка

30/09/2020 by Виктория Крачилова

Условие задачи

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

Вывести количество способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний.

Тесты

№	Ввод	Вывод
1	4 5	10
2	3 14	105
3	11 17	5311735
4	20 21	68923264410
5	30 30	30067266499541040

Код программы (циклы)

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int m = i.nextInt();
	    if (m > n){
	    	int t = n;
	    	n = m;
	    	m = t;
	    }
	    long den = 1, ways = 1; // den - знаменатель, ways - количество способов.
	    for (int j = 0; j < m - 1; j++) {
	        ways *= n + j;
	        if (ways % den == 0) {
	            ways /= den;
	            den++;
	        }
	    }
	    System.out.println(ways);
	}
}

class Main

{

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

{

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

int m = i.nextInt();

if (m > n){

int t = n;

n = m;

m = t;

}

long den = 1, ways = 1; // den - знаменатель, ways - количество способов.

for (int j = 0; j < m - 1; j++) {

ways *= n + j;

if (ways % den == 0) {

ways /= den;

den++;

}

System.out.println(ways);

}

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$. Для того, чтобы избежать больших чисел, делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

Ссылки (циклы)

Код программы (динамическое программирование)

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    // Создаем треугольную матрицу для хранения всех ответов
	    long [][]x = new long [30][];
	    for (int i = 0; i < 30; ++i) x[i] = new long[i+1];
	    // Находим все ответы
	    x[0][0] = 1;
	    for (int i = 1; i < 30; ++i) {
	        x[i][0] = 1;
	        for (int j = 1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];
	        x[i][i] = 2 * x[i][i-1];        
	    }
	    // Проходим все тесты
	    java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int m = i.nextInt();
	    System.out.println(x[Math.max(n,m)-1][Math.min(n,m)-1]);
	}
}

class Main

{

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

{

// Создаем треугольную матрицу для хранения всех ответов

long [][]x = new long [30][];

for (int i = 0; i < 30; ++i) x[i] = new long[i+1];

// Находим все ответы

x[0][0] = 1;

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

x[i][0] = 1;

for (int j = 1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];

x[i][i] = 2 * x[i][i-1];

}

// Проходим все тесты

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

int m = i.nextInt();

System.out.println(x[Math.max(n,m)-1][Math.min(n,m)-1]);

}

Решение

Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.

Ссылки (динамическое программирование)

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

e-olimp 7848. Переставить соседние

20/09/2020 by Елизавета Савицкая

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

Тесты

Входные данные	Выходные данные
7 3 5 -7 7 5 -9 -4	5 3 7 -7 -9 5 -4
8 -9 81 27 -38 2 6 -56 -21	81 -9 -38 27 6 2 -21 -56
2 25 -76	-76 25
3 55 44 33	44 55 33
1 99	99

Код

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int arr[] = new int[n];
		for(int k = 0; k < n; k++){
        	arr[k] = i.nextInt();
		} 
    	for(int k = 1; k < n; k+=2){
        	int q = arr[k];
        	arr[k] = arr[k-1];
        	arr[k-1] = q;
		}
		for(int k = 0; k < n; k++){
    		System.out.print(arr[k] + " ");
		}
	}
}

class Main{

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

int arr[] = new int[n];

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

arr[k] = i.nextInt();

}

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

int q = arr[k];

arr[k] = arr[k-1];

arr[k-1] = q;

}

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

System.out.print(arr[k] + " ");

}

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olimp 8234. Сходинки

20/09/2020 by Елизавета Савицкая

Задача

Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

Вхідні дані

Одне число $n$ — номер сходинки $(n \leqslant 60)$.

Вихідні дані

Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

Тести

Вхідні дані	Вихідні дані
0	1
5	13
15	5768
32	181997601
60	4680045560037375

Код № 1

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		long array[] = new long[61];
		array[0] = 1;
    	array[1] = 1;
    	array[2] = 2;
    	for(int k = 3; k <= n; k++) {
        	array[k] = array[k-1] + array[k-2] + array[k-3];
		}
		System.out.print(array[n]);
	}
}

class Main{

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

long array[] = new long[61];

array[0] = 1;

array[1] = 1;

array[2] = 2;

for(int k = 3; k <= n; k++) {

array[k] = array[k-1] + array[k-2] + array[k-3];

}

System.out.print(array[n]);

}

Рішення

Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

Код № 2

public class Main{
	public static long array[] = new long[61];
    public static long num_of_ways(int n){
		if(array[n] == 0) {
			array[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);
        	return array[n];
    	}
		else {
        	return array[n];
    	}
	}
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		array[0] = 1;
    	array[1] = 1;
    	array[2] = 2;
		System.out.print(num_of_ways(n));
	}
}

public class Main{

public static long array[] = new long[61];

public static long num_of_ways(int n){

if(array[n] == 0) {

array[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);

return array[n];

}

else {

return array[n];

}

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

array[0] = 1;

array[1] = 1;

array[2] = 2;

System.out.print(num_of_ways(n));

}

Посилання

Умова задачі на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

e-olimp 9536. Сумма матриц

20/09/2020 by Елизавета Савицкая

Задача

Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

Тесты

Входные данные	Выходные данные
1 1 2 3	5
1 5 4 3 7 2 1 3 2 2 1 6	7 5 9 3 7
2 2 0 4 2 3 5 4 1 6	5 8 3 9
3 4 3 4 5 6 1 2 3 4 7 6 5 4 0 0 -3 -2 -1 3 4 5 5 6 1 2	3 4 2 4 0 5 7 9 12 12 6 6
3 3 2 -128 47 -365 5 56 243 42 12 678 43 76 4 345 -23 97 -453 18	680 -85 123 -361 350 33 340 -411 30

Код

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int m = i.nextInt();
		int array1[][] = new int[n][m];
		int array2[][] = new int[n][m];
		int array_sum[][] = new int[n][m];
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array1[k][j] = i.nextInt();
    		}
		}
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array2[k][j] = i.nextInt();
    		}
		}
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array_sum[k][j] = array1[k][j] + array2[k][j];
        		System.out.print (array_sum[k][j] + " ");
    		}
    		System.out.println();
		}
	}
}

class Main{

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

int m = i.nextInt();

int array1[][] = new int[n][m];

int array2[][] = new int[n][m];

int array_sum[][] = new int[n][m];

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

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

array1[k][j] = i.nextInt();

}

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

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

array2[k][j] = i.nextInt();

}

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

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

array_sum[k][j] = array1[k][j] + array2[k][j];

System.out.print (array_sum[k][j] + " ");

}

System.out.println();

}

Решение

Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olymp 399. Последствия гриппа в Простоквашино

19/09/2020 by Никита Репнин

Задача

”Дорогой дядя Фёдор!

После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!

Я сначала обрадовался, так как помню, что из шахматной доски он не мог выпилить больше 64-х квадратиков. Но скоро понял, что я глубоко ошибался.

Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

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

В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

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

Вывести в $n$ строках по одному числу – ответ на соответствующее задание Шарика.

Тесты

№	Входные данные	Выходные данные
1	3 2 3 4	1 0 2
2	5 3 11 7 43 27	0 0 0 0 0
3	6 2 28 42 14 64 0	1 2674440 24466267020 429 55534064877048198 1

Код

import java.util.Scanner;

class Main{
	public static void main (String[] args) throws java.lang.Exception{
		Scanner in = new Scanner(System.in);
		int n, k;
		long[] brackets = new long[33];
		brackets[0] = 1;
		for(int i = 1; i <= 32; ++ i){
			brackets[i] = 0;
			for(int j = 0; j < i; ++ j){
				brackets[i] += brackets[j] * brackets[i - 1 - j];
			}
		}
		n = in.nextInt();
    	        for (int i = 0; i < n; i ++) {
			k = in.nextInt();
			System.out.println(k % 2 == 0 ? brackets[k / 2] : 0);
		}
	}
}

import java.util.Scanner;

class Main{

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

Scanner in = new Scanner(System.in);

int n, k;

long[] brackets = new long[33];

brackets[0] = 1;

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

brackets[i] = 0;

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

brackets[i] += brackets[j] * brackets[i - 1 - j];

}

n = in.nextInt();

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

k = in.nextInt();

System.out.println(k % 2 == 0 ? brackets[k / 2] : 0);

}

Решение

Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

Задача на e-olymp
Код программы на ideone
Засчитанное решение

e-olymp 9410. Студенческая любовь

18/09/2020 by Дмитрий Воротов

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношения. Коэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

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

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

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

Выведите одно число — ответ на задачу.

Тесты

№	Входные данные	Выходные данные
1	2 -3 -5 3 5	0
2	1 5 -2	0
3	5 -5 -2 -1 0 4 5 4 0 0 -1	4
4	9 1000 -22 333 -56 1 2 -77 -650 10 -7 166 -333 90 -565 12 788 -800 111	523

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

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

class Main
{
	public static void main(String[] args) throws java.lang.Exception {
	    Scanner in = new Scanner(System.in);
    	PrintWriter out = new PrintWriter(System.out);
	    int n;
	    n = in.nextInt();
	    int[] a = new int[n];
	    int[] b = new int[n];
	    for (int i = 0; i < n; i ++) a[i] = in.nextInt(); // Считываем массивы
	    for (int i = 0; i < n; i ++) b[i] = in.nextInt();  
	    Arrays.sort(a);// Сортируем массивы
	    Arrays.sort(b);// Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке
	    for (int i = 0; i < n; i ++) a[i] += b[n - i - 1];  // Суммируем элементы
	    int maxa = a[0], mina = a[0];
	    for (int i = 0; i < n; i ++) {
	        maxa = Math.max(maxa, a[i]);    // Находим минимальный и максимальный элементы
	        mina = Math.min(mina, a[i]);     
	    }
		out.println(maxa - mina);// Разность минимального и максимального и будет самым маленьким индексом любви 
		out.flush();
	}
}

import java.util.*;

import java.io.*;

class Main

{

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

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n;

n = in.nextInt();

int[] a = new int[n];

int[] b = new int[n];

for (int i = 0; i < n; i ++) a[i] = in.nextInt(); // Считываем массивы

for (int i = 0; i < n; i ++) b[i] = in.nextInt();

Arrays.sort(a);// Сортируем массивы

Arrays.sort(b);// Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке

for (int i = 0; i < n; i ++) a[i] += b[n - i - 1]; // Суммируем элементы

int maxa = a[0], mina = a[0];

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

maxa = Math.max(maxa, a[i]); // Находим минимальный и максимальный элементы

mina = Math.min(mina, a[i]);

}

out.println(maxa - mina);// Разность минимального и максимального и будет самым маленьким индексом любви

out.flush();

}

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

Условие задачи e-olymp

Код решения ideone