e-olymp 84. Transfer

20/11/2018 by Костя Григорян

Task

Vasya has one package of mobile phone operator Ratsviyk and $S_0$ tugriks on its account. (Tugrik is the currency in Vasya’s country. $0.01$ of tugrik is a cent). Also he has $n$ packages of Eciujd which is the satellite of Ratsviyk. There are $S_i$ tugriks on the account of the $i$-th package of Eciujd. There was a new tariff plan on Ratsviyk and Vasya want to go into it. For this purpose it is necessary to have at least $S$ tugriks on the account. Vasya hasn’t any money, that is why he don’t want to buy new bill replenishment, to fill up the Ratsviyk account to the necessary sum. But the escape exists.
On Ratsviyk there is such possibility as to transfer money between each others. The transfer is the sending of some money from one account to another. It is possible to send only an integer amounts of tugriks, not smaller than $5$. The cost of the transfer is $10$ cents which is draw from the account from which money was sended. Transfer can be made only if after it on the account remains at least $5$ tugriks. Since Eciujd is the satellite of Ratsviyk, then subscribers of Eciujd also can participate in this transfers.
Giving $S_0, S, n, S_i (1 \leq i \leq n)$ find whether it is possible to go into new tariff plan without buying new bill replenishment and if so find the minimum number of transfers needed for this.

Input

In the first line of input there is an integer $n (0 \leq n \leq 1000), S_0$ and $S$. In the second line are written down through a blank numbers $S_1, S_2,$…$,S_n$. All numbers $S, S_i (0 \leq i \leq n)$ — real numbers from the interval $[0.01, 10000.00]$ with exactly with two digits after a decimal point.

Output

Output the minimum number of transfers needed to go into new tariff plan or $-1$ if it is impossible without buying a new bill replenishment.

Tests

Input	Output
[latex]2\, 10.00\, 16.00[/latex]	[latex]2[/latex]
[latex]10.10\, 6.10[/latex]
[latex]3\, 100.00\, 50.00[/latex]	[latex]0[/latex]
[latex]2.00\, 19.05\ 30.20[/latex]
[latex]3\ 10.00\ 14.00[/latex]	[latex]-1[/latex]
[latex]2.00\ 10.05\ 10.00[/latex]
[latex]2\ 142.10\ 143.00[/latex]	[latex]2[/latex]
[latex]6.05\ 7.00[/latex]

Code

import java.util.Scanner;
import java.util.*;
  
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		double s0 = scanner.nextDouble();
		double s = scanner.nextDouble();
		double [] A = new double[n];
		double [] B = new double[n];
		if(s0>=s)
			System.out.println(0);
		else if(n==0)
			System.out.println(-1);
		else
		{
		    for(int i=0; i<n; i++)
		    {
		        double a = scanner.nextDouble();
		        A[i]=a;
		        B[i]=A[i];
		    }
		    Arrays.sort(B);
		    int ans=0;
		    for(int i=n-1; i>=1; i--)
		    {
		        if(B[i]>=10.1)
		        {
		            if((int)(B[i]-5.1)+s0>=s){
		                ans++;
		                System.out.println(ans);
		                System.exit(0);
		            }
		            else
		            {
		                ans++;
		                B[i-1]+=(int)(B[i]-5.1);
		            }
		        }
		        else
		        {
		            break;
		        }
		    }
		    if((B[0]>=10.1)&&((int)(B[0]-5.1)+s0>=s))
		        System.out.println(ans+1);
		    else
		    {
		        Arrays.sort(A);
		        if(s0>=10.1)
		        {
		            A[n-1]+=(int)(s0-5.1);
		            s0-=(int)(s0-5.1);
						s0-=0.1;
		            ans=1;
		            for(int i=n-1; i>=1; i--)
		            {
		                if(A[i]>=10.1)
		                {
		                    if((int)(A[i]-5.1)+s0>=s){
		                        ans++;
		                        System.out.println(ans);
		                        System.exit(0);
		                    }
		                    else
		                    {   
		                        ans++;
		                        A[i-1]+=(int)(A[i]-5.1);
		                    }
		                }
		                else
		                {
		                    break;
		                }
		            }
		            if((A[0]>=10.1)&&((int)(A[0]-5.1)+s0>=s))
		                System.out.println(ans+1);
		            else
		                System.out.println(-1);
		        }
		        else
		        	System.out.println(-1);
		    }   
		}	
	}
}

import java.util.Scanner;

import java.util.*;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

