e-olymp 2662. Метод минимума

20/11/2020 by Виктория Крачилова

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

Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?

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

Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.

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

Вывести количество перемещений первого элемента.

Тесты

№	Ввод	Вывод
1	3 1 3 2	0
2	2 2 1	1
3	4 4 1 5 3	3
4	6 23 5 56 2 87 3	1
5	7 15 1 6 3 9 8 13	4

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner in = new java.util.Scanner(System.in);
		int n = in.nextInt();
		int []x = new int [n];
	    int counter = 0; // количество перемещений
	    for (int i = 0; i < n; i++){
	        x[i] = in.nextInt();
	    }
	    int first = x[0]; // первый по порядку элемент
	    for (int i = 0; i < n - 1; i++) {
	        int min = i; // индекс минимального элемента
	        for (int j = i + 1; j < n; j++) {
	            if (x[j] < x[min]) min = j;
	        }
	        if((x[i] == first || x[min] == first) && x[i] != x[min]) counter ++;
	        int t = x[i];
		    x[i] = x[min];
		    x[min] = t;
	    }
    	System.out.print(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

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

int n = in.nextInt();

int []x = new int [n];

int counter = 0; // количество перемещений

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

x[i] = in.nextInt();

}

int first = x[0]; // первый по порядку элемент

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

int min = i; // индекс минимального элемента

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

if (x[j] < x[min]) min = j;

}

if((x[i] == first || x[min] == first) && x[i] != x[min]) counter ++;

int t = x[i];

x[i] = x[min];

x[min] = t;

}

System.out.print(counter);

}

Решение

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

Подробное изложение алгоритма сортировки можно найти в этой статье .

Ссылки

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-olymp 595. Новый Лабиринт Амбера

27/12/2018 by Даниель Савчак

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

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].

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

В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.

Тесты

№	Входные данные	Выходные данные
1	5 1000 2 3 1 3	6
2	2 1 2	2
3	4 1 3 100 0	3

Решение с использованием цикла

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		int[] dp = new int [n+1];
		for(int i = 1; i<=n; ++i){
        		dp[i] = in.nextInt();
		}
		dp[0] = 0;
		dp[1] = 0;
		for(int i = 2; i<=n; ++i){
    		if(i - 3 >= 0)
        		dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);
		}
		System.out.print(dp[n]);
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

int[] dp = new int [n+1];

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

dp[i] = in.nextInt();

}

dp[0] = 0;

dp[1] = 0;

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

if(i - 3 >= 0)

dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);

}

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

}

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.

Код на ideone.com.

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

e-olymp 1281. Простая задачка Шарика

27/12/2018 by Дима Мороз

Задача

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

«Сколько разных последовательностей длины $n$ можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд«?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

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

Длина последовательности $n (n ≤ 64)$.

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

Вывести количество указанных последовательностей.

Тесты

Входные данные	Выходные данные
1	2
2	4
3	7
4	13

Код задачи

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);
        long x1, x2, x3, x4 = 0;
        long n = in.nextLong();
        x1 = 2;
        x2 = 4;
        x3 = 7;
        for (int i = 3; i < n; i++) {
            x4 = x1 + x2 + x3;
            x1 = x2;
            x2 = x3;
            x3 = x4;    
        }
        if (n == 1) 
            System.out.println(2); 
        else if (n == 2) 
            System.out.println(4); 
        else if (n == 3)
            System.out.println(7); 
        else 
            System.out.println(x4);
    }
}

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

long x1, x2, x3, x4 = 0;

long n = in.nextLong();

x1 = 2;

x2 = 4;

x3 = 7;

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

x4 = x1 + x2 + x3;

x1 = x2;

x2 = x3;

x3 = x4;

}

if (n == 1)

System.out.println(2);

else if (n == 2)

System.out.println(4);

else if (n == 3)

System.out.println(7);

else

System.out.println(x4);

}

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

Для решения задачи воспользуемся рекуррентным соотношением $f(n)=f(n−1)+f(n−2)+f(n−3)$ $f (n) = f (n - 1) + f (n - 2) + f (n - 3)$ , где $f$ — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины $1, 2,$ и $3$ соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения $f(n)$ при $n≤3$ можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 263. Три единицы

27/12/2018 by Карина Миловская

Задача

Вычислить количество последовательностей длины $n,$ состоящих только из нулей и единиц, в которых не встречается три единицы подряд.

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

Длина последовательностей $n$ $\left ( 1 \leq n \leq 10^{5} \right ).$

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

Вывести количество искомых последовательностей по модулю $12345.$

Тесты

Входные данные	Выходные данные
$1$	$2$
$4$	$0$
$263$	$10159$
$10000$	$8872$

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

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

