e-olymp 977. Дерево?

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

Задача

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

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

Первая строка содержит количество вершин графа $n \left (1 \leq n \leq 100 \right).$ Далее записана матрица смежности размером $n × n$, в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

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

Выведите сообщение YES, если граф является деревом, и NO в противном случае.

Тесты

Входные данные	Выходные данные
[latex]3 \\ 0 \ 1 \ 0 \\ 1 \ 0 \ 1 \\ 0 \ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]2 \\ 0 \ 1 \\ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]4 \\ 0 \ 0 \ 0 \ 1 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 0 \ 0[/latex]	[latex]NO[/latex]
[latex]1 \\ 0[/latex]	[latex]YES[/latex]

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

import java.util.Scanner;
import java.util.ArrayList;

class Main
{
	private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {
		A[v]++;
		if (A[v]>1)
			return;
		for (int i=0; i<g.get(v).size(); i++)
		{
			if (g.get(v).get(i)!=p)
				dfs(g.get(v).get(i), v, g, A);
		}
	}
	
	public static void main (String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] A = new int[n];
		ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i<n; i++) {
			ArrayList<Integer> r = new ArrayList<Integer>();
			for (int j=0; j<n; j++) {
				int a = scanner.nextInt();
				if (a==1) {
					r.add(j);
				}
			}
			g.add(r);
		}
		int t=0;
		dfs(0, -1, g, A);
		for (int i=0; i<n; i++)
		{
			if (A[i]!=1)
			{
				t++;
				break;
			}
		}
		if (t!=0)
			System.out.print("NO");
		else
			System.out.print("YES");
	}
}

import java.util.Scanner;

import java.util.ArrayList;

class Main

{

private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {

A[v]++;

if (A[v]>1)

return;

for (int i=0; i<g.get(v).size(); i++)

{

if (g.get(v).get(i)!=p)

dfs(g.get(v).get(i), v, g, A);

}

public static void main (String[] args)

{

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] A = new int[n];

ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();

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

ArrayList<Integer> r = new ArrayList<Integer>();

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

int a = scanner.nextInt();

if (a==1) {

r.add(j);

}

g.add(r);

}

int t=0;

dfs(0, -1, g, A);

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

{

if (A[i]!=1)

{

t++;

break;

}

if (t!=0)

System.out.print("NO");

else

System.out.print("YES");

}

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

Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.

Ссылки

Условие задачи на 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
Код решения

А329. Квадрат суммы цифр числа

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

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа $n$, $m$. Получить все меньшие натуральные числа, квадрат суммы цифр которых равен $m$.

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

Два положительных числа $n$ и $m$.

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

Все целые числа из $\left ( 0, n \right )$, удовлетворяющие условию.

Тесты

Входные данные	Выходные данные
$1234 \ 9$	$3 \ 12 \ 21 \ 30 \ 102 \ 111 \ 120 \ 201 \ 210 \ 300 \ 1002 \ 1011 \ 1020 \ 1101 \ 1110 \ 1200$
$100 \ 4$	$2 \ 11 \ 20$
$49 \ 49$	$7 \ 16 \ 25 \ 34 \ 43$
$1000 \ 1$	$1 \ 10 \ 100$

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

import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		for(int i=1; i<n; i++) {
			int a=i;
			int sum=0;
			while(a!=0) {
				sum+=a%10;
				a/=10;
			}
			if(sum*sum==m)
				System.out.print(i+" ");
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int m = scanner.nextInt();

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

int a=i;

int sum=0;

while(a!=0) {

sum+=a%10;

a/=10;

}

if(sum*sum==m)

System.out.print(i+" ");

}

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

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

Ссылки

Условие задачи (страница 135)
Код решения

e-olymp 2892. Сумма значений

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

Задача

Найдите сумму значений функции
$$f \left(x \right ) = x + \frac{1}{x}$$
в нескольких целых точках.

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

В первой строке задано количество точек $n$ $\left (1 \leqslant n \leqslant 50 \right ).$ В следующей строке заданы $n$ целых чисел $x_1, x_2, …, x_n$ — точки, значения функции в которых нужно просуммировать $\left (0 \leqslant \left |x_i \right | \leqslant 10^9 \right ).$

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

Выведите одно число — сумму значений функции $f \left(x \right )$ в заданных точках. Ответ считается правильным, если абсолютная или относительная погрешность не превышает $10^{-9}.$

Тесты

Входные данные	Выходные данные
$3$	$7.833333333333333$
$1 \ 2 \ 3$
$2$	$0$
$1 \ -1$
$5$	$4.265140415140415$
$10 \ -13 \ 21 \ -18 \ 4$
$1$	$10.1$
$10$

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

import java.util.Scanner;
import java.util.ArrayList;
import java.math.BigDecimal; 
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		BigDecimal ans = new BigDecimal(0);
		ArrayList<BigDecimal> a = new ArrayList<BigDecimal>();
		for(int i=0; i<n; i++) {
			BigDecimal x = scanner.nextBigDecimal();
			a.add(x);
		}
		for(int i=0; i<n; i++) {
			BigDecimal w = a.get(i);		
			BigDecimal v = new BigDecimal(1); 
			ans = ans.add(w.add(v.divide(w, 15, BigDecimal.ROUND_HALF_UP)));
		}
		System.out.println(ans);
	}
}