double s0 = scanner.nextDouble();

double s = scanner.nextDouble();

double [] A = new double[n];

double [] B = new double[n];

if(s0>=s)

System.out.println(0);

else if(n==0)

System.out.println(-1);

else

{

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

{

double a = scanner.nextDouble();

A[i]=a;

B[i]=A[i];

}

Arrays.sort(B);

int ans=0;

for(int i=n-1; i>=1; i--)

{

if(B[i]>=10.1)

{

if((int)(B[i]-5.1)+s0>=s){

ans++;

System.out.println(ans);

System.exit(0);

}

else

{

ans++;

B[i-1]+=(int)(B[i]-5.1);

}

else

{

break;

}

if((B[0]>=10.1)&&((int)(B[0]-5.1)+s0>=s))

System.out.println(ans+1);

else

{

Arrays.sort(A);

if(s0>=10.1)

{

A[n-1]+=(int)(s0-5.1);

s0-=(int)(s0-5.1);

s0-=0.1;

ans=1;

for(int i=n-1; i>=1; i--)

{

if(A[i]>=10.1)

{

if((int)(A[i]-5.1)+s0>=s){

ans++;

System.out.println(ans);

System.exit(0);

}

else

{

ans++;

A[i-1]+=(int)(A[i]-5.1);

}

else

{

break;

}

if((A[0]>=10.1)&&((int)(A[0]-5.1)+s0>=s))

System.out.println(ans+1);

else

System.out.println(-1);

}

else

System.out.println(-1);

}

Solution

To begin with, if we have enough money in our account, then we do not need to do anything. Otherwise, we have three options: when we can collect the required amount without manipulating the main account, when we can collect the necessary amount by manipulating the main account and when we can not collect the required amount at all.
For the first option, we will transfer the largest possible amount to smaller ones from large side accounts and check whether we can switch to a new tariff by transferring the current account amount to the main account. In cases of a positive answer, the problem is solved.
If in the end you did not manage to get the right amount, go to the second option. We simply transfer the maximum possible amount from the main account to the largest collateral account. Then we do everything the same as in the first version. In cases of a positive answer, the problem is solved.
Otherwise, you can not get the right amount.

References

The task at E-Olymp
My solution at ideone

e-olymp 8530. Печать матрицы

13/11/2018 by Александр Дяченко

Задача

Задана матрица $n \times n$ — назовем ее $[1 \ldots n] \times [1 \ldots n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1 \ldots r] \times [1 \ldots c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n \space (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \times n$. Последняя строка содержит два числа $r$ и $c \space (1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \times c$.

Тесты

Входные данные	Выходные данные
4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2	1 2 5 6 9 1
5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3	18 25 34 54 65 75 95 15 25 -4 15 -6
6 30 -10 30 -69 -84 75 -3 -39 60 15 75 -74 36 68 35 23 25 -44 16 42 83 15 59 -18 71 43 35 -81 -38 51 37 -49 55 26 6 33 4 5	30 -10 30 -69 -84 -3 -39 60 15 75 36 68 35 23 25 16 42 83 15 59

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

import java.io.*;
import java.util.*;
 
public class Main
{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
 
		int n = in.nextInt();
		int [][] x = new int [n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				x[i][j] = in.nextInt();
		int r = in.nextInt();
		int c = in.nextInt();
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++)
				out.print(x[i][j] + " ");
			out.print("\n");
		}
 
		out.flush();
	}
}

import java.io.*;

import java.util.*;

public class Main

{

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n = in.nextInt();

int [][] x = new int [n][n];

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

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

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

int r = in.nextInt();

int c = in.nextInt();

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

for (int j = 0; j < c; j++)

out.print(x[i][j] + " ");

out.print("\n");

}

out.flush();

}

Решение

Для того, чтобы вывести матрицу на экран, нам нужно запустить $2$ цикла, один из которых будет вложен в предыдущий:

первый цикл ($17$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
второй цикл ($18$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

e-olymp 2501. Круговая диаграмма

04/11/2018 by Александр Дяченко

Задача

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

Исходными данными для этой диаграммы является набор чисел $a_1,\ldots, a_n, а$ диаграмма представляет собой круг радиуса $r$, разделенный на секторы. При этом каждому из чисел соответствует ровно один сектор, площадь которого пропорциональна этому числу. Общая площадь секторов равна площади круга.

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

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

Первая строка содержит два целых числа $n$ и $r \space (1 \leq n, r \leq 100)$. Вторая строка содержит $n$ целых чисел $a_1,\ldots, a_n \space (1 \leq a_i \leq 100 \space \forall \space i = \overline{1, n})$.

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

Выведите $n$ вещественных чисел — площади секторов, соответствующих числам $a_1,\ldots, a_n$. Выводите каждое из чисел в отдельной строке.

Все эти числа должны быть выведены с точностью не хуже $10^{-6}$.

Тесты

Входные данные	Выходные данные
3 2 1 4 3	1.570796327 6.283185307 4.712388980
2 3 3 8	7.711181968 20.563151914
4 5 2 5 9 1	9.239978393 23.099945982 41.579902768 4.619989196
5 9 4 16 8 20 11	17.252135928 69.008543713 34.504271856 86.260679641 47.443373803

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

import java.io.*;
import java.util.*;
 
public class Main
{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int n = in.nextInt();
		int r = in.nextInt();
		int sum = 0;
		double S;
		int[] x = new int[n];
		for (int i = 0; i < n; i++)
			x[i] = in.nextInt();
		for (int i = 0; i < n; i++)
			sum += x[i];
		S = Math.PI * r * r;
		for (int i = 0; i < n; i++)
			out.format("%.9f%n", (S / sum) * x[i]);
		
		out.flush();
	}
}

import java.io.*;

import java.util.*;

public class Main

{

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n = in.nextInt();

int r = in.nextInt();

int sum = 0;

double S;

int[] x = new int[n];

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

x[i] = in.nextInt();

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

sum += x[i];

S = Math.PI * r * r;

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

out.format("%.9f%n", (S / sum) * x[i]);

out.flush();

}

Решение

Найдем сперва сумму всех чисел $a_i$ и площадь диаграммы (по известной формуле площади круга). Теперь можем легко посчитать площади каждого из секторов нашей диаграммы, разделив площадь последней на ранее найденную сумму и умножив их частное на соответствующее число $a_i$.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

e-olymp 88. Месть Ли Чака

15/10/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main{

    private static class Node {
        private int i;
        private int j;

        private Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    private static void fill(int[][] a, int value) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = value;
            }
        }
    }

    private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        moves[start.i][start.j] = 0;
        queue.add(start);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
    }

    private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(start);
        moves[start.i][start.j] = 0;
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (map[i][j] == 'e') {
                return true;
            }
            if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tests = Integer.parseInt(bufferedReader.readLine());
        for (int r = 0; r < tests; r++) {
            String[] sizes = bufferedReader.readLine().split(" ");
            int n = Integer.parseInt(sizes[0]);
            int m = Integer.parseInt(sizes[1]);
            char[][] map = new char[n][m];
            Node g = null;
            Node l = null;
            Node e = null;
            for (int i = 0; i < n; i++) {
                map[i] = bufferedReader.readLine().toCharArray();
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 'g') {
                        g = new Node(i, j);
                    }
                    else if (map[i][j] == 'l') {
                        l = new Node(i, j);
                    }
                    else if (map[i][j] == 'e') {
                        e = new Node(i, j);
                    }
                }
            }
            int[][] secondPlayerDistances = new int[n][m];
            fill(secondPlayerDistances, Integer.MAX_VALUE);
            bfsSecondPlayer(map, secondPlayerDistances, l);
            int[][] firstPlayerDistances = new int[n][m];
            fill(firstPlayerDistances, Integer.MAX_VALUE);
            boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);
            System.out.println(ok ? "YES" : "NO");
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

public class Main{

private static class Node {

private int i;

private int j;

private Node(int i, int j) {

this.i = i;

this.j = j;

}

private static void fill(int[][] a, int value) {

for (int i = 0; i < a.length; i++) {

for (int j = 0; j < a[i].length; j++) {

a[i][j] = value;

}

private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {

Queue<Node> queue = new LinkedList<>();

moves[start.i][start.j] = 0;

queue.add(start);

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {

Queue<Node> queue = new LinkedList<>();

queue.add(start);

moves[start.i][start.j] = 0;

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (map[i][j] == 'e') {

return true;

}

if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

return false;

}

public static void main(String[] args) throws IOException{

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

int tests = Integer.parseInt(bufferedReader.readLine());

for (int r = 0; r < tests; r++) {

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

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

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

char[][] map = new char[n][m];

Node g = null;

Node l = null;

Node e = null;

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

map[i] = bufferedReader.readLine().toCharArray();

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

if (map[i][j] == 'g') {

g = new Node(i, j);

}

else if (map[i][j] == 'l') {

l = new Node(i, j);

}

else if (map[i][j] == 'e') {

e = new Node(i, j);

}

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

fill(secondPlayerDistances, Integer.MAX_VALUE);

bfsSecondPlayer(map, secondPlayerDistances, l);

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

fill(firstPlayerDistances, Integer.MAX_VALUE);

boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);

System.out.println(ok ? "YES" : "NO");

}

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

Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. Обозначим начальное местоположение Гайбраша — $g,$ Ли Чака — $l.$, выход $e.$
Безопасный для Гайбраша маршрут существует тогда и только тогда, когда существует путь $\omega,$ такой, что для $\forall v \in \omega \ \rho \left(g, v \right ) + 1 < \rho(l, v).$ С помощью поиска в ширину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в ширину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае — нет.

Ссылки

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

e-olymp 179. Распределение

02/10/2018 by Даниил Крутоголов

Распределение

Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов [latex]N[/latex] различных отрядов, которые были отправлены на завоевания. Однако прибывшие лишь только сейчас разведчики донесли о силах противников, скопленных в этих поселениях, что естественно скорректировало планы Оргрима. И теперь он хочет произвести перераспределение войск по отрядам, переводя воинов из одного отряда в другой. При этом, чтобы не создавать неразбериху в рядах своей армии и выполнить перераспределение как можно быстрее, количество таких переводов должно быть минимально возможным (за один раз переводится один солдат из некоторого отряда в другой).

Напишите программу, которая определяет минимальное количество переводов для перераспределения войск.

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

Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
2 4 2 5 1	1
1 4 4	0
3 2 2 2 4 1 1	2
3 6 3 1 0 0 10	9

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		int size = scan.nextInt();
		long arr1[] = new long [size];
		long arr2[] = new long [size];
		for(int i = 0; i < size; i++){
			arr1[i] = scan.nextInt();
		}
		for(int i = 0; i < size; i++){
			arr2[i] = scan.nextInt();
		}
		long tmp = 0;
		for(int i = 0; i < size; i++){
			tmp+= Math.abs(arr2[i] - arr1[i]);
		}
		System.out.println (tmp / 2);
	}
}

import java.util.Scanner;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

int size = scan.nextInt();

long arr1[] = new long [size];

long arr2[] = new long [size];

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

arr1[i] = scan.nextInt();

}

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

arr2[i] = scan.nextInt();

}

long tmp = 0;

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

tmp+= Math.abs(arr2[i] - arr1[i]);

}

System.out.println (tmp / 2);

}

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

Данная задача решается вычислением и суммированием разности соответствующих элементов второго массива и первого. Таким образом мы найдем количество воинов, которых не хватает и которых надо перевести в другой отряд. Возьмём эту разность по модулю, затем поделим на [latex]2[/latex], так как мы учитывали всех воинов. В итоге получим минимальное количество переводов из одного отряда в другой.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

A393a

28/11/2017 by Мазурин Эдвард

Задача:

Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n},[/latex] где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале [latex]i[/latex]-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