class Main
{
	static int MAX = 100010;
	static int f[] = new int[MAX];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		f[1] = 2; 
		f[2] = 4; 
		f[3] = 7;
		for(int i = 4; i <= n; i++) {
			f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;
		}
		System.out.println(f[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static int MAX = 100010;

static int f[] = new int[MAX];

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

f[1] = 2;

f[2] = 4;

f[3] = 7;

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

f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;

}

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

}

Решение

Объявим массив $f,$ в котором будем сохранять значения $f(1), f(2),\dots, f(n).$ Далее читаем входные данные и заносим в соответствующие ячейки массива $f$ значения $f(1), f(2)$ и $f(3).$ Вычисляем значения $f(i)$ по рекуррентной формуле $f(n) = f(n – 1) + f(n – 2) + f(n – 3).$
Эту формулу получили так: сперва обозначили через $f(n)$ количество искомых последовательностей из $0$ и $1$ длины $n.$ Далее мы смотрим, если на первом месте последовательности будет находиться $0,$ то начиная со второго места можно построить $f(n – 1)$ последовательность. Если на первом месте стоит $1,$ то на втором месте возможны оба варианта. Если там стоит $0,$ то на следующих $n – 2 $свободных местах можно построить $f(n – 2)$ последовательности. Если $1,$ то на третьем месте обязательно должен находиться $0$ и начиная с четвертого места можно построить $f(n – 3)$ последовательности.
Вычисления значения $f(i)$ производим по модулю $12345.$ В результате выводим количество искомых последовательностей по модулю.

Ссылки

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

Код решения задачи ideone

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

27/12/2018 by Андрей Лисовой

Задача

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

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

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

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

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

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

Тесты

Входные данные	Выходные данные
$4$ $3$	$10$
$5$ $5$	$70$
$4$ $8$	$120$
$10$ $10$	$48620$

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

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 m = in.nextInt();
        int n = in.nextInt();
        long[][] a = new long[m][n];
        a[m-1][0] = 1;
        for(int i = m-1; i >= 0; i--) {
            for(int j = 0; j < n; j++) {
                if(i == m-1 && j == 0) continue;
                a[i][j] = (i < m-1 ? a[i+1][j] : 0) + (j > 0 ? a[i][j-1] : 0);
            }
        }
        System.out.print(a[0][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 m = in.nextInt();

int n = in.nextInt();

long[][] a = new long[m][n];

a[m-1][0] = 1;

for(int i = m-1; i >= 0; i--) {

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

if(i == m-1 && j == 0) continue;

a[i][j] = (i < m-1 ? a[i+1][j] : 0) + (j > 0 ? a[i][j-1] : 0);

}

System.out.print(a[0][n-1]);

}

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

Для решения задачи представим, что черепашка уже находится в правом верхнем углу поля. Начинаем движение сверху-вниз справа-налево, т.е возможные ходы черепашки только наоборот(черепашка может ходит вверх и направо). Если черепашка сместилась вниз по карте, т.e. j > 0, то прибавляем ячейке значение верхней, если черепашка сместилась налево, т.e. i < m-1, то прибавляем ячейке значение правой. Эта сумма будет накапливаться и будет равна количеству всех возможных ходов черепашки. Проходя через всю карту, попадем в левую нижнюю ячейку(старт черепашки), эта ячейка и будет содержать число возможных путей к правой верхней точки. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 44. Единицы

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

Задача

В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?

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

Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]

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

Искомое количество единиц.

Тесты

#	Входные данные	Выходные данные
1	7	6
2	22	10
3	90	13
4	157	16
5	985	21

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.lang.Math;
 
class Main
{
	public static int max = 5001;
	static int [] x = new int[max];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k;
		x[1] = 1;
		x[2] = 2;
		for (int i = 3; i <= n; i++) {
			x[i] = x[i-1]+1;
			for (int j = 2; j <= Math.sqrt(n); j++) {
				if(i % j == 0) {
					k = x[j] + x[i/j];
					if( k < x[i]) x[i] = x[j] + x[i/j];
				}
			}
		}
		System.out.println(x[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

public static int max = 5001;

static int [] x = new int[max];

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k;

x[1] = 1;

x[2] = 2;

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

x[i] = x[i-1]+1;

for (int j = 2; j <= Math.sqrt(n); j++) {

if(i % j == 0) {

k = x[j] + x[i/j];

if( k < x[i]) x[i] = x[j] + x[i/j];

}

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

}

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

Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 595. Новый Лабиринт Амбера

17/12/2018 by Алиса Ворохта

Задача

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от 1 до N. Из ячейки под номером i можно попасть в ячейки под номерами $i+2$ (если $i+2 ≤ N$) и $i+3$ (если $i+3 ≤ N$). На каждой ячейке лежит какое-то количество золотых монет $k_i$. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером N. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером N, вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число $N$ $(2 ≤ N ≤ 100000)$, а во второй $N$ целых чисел, разделенных одним пробелом, $k_i$ – количество монеток лежащих в ячейке с номером $i (0 ≤ k_i ≤ 1000)$.

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

Тесты

Входные данные	Выходные данные
$5$ $1000$ $2$ $3$ $1$ $3$	$6$
$2$ $1$ $2$	$5610$
$4$ $1$ $3$ $100$ $0$	$3$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		int[] dp = new int[n + 1];
		for(int i = 1; i <= n; ++i){
			dp[i] = in.nextInt();
		}
		dp[1] = -1;
		for(int i = 3; i<=n; ++i){
			dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);
		}
		System.out.println(dp[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

int[] dp = new int[n + 1];

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

dp[i] = in.nextInt();

}

dp[1] = -1;

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

dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);

}

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

}

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив $dp$ длиной $n + 1$ элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего значение первого элемента массива делаем отрицательным, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером $i$ он может попасть или из ячейки с номером $i — 2$, или из ячейки с номером $i — 3$. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения $i$-й ячейки имеет вид $dp_i = dp_i + max\{dp_{i — 2}; dp_{i — 3}\}$, и ответ к задаче хранится в $n$-й ячейке массива.

Ссылки

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

e-olymp 4018. Черепашка

16/12/2018 by Костя Григорян

Задача

В левом верхнем углу прямоугольной таблицы размером $n × m$ находится черепашка. На каждой клетке таблицы разлито некоторое количество кислоты. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

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

В первой строке записаны два натуральных числа $n$ и $m$, не превосходящие $1000$ — размеры таблицы. Далее идёт $n$ строк, каждая из которых содержит $m$ чисел, разделённых пробелами — описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).

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