import java.util.Scanner;

import java.util.ArrayList;

import java.math.BigDecimal;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

BigDecimal ans = new BigDecimal(0);

ArrayList<BigDecimal> a = new ArrayList<BigDecimal>();

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

BigDecimal x = scanner.nextBigDecimal();

a.add(x);

}

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

BigDecimal w = a.get(i);

BigDecimal v = new BigDecimal(1);

ans = ans.add(w.add(v.divide(w, 15, BigDecimal.ROUND_HALF_UP)));

}

System.out.println(ans);

}

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

Мы просто суммируем значения функции в каждой точке. Тут использовали класс BigDecimal для точек и значений функции для более высокой точности.

Ссылки

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

e-olymp 670. Поиск палиндромов

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

Задача

Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «madam», «bob».
Определите, сколько палиндромов заданной длины $K$ содержит заданная строка $S$.

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

В первой строке содержится целое число $K$ ($2 \leqslant K \leqslant 200$), а во второй – заданная строка $S$, состоящая только из латинских букв, причем большие и малые буквы различаются (т.е. «Bob» — не палиндром). Длина $S$ от $1$ до $30000$ символов.

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

В единственной строке должно находиться количество различных палиндромов длины $K$, содержащихся в $S$ (т.е. являющихся последовательностями подряд идущих символов в $S$) (различными считаются палиндромы, начинающиеся с разных позиций в $S$).

Тесты

Входные данные	Выходные данные
$3$	$3$
$babcbab$
$1$	$5$
$abcde$
$4$	$0$
$aarreeds$
$5$	$3$
$aaaaaaa$
$3$	$0$
$CaccaC$

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String q = bufferedReader.readLine();
        int k = Integer.parseInt(q);
        String s = bufferedReader.readLine();
        int l, r, flag=0, ans=0;
		for(int i=0; i<s.length()-k+1; i++)
		{
			flag=0;
			l=i;
			r=i+k-1;
			for(int j=0; j<k/2; j++)
			{
			    if(s.charAt(l+j)!=s.charAt(r-j)){ 
			        flag=1;
			        break;
			    }
			}
			if(flag==0){
			    ans++;
			}
		}
		System.out.print(ans);
    }
}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

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

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

String q = bufferedReader.readLine();

int k = Integer.parseInt(q);

String s = bufferedReader.readLine();

int l, r, flag=0, ans=0;

for(int i=0; i<s.length()-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s.charAt(l+j)!=s.charAt(r-j)){

flag=1;

break;

}

if(flag==0){

ans++;

}

System.out.print(ans);

}

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

Мы рассматриваем все подстроки строки $s$ длины $k$ и проверяем, является ли каждая подстрока палиндромом. В случае положительного ответа, увеличиваем счетчик. Проверка, является ли каждая подстрока палиндромом, выполняется следующим образом: мы ставим указатели на противоположные концы подстроки, далее сравниваем элементы на которые указывают указатели и если они равны, одновременно сдвигаем указатели на один к центру этой подстроки. Продолжаем этот процесс до тех пор, пока указатели не «встретятся». Если на каком то этапе элементы не равны, прекращаем процесс с отрицательным ответом для этой подстроки. Если же указатели «встретились», то эта подстрока является палиндромом.

Ссылки

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

e-olymp 2668. Спираль

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

Задача

Заполнить массив размера $n × n$ единичками по спирали (см. пример).

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

Одно нечетное натуральное число $n$, не превышающее $50$.

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

Вывести построенную спираль. Центральная клетка должна содержать $0$.

Тесты

Входные данные	Выходные данные
[latex]7[/latex]	[latex]1111111 \\ 0000001 \\ 1111101 \\ 1000101 \\ 1011101 \\ 1000001 \\ 1111111[/latex]
[latex]1[/latex]	[latex]0[/latex]
[latex]3[/latex]	[latex]111 \\ 001 \\ 111[/latex]
[latex]5[/latex]	[latex]11111 \\ 00001 \\ 11001 \\ 10001 \\ 11111[/latex]

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