Тесты:


Вводимые данные		Предполагаемый вывод	Комментарий
4	4 3 2 1	4 3 2 1	Тест пройден
	4 3 2 1
	4 3 2 1
	4 3 2 1
	1 2 3 4	1 1 1 1	Тест пройден
	1 2 3 4
	1 2 3 4
	1 2 3 4

Решение:

Считываем матрицу и проходим в цикле по каждой строке ведя поиск минимального элемента (но есть одно «Но», поиск ведется под главной диагональю матрицы).
У всех элементов находящихся под главной диагональю матрицы, включительно, индекс строк больше или равен индексу столбцов заданной матрицы. Учтем это при составлении программы.
Осталось только написать код с учетом вышеперечисленных особенностей задачи.

Код:

import java.util.*;

public class multi_arrays {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt();                //Объявление переменной, обозначающей размерность массива
            int[][] a = new int [n][n];      //Создание двумерного массива
        for (int i = 0; i < n; i++) {        
            for (int j = 0; j < n; j++) {
                System.out.print("Заполните массивы элементами: ");
                a[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            int min = a[i][0];
            for (int j = 0; i - j >= 0; j++)  // критерий отбора элементов под главной диагональю
            {
                if (a[i][j] < min) {
                    min = a[i][j];
                }
            }
            System.out.println(min);
        }
    }
}

import java.util.*;

public class multi_arrays {

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива

int[][] a = new int [n][n]; //Создание двумерного массива

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

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

System.out.print("Заполните массивы элементами: ");

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

}

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

int min = a[i][0];

for (int j = 0; i - j >= 0; j++) // критерий отбора элементов под главной диагональю

{

if (a[i][j] < min) {

min = a[i][j];

}

System.out.println(min);

}

Версия программы на Ideone.com

Ссылка на источник

Ю 4.24

28/11/2017 by Мазурин Эдвард

Задача:

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


Вводимые данные	Предполагаемый вывод	Комментарий
1 1 1 1 1 1	1 1 2 3 4 5	Тест пройден
1 2 3 4 5 6 7 8 9	1 1 3 6 10 15 21 28 36	Тест пройден
3 5 2 9 0 4 65 156 1	3 3 8 10 19 19 23 88 244	Тест пройден
2 -7 3 8 -4 5 -2 4 2	2 2 -5 -2 6 2 7 5 9	Тест пройден

Код:

import java.util.*;


public class cu_total {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива
        int[] a = new int[n]; //Создание массива
        for(int i=0;i<n;i++){ //Ввод значений элементов массива с помощью цикла
            System.out.print("Заполните массив элементами: ");
            a[i] = in.nextInt();
        }
        int b[] = new int[n]; //Создание дополнительного массива, в котором и будет храниться результат.
        int S=0;              //Создание вспомогательной переменной
        b[0]=a[0];            //Инициализация первого элемента второго массива
        for(int i=1;i<n;i++)  //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив
        {
            S+=a[i-1];
            b[i]=S;
        }
        for(int i=0;i<n;i++){
            System.out.println(b[i]);
        }
        System.out.print("\n" + "Тест пройден");
    }
}