Вывести минимальную возможную стоимость маршрута черепашки.

Тесты

Входные данные	Выходные данные
[latex]3 \ 4[/latex]	[latex]35[/latex]
[latex]5 \ 9 \ 4 \ 3[/latex]
[latex]3 \ 1 \ 6 \ 9[/latex]
[latex]8 \ 6 \ 8 \ 12[/latex]
[latex]1 \ 1[/latex]	[latex]1[/latex]
[latex]1[/latex]
[latex]5 \ 6[/latex]	[latex]25[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]4 \ 1[/latex]	[latex]103[/latex]
[latex]100[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1 \ 5[/latex]	[latex]7[/latex]
[latex]1 \ 1 \ 2 \ 2 \ 1[/latex]

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main
{
	public static void main (String[] args) throws Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String[] params1 = bufferedReader.readLine().split(" ");
		int n = Integer.parseInt(params1[0]);
		int m = Integer.parseInt(params1[1]);
		int[][] A = new int[n][m];
		for (int i=0; i<n; i++)	{
	        String[] params2 = bufferedReader.readLine().split(" ");
			for (int j=0; j<m; j++)	{
				A[i][j] = Integer.parseInt(params2[j]);
			}
		}
		for (int i=1; i<n; i++)	{
			A[i][0]+=A[i-1][0];
		}
		for (int i=1; i<m; i++)	{
			A[0][i]+=A[0][i-1];
		}
		for (int i=1; i<n; i++)	{
			for (int j=1; j<m; j++) {
				A[i][j]+=Math.min(A[i-1][j],A[i][j-1]);
			}
		}
		System.out.println(A[n-1][m-1]);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int n = Integer.parseInt(params1[0]);

int m = Integer.parseInt(params1[1]);

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

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

String[] params2 = bufferedReader.readLine().split(" ");

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

A[i][j] = Integer.parseInt(params2[j]);

}

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

A[i][0]+=A[i-1][0];

}

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

A[0][i]+=A[0][i-1];

}

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

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

A[i][j]+=Math.min(A[i-1][j],A[i][j-1]);

}

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

}

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

Для начала посчитаем значение для каждой клетки $0$-ой строки и $0$-ого столбца. Далее, для каждой клетки $\left (i, j \right )$, где $i > 0$ и $j > 0$, считаем значение клетки как сумму значения, лежащего в этой клетке и минимум из пути, откуда черепашка могла прийти (т. е. минимум из клетки $\left (i-1, j \right )$ и клетки $\left (i, j-1 \right )$). Ответом будет значение, лежащее в клетке $\left (n-1, m-1 \right ).$
Для считывания данных использовался BufferedReader, а не Scanner, так как Scanner работает дольше и из-за этого проходит не все тесты.

Ссылки

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