import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int [][] s = new int[50][50];
		for(int i=0; i<n; i++)
		{
			s[0][i]=1;
			s[n-1][i]=1;
			s[i][n-1]=1;
		}
		int h=n-2, d=n-2;
		int pointx=n-1, pointy=0; 
		while(true)
		{
			for(int i=0; i<h; i++)
			{
			    s[pointx-i][pointy]=1;
			}
			pointx-=h-1;
			h-=2;
			if(h<=0)
			    break;
			for(int i=0; i<d; i++)
			{
			    s[pointx][pointy+i]=1;
			}
			pointy+=d-1;
			d-=2;
			if(d<=0)
			    break;
		    for(int i=0; i<h; i++)
			{
			    s[pointx+i][pointy]=1;
			}
			pointx+=h-1;
			h-=2;
			if(h<=0)
			    break;
			for(int i=0; i<d; i++)
			{
			    s[pointx][pointy-i]=1;
			}
			pointy-=d-1;
			d-=2;
			if(d<=0)
			    break;
		}
		s[n/2][n/2]=0;
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
			    System.out.print(s[i][j]);
			}
			System.out.println();
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int [][] s = new int[50][50];

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

{

s[0][i]=1;

s[n-1][i]=1;

s[i][n-1]=1;

}

int h=n-2, d=n-2;

int pointx=n-1, pointy=0;

while(true)

{

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

{

s[pointx-i][pointy]=1;

}

pointx-=h-1;

h-=2;

if(h<=0)

break;

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

{

s[pointx][pointy+i]=1;

}

pointy+=d-1;

d-=2;

if(d<=0)

break;

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

{

s[pointx+i][pointy]=1;

}

pointx+=h-1;

h-=2;

if(h<=0)

break;

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

{

s[pointx][pointy-i]=1;

}

pointy-=d-1;

d-=2;

if(d<=0)

break;

}

s[n/2][n/2]=0;

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

{

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

{

System.out.print(s[i][j]);

}

System.out.println();

}

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

Для начала мы верхнюю, нижнюю и правую грани зразу заполним единицами. Далее идем поочередно в четырех направления (вверх, вправо, вниз, влево). Мы имеем два параметра: ширину и высоту заполняемого единицами отрезка (ширине соответствуют движения вправо и влево, высоте — вверх и вниз). На каждом шаге уменьшаем соответствующий заполняемый отрезок (ширину или высоту) на $2$ и проверяем, чтобы он был больше $0$, иначе заканчиваем. На протяжении всего решения храним еще два параметра: координаты точки, откуда начнем следующий шаг.
P.s. На сайте www.e-olymp.com это решение не проходит полностью из-за неправильности $5$-го теста. У них в $5$-ом тесте центральный элемент $1$, что противоречит условию.

Ссылки

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

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 49. Кот учёный

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

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

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

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

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

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

Тесты

Входные данные	Выходные данные
[latex]4\, 4\, 2[/latex]	[latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex]	[latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex]	[latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

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

import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int l = scanner.nextInt();
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int count = 0;
		for(int i=0; i<n; i++) {
			int x1 = scanner.nextInt();
			int y1 = scanner.nextInt();
			int x2 = scanner.nextInt();
			int y2 = scanner.nextInt();
			if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)
				count++;
			else {
			 	int a, b, c;
		    	int deltaX=x2-x1;
				int deltaY=y2-y1;
		    	a=deltaY;
		    	b=-deltaX;
		    	c=y1*deltaX-x1*deltaY;
		    	if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*Math.max(y2, y1)&&-c*b>=(b*b+a*a)*Math.min(y2, y1)))
		        	count++;
			}
		}
		System.out.println(count/k+1);
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int l = scanner.nextInt();

int n = scanner.nextInt();

int k = scanner.nextInt();

int count = 0;

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

int x1 = scanner.nextInt();

int y1 = scanner.nextInt();

int x2 = scanner.nextInt();

int y2 = scanner.nextInt();

if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)

count++;

else {

int a, b, c;

int deltaX=x2-x1;

int deltaY=y2-y1;

a=deltaY;

b=-deltaX;

c=y1*deltaX-x1*deltaY;

if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*Math.max(y2, y1)&&-c*b>=(b*b+a*a)*Math.min(y2, y1)))

count++;

}

System.out.println(count/k+1);

}

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

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

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