import java.util.*;

public class cu_total {

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива

int[] a = new int[n]; //Создание массива

for(int i=0;i<n;i++){ //Ввод значений элементов массива с помощью цикла

System.out.print("Заполните массив элементами: ");

a[i] = in.nextInt();

}

int b[] = new int[n]; //Создание дополнительного массива, в котором и будет храниться результат.

int S=0; //Создание вспомогательной переменной

b[0]=a[0]; //Инициализация первого элемента второго массива

for(int i=1;i<n;i++) //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив

{

S+=a[i-1];

b[i]=S;

}

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

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

}

System.out.print("\n" + "Тест пройден");

}

Описание:

Простейшие операции с массивом. С помощью цикла записываем данные в массив, после чего, снова с помощью цикла, записываем новые данные во второй массив. Далее выводим результат.

Алгоритм:

Объявление переменной и ввод размерности массива.
Создание массива.
Создание цикла, для записи вводимых данных в массив.
Создание нового массива.
Создание цикла, для ввода обработанных данных в новый массив.
Создание цикла, для вывода результата.
Окончания работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

Ю4.35

23/08/2017 by Валентин Лавриненко

Постановка задачи

Совместная работа. Известно время $latex t_1,t_2,\cdots,t_n$ , за которое некоторую работу может выполнить каждый из рабочих бригады, работая в одиночку. Сколько времени понадобится бригаде на выполнение этой работы, если они будут работать совместно (и при этом никто из них не «сачкует»)?

