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 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 8352. Такси

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

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

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

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

Три натуральных числа, не превосходящих $100$ — количество пассажиров в первой, второй и третьей маршрутках соответственно.

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

Выведите одно число — наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово IMPOSSIBLE (заглавными буквами).

Тесты

№	Ввод	Вывод
1	1 2 3	1
2	6 7 4	IMPOSSIBLE
3	18 10 2	8
4	54 10 96	IMPOSSIBLE
5	27 27 27	0

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int b1 = i.nextInt();
		int b2 = i.nextInt();
		int b3 = i.nextInt();
		if ((b1 + b2 + b3) % 3 != 0) {
			System.out.println("IMPOSSIBLE");
		}
		else {
			int average; // среднее арифметическое
			int count = 0; // наименьшее количество пассажиров, которое требуется пересадить
			average = (b1 + b2 + b3) / 3;
			if (b1 > average) count += b1 - average;
			if (b2 > average) count += b2 - average;
			if (b3 > average) count += b3 - average;
			System.out.println(count);
		}
	}
}

class Main

{

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

{

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

int b1 = i.nextInt();

int b2 = i.nextInt();

int b3 = i.nextInt();

if ((b1 + b2 + b3) % 3 != 0) {

System.out.println("IMPOSSIBLE");

}

else {

int average; // среднее арифметическое

int count = 0; // наименьшее количество пассажиров, которое требуется пересадить

average = (b1 + b2 + b3) / 3;

if (b1 > average) count += b1 - average;

if (b2 > average) count += b2 - average;

if (b3 > average) count += b3 - average;

System.out.println(count);

}

Решение

Мы сможем рассадить пассажиров поровну в три маршрутки только тогда, когда их общее количество кратно трем. Если это условие не выполняется, выводим на экран слово IMPOSSIBLE.

Иначе вычисляем среднее арифметическое исходного количества пассажиров каждой маршрутки по формуле: $\frac{b_{1}+b_{2}+b_{3}}{3}$ и находим минимальное количество пересаживаемых пассажиров, суммируя только положительные отклонения от среднего арифметического.

java@Cat

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

Author Archives: Виктория Крачилова

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

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

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

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

Тесты

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

Решение

Ссылки

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

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

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

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

Тесты

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

Решение

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

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

Решение

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

e-olymp 8352. Такси

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

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

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

Тесты

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

Решение

Ссылки