e-olymp 161. Роботы

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

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

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

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

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

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

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные	Выходные данные
[latex]6[/latex]	[latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex]	[latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex]	[latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex]	[latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

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

import java.util.*;

public class Main {
	
	private static class Pair{
		int a, b;
		
		public Pair(int a, int b) {
			this.a=a;
			this.b=b;
		}
		
	}
	
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int na = scanner.nextInt();
		int[] A = new int[na];
		int[] times = new int[n];
		PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->a.a-b.a);
		for(int i=0; i<na; i++) {
			A[i] = scanner.nextInt();
			q.add(new Pair(A[i], A[i]));
		}
		for(int i=0; i<n; i++) {
			Pair pair=q.poll();
			times[i]=pair.a;
			q.add(new Pair(pair.a+pair.b, pair.b));
		}
		q.clear();
		int nb = scanner.nextInt();
		int[] B = new int[nb];
		int max_time=0;
		for(int i=0; i<nb; i++) {
			B[i] = scanner.nextInt();
			q.add(new Pair(B[i], B[i]));
		}
		for(int i=n-1; i>=0; i--) {
			Pair pair=q.poll();
		    times[i]+=pair.a;
			q.add(new Pair(pair.a+pair.b, pair.b));
			if(times[i]>max_time)
				max_time=times[i];
		}
		System.out.println(max_time);
	}
}

import java.util.*;

public class Main {

private static class Pair{

int a, b;

public Pair(int a, int b) {

this.a=a;

this.b=b;

}

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int na = scanner.nextInt();

int[] A = new int[na];

int[] times = new int[n];

PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->a.a-b.a);

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

A[i] = scanner.nextInt();

q.add(new Pair(A[i], A[i]));

}

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

Pair pair=q.poll();

times[i]=pair.a;

q.add(new Pair(pair.a+pair.b, pair.b));

}

q.clear();

int nb = scanner.nextInt();

int[] B = new int[nb];

int max_time=0;

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

B[i] = scanner.nextInt();

q.add(new Pair(B[i], B[i]));

}

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

Pair pair=q.poll();

times[i]+=pair.a;

q.add(new Pair(pair.a+pair.b, pair.b));

if(times[i]>max_time)

max_time=times[i];

}

System.out.println(max_time);

}

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

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
На втором этапе фактически делаем тоже, что и на первом с учетом следующей стратегии комбинации. Для детали, которая пройдет первый этап последней, на втором этапе резервируем самый быстрый из роботов второго типа.
Теперь оценим сложность работы алгоритма. Для каждой из $n$ деталей работает логарифмическая вставка в очередь с приоритетом. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

e-olymp 130. Прямоугольник

04/10/2018 by Костя Григорян

Задача

Заданы координаты трёх вершин прямоугольника. Найдите координаты четвертой вершины.

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

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

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

Два числа, координаты искомой вершины прямоугольника. Все входные и выходные данные — целые числа, не превышающие по модулю [latex]100[/latex].

Тесты

Входные данные	Выходные данные
[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]1[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]2[/latex] [latex]0[/latex]
[latex]1\, 4\, 4\, 0\, 0\, 2[/latex]	[latex]5\, 2[/latex]
[latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]-100[/latex]	[latex]-100[/latex] [latex]100[/latex]
[latex]2[/latex] [latex]-1[/latex] [latex]3[/latex] [latex]1[/latex] [latex]-2[/latex] [latex]1[/latex]	[latex]-1[/latex] [latex]3[/latex]
[latex]8\, 0\, 1\, 6\, 0\, 4[/latex]	[latex]9\, 2[/latex]

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

import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int x1 = scanner.nextInt();
		int y1 = scanner.nextInt();
		int x2 = scanner.nextInt();
		int y2 = scanner.nextInt();
		int x3 = scanner.nextInt();
		int y3 = scanner.nextInt();
		if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0) {
			System.out.println((x2+x3-x1)+" "+(y2+y3-y1));
		}
		else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0) {
			System.out.println((x1+x3-x2)+" "+(y1+y3-y2));
		}
		else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0) {
			System.out.println((x1+x2-x3)+" "+(y1+y2-y3));
		}   
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int x1 = scanner.nextInt();

int y1 = scanner.nextInt();

int x2 = scanner.nextInt();

int y2 = scanner.nextInt();

int x3 = scanner.nextInt();

int y3 = scanner.nextInt();

if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0) {

System.out.println((x2+x3-x1)+" "+(y2+y3-y1));

}

else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0) {

System.out.println((x1+x3-x2)+" "+(y1+y3-y2));

}

else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0) {

System.out.println((x1+x2-x3)+" "+(y1+y2-y3));

}

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

Прямоугольник

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [latex]x_4=x_1+x_3-x_2[/latex] и [latex]y_4=y_1+y_3-y_2[/latex]. Но мы не знаем какая из входных вершин противоположна четвертой, а какие — прилежащие. Так как наша фигура это прямоугольник, то противоположная вершина будет при угле [latex]90^{\circ}[/latex]. Произведение перпендикулярных векторов дает [latex]0[/latex]. Перебрав три варианта произведения векторов, заданных входными вершинами, находим вершину при угле [latex]90^{\circ}[/latex]. Остальные две, соответственно, будут прилежащими. Находим координаты четвертой вершины по формуле, заданной выше.

Ссылки

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