Тесты

Количество рабочих n.	Время t каждого рабочего, требуемое для выполнения некоторой работы.	Время совместной работы.
3	5 7 9	2.2
4	7 9 11 23	2.6
4	1 2 3 4	0.5
5	3 1 5 2 3	0.4

Код

import java.util.*;
import java.lang.*;
 
class Task5
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		double workingTime, sum = 0;
		for(;n>0;n--) 
		{
			workingTime=input.nextDouble();
			sum+=1/workingTime;
		}
		System.out.printf("Работа будет выполнена за%5.1f часов \n", 1/cof);
	}
}

import java.util.*;

import java.lang.*;

class Task5

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n = input.nextInt();

double workingTime, sum = 0;

for(;n>0;n--)

{

workingTime=input.nextDouble();

sum+=1/workingTime;

}

System.out.printf("Работа будет выполнена за%5.1f часов \n", 1/cof);

}

Описание решения

В данной задаче нам нужно найти время, за которое рабочих выполнят какую-то совместную работу. В задаче не указан общий объём выполняемой работы, по-этому зададим его как 1. Время совместной работы находят по формуле: $latex \frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\cdots+\frac{1}{t_n}}$ .

В программе используем один цикл for в котором задаем значение переменной workingTime и суммируем объем выполняемой работы за час для каждого шага цикла (для каждого рабочего). После завершения цикла получаем объем работы выполняемой всеми работниками вместе за час. Делим общий объем работы на объем работы за час и получаем искомую величину.

Посмотреть, как работает программа можно на сайте ideone.
Задача была решена на основе данного решения.

Ю4.3

13/07/2017 by Гуменюк Марина

Задача

Центрирование массива. От каждого из заданных чисел [latex]{x}_{1}, {x}_{2}, \ldots, {x}_{m}[/latex] отнять их среднее арифметическое [latex]\overline{x}_{i} = {x}_{i}[/latex] — [latex]{x}_{cp}[/latex], [latex]i = 1, 2[/latex], … , [latex]m[/latex].

[latex]\overline{x}[/latex] = [latex]1/m[/latex];
[latex]E[/latex] от [latex]m[/latex] при [latex]i = 1 (x_1)[/latex];
[latex]{x}_{i}[/latex] = [latex]{x}_{i}[/latex] — [latex]\overline{x}[/latex]; [latex]i = 1, 2[/latex], … , [latex]m[/latex]

Результаты разместить на месте исходных данных.

Тесты

Количество элементов в массиве — m	Массив	Результат
2	2 5	-1,5 1,5
2	2 6	-2 2
7	2 6 -3 5 1 0 0	0.43 4.43 -4.57 3.43 -0.57 -1.57 -1.57

Код

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();//количество элементов в массиве
		double sum = 0; // сумма чисел массива
		
		double[] arr = new double[m];
		for(int i = 0; i < m; i++)
		{
			arr[i] = in.nextDouble();
		}
		
		for (int i = 0; i < m; i++)
		{
			sum += arr[i];//вводим следующее число
		}

		for (int i = 0; i < m; i++)
		{
			arr[i] = arr[i] - (sum / m);//результат
			System.out.println(arr[i]);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int m = in.nextInt();//количество элементов в массиве

double sum = 0; // сумма чисел массива

double[] arr = new double[m];

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

{

arr[i] = in.nextDouble();

}

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

{

sum += arr[i];//вводим следующее число

}

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

{

arr[i] = arr[i] - (sum / m);//результат

System.out.println(arr[i]);

}

Протестированный код можно увидеть тут.

Решение

Объявляем массив типа double размерностью m. Считываем размерность из первой строки ввода, конвертируем из типа string в тип int; затем считываем элементы массива из второй строки ввода (их конвертируем в double — для точности вычислений). В циклах: находим сумму введенных чисел, затем их среднее арифметическое, затем высчитываем новые значения элементов массива, вычитая от каждого из них среднее арифметическое всего массива. Записываем новые значения поэлементно в исходный массив arr[ ]. Выводим arr[ ].

Ю 4.17

03/07/2017 by Присяжный Михаил

Постановка задачи

В массиве [latex]A(n)[/latex] найти и напечатать номера (индексы) локальных максимумов, то есть таких [latex]a_{i}[/latex], что [latex]a_{i-1}<x_{i}>a_{i+1}[/latex].

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

Количество значений и сами значения

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

Индексы локальных максимумов

Тесты

№	Количество значений	Значения	Результат
1	6	2 4 6 1 3 7 5	2
2	7	3 1 6 2 8 5 7	2, 4
3	10	2 5 8 3 5 6 9 7 1 4	2, 6

Решение

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

class Ideone
{
	public static void main (String[] args)
	{
		int n;
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		double[] x = new double[n];
		for(int i=0; i<n; i++){
			x[i]=s.nextInt();
		}
		for(int j=1; j<=(n-2); j++){
			if((x[j]>x[j+1])&&(x[j]>x[j-1])){
				System.out.println(j + " ");
			}	
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

int n;

Scanner s = new Scanner(System.in);

n = s.nextInt();

double[] x = new double[n];

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

x[i]=s.nextInt();

}

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

if((x[j]>x[j+1])&&(x[j]>x[j-1])){

System.out.println(j + " ");

}

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n для хранения размера массива. Далее создаем массив типа double. Для нахождения локальных максимумов x[i] создаем цикл for, в котором при каждой итерации будем проверять, являются ли значения локальными максимумами. Если значение удовлетворяет условие, выводим на экран индекс этого значения. Например, в первом тесте мы вводим количество значений 6, сами значения 2 4 6 1 3 7 5 и нашим результатом оказывается число с индексом 2, т.е. число 6. Так как числа 4 и 1 меньше 6, наше значение будет удовлетворять условие.