e-olymp 1327. Ладьи на шахматной доске

27/12/2018 by Ivan Myasoedov

Ладьи на шахматной доске

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером $n × n$ можно расставить $n$ ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее $1000$.

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

Выведите ответ, найденный Гариком.

Тесты

#	ВХОДНЫЕ ДАННЫE:	ВЫХОДНЫЕ ДАННЫЕ:
1	2	2
2	10	3628800
3	3	6
4	1	1
5	4	24

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

import java.util.Scanner;
import java.math.BigInteger;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
    	Scanner in = new Scanner(System.in);
    	int a = in.nextInt();
    	BigInteger [] f = new BigInteger[30000];
    	f[0] = BigInteger.valueOf(1);
    	for(int i = 1; i <= a; i++)
    	{
    	  f[i]=f[i-1].multiply(BigInteger.valueOf(i));
    	}
	    System.out.print(f[a]);
	}
}

import java.util.Scanner;

import java.math.BigInteger;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int a = in.nextInt();

BigInteger [] f = new BigInteger[30000];

f[0] = BigInteger.valueOf(1);

for(int i = 1; i <= a; i++)

{

f[i]=f[i-1].multiply(BigInteger.valueOf(i));

}

System.out.print(f[a]);

}

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

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 2618. Следующее число

27/12/2018 by Ivan Myasoedov

Следующее число

Дано число $n$. Необходимо вывести число $n+1$.

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

Дано неотрицательное целое число $n$. Известно, что количество цифр в числе не превышает $10^6$.

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

Вывести число $n+1$.

Тесты

#	ВХОДНЫЕ ДАННЫE:	ВЫХОДНЫЕ ДАННЫЕ:
1	45654	45655
2	5799	5800
3	2131312	2131313
4	0	1
5	699999	700000

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

import java.util.Scanner;
 
public class Main 
{
	public static void main(String[] args) 
	{
    	String s = new Scanner(System.in).next();
    	StringBuilder sb = new StringBuilder();
    	int n = s.length(), c = 1;
    	for(int i=n-1; i>-1; i--) 
    	{
    		int v = s.charAt(i) - '0' + c;
    		c = v / 10;
    		sb.append(v%10);
    	    if(c == 0) 
    	    {
    			if(i > 0) sb.append(new StringBuilder(s.substring(0, i)).reverse());
    			break;
    		}
    	}
    	if(c == 1) sb.append(1);
    	System.out.println(sb.reverse().toString());
	}
}

import java.util.Scanner;

public class Main

{

public static void main(String[] args)

{

String s = new Scanner(System.in).next();

StringBuilder sb = new StringBuilder();

int n = s.length(), c = 1;

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

{

int v = s.charAt(i) - '0' + c;

c = v / 10;

sb.append(v%10);

if(c == 0)

{

if(i > 0) sb.append(new StringBuilder(s.substring(0, i)).reverse());

break;

}

if(c == 1) sb.append(1);

System.out.println(sb.reverse().toString());

}

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

Для решения данной задачи будем использовать строки, так как заданное число превышает максимально возможное значение любых числовых переменных. Далее создаём функцию, которая будет определять всё написанное в строке до и после символа $+$ как подстроку, после чего создаём функцию, которая суммирует эти подстроки. Исполнив этот алгоритм получим правильный ответ.

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 2669. Поворот

09/12/2018 by Ivan Myasoedov

Поворот

Дан массив [latex]n\times m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 2 1 2 3 4	2 2 3 1 4 2
2	3 3 1 2 3 4 5 6 7 8 9	3 3 4 7 1 8 5 2 9 6 3
3	3 4 4 5 7 8 3 6 8 7 2 2 4 5	4 3 2 3 4 2 6 5 4 8 7 5 7 8
4	1 2 5 4	2 1 5 4
5	1 1 2	1 1 2

ВХОДНЫЕ ДАННЫЕ

ВЫХОДНЫЕ ДАННЫЕ

2 2

1 2

3 4

2 2

3 1

4 2

3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

1 2

5 4

2 1

1 1

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

class Main
{
    public static void main (String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int x[][] = new int[n][];
        for (int i = 0; i < n; i++)
            x[i] = new int[m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                x[i][j] = input.nextInt();
        System.out.println(m + " " + n);
        for (int j = 0; j < m; j++){
            for (int i = n - 1; i >= 0; i--)
                System.out.print(x[i][j] + " ");
            System.out.println();
        }   
    }
}

import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n = input.nextInt();

int m = input.nextInt();

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

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

x[i] = new int[m];

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

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

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

System.out.println(m + " " + n);

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

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

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

System.out.println();

}

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

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

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 921. Отрицательные элементы

09/12/2018 by Ivan Myasoedov

Отрицательные элементы

Задан одномерный массив вещественных чисел длины [latex]n[/latex]. Определить сумму и количество отрицательных элементов в массиве.

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

В первой строке задано количество элементов массива [latex]n[/latex] ([latex]n[/latex] ≤ [latex]100[/latex]). В следующей строке через пробел задано [latex]n[/latex] вещественных чисел — элементы массива, значения которых не превышают по модулю [latex]100[/latex].

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

В одной строке вывести количество отрицательных чисел и через пробел их сумму с точностью до [latex]2[/latex]-х знаков после десятичной точки.

Тесты

#	ВХОДНЫЕ ДАННЫE:	ВЫХОДНЫЕ ДАННЫЕ:
1	5 6 -7.5 2.1 -2.0 0	2 -9.50
2	2 -1 -2	2 -3.00
3	6 1 1 1 1 1 1	0 0.00
4	7 -1.99 -5.34 9 6.43 -6.32 0 -7.43	4 -21.08
5	3 -1.992345 -5.334224 9	2 -7.33

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

import java.util.*;
import java.lang.*;
 
class Main
{    
      public static void main (String[] args)
      {   
 
	  int m = 0;
	  double k = 0;
	  Scanner input = new Scanner(System.in);
	  int n = input.nextInt();
	  double x[] = new double [n];
	  for (int i = 0; i<n; i++)
	  {
	       x[i] = input.nextDouble();
	  }
	  for (int i = 0; i<n; i++)
	  {     
		   if (x[i]<0)
		   {
		        m++;
		        k += x[i];
		   }
	  }   
	  System.out.print(m + " " + String.format("%.3g%n", k));
    }
}

import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args)

{

int m = 0;

double k = 0;

Scanner input = new Scanner(System.in);

int n = input.nextInt();

double x[] = new double [n];

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

{

x[i] = input.nextDouble();

}

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

{

if (x[i]<0)

{

m++;

k += x[i];

}

System.out.print(m + " " + String.format("%.3g%n", k));

}

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

Для решения данной задачи я описал две переменные: [latex]m[/latex] типа [latex]int[/latex] и [latex]k[/latex] типа [latex]double[/latex], которые изначально равны [latex]0[/latex]. Цикл ищет в массиве элементы которые меньше [latex]0[/latex]. C каждым найденным отрицательным элементом, [latex]m[/latex] увеличиваться на [latex]1[/latex], а к числу [latex]k[/latex] прибавляется сам элемент.

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 2261. Защита королевства

02/12/2018 by Ivan Myasoedov

Защита королевства

Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.

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

Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].

Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	10 10 3 1 1 2 2 3 3	49
2	15 15 4 4 4 5 5 7 8 13 15	30
3	30 30 5 13 14 16 27 29 30 5 5 10 15	132
4	100 100 2 1 1 100 100	9604
5	3 3 3 1 1 2 2 3 3	0

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

import java.util.*;
import java.lang.*;
import java.util.Arrays.*;
 
class Main
{
	public static void main (String[] args)
	{
		int a = 0, b = 0;
		Scanner input = new Scanner(System.in);
		int x_max = input.nextInt();
		int y_max = input.nextInt();
		int n = input.nextInt();
		int x[] = new int[n+2];
		int y[] = new int[n+2];
		for(int i = 1; i < n + 1; i++)
		{
			x[i] = input.nextInt();
			y[i] = input.nextInt();
		}	
		x[0] = y[0] = 0;
        x[n + 1] = x_max + 1; 
        y[n + 1] = y_max + 1;
        Arrays.sort(x);
        Arrays.sort(y);
        for(int i = 0; i < n + 1; i++)
        { 
             if(x[i + 1]-x[i]>a) a = x[i + 1]-x[i];
             if(y[i + 1]-y[i]>b) b = y[i + 1]-y[i];
        }
        System.out.print((a-1)*(b-1));
	}
}

import java.util.*;

import java.lang.*;

import java.util.Arrays.*;

class Main

{

public static void main (String[] args)

{

int a = 0, b = 0;

Scanner input = new Scanner(System.in);

int x_max = input.nextInt();

int y_max = input.nextInt();

int n = input.nextInt();

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

int y[] = new int[n+2];

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

{

x[i] = input.nextInt();

y[i] = input.nextInt();

}

x[0] = y[0] = 0;

x[n + 1] = x_max + 1;

y[n + 1] = y_max + 1;

Arrays.sort(x);

Arrays.sort(y);

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

{

if(x[i + 1]-x[i]>a) a = x[i + 1]-x[i];

if(y[i + 1]-y[i]>b) b = y[i + 1]-y[i];

}

System.out.print((a-1)*(b-1));

}

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

Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.

Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами ([latex]0[/latex];[latex]0[/latex]) и ([latex]x[/latex] [latex]max+1[/latex]; [latex]y[/latex] [latex]max+1[/latex]). Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex](a-1)\cdot(b-1)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 8288. Олимпиада по программированию

02/12/2018 by Ivan Myasoedov

Олимпиада по программированию

На АСМ-олимпиаду прибыло [latex]N[/latex] участников. В результате анкетированные члены жури установили, что [latex]A[/latex] участников программируют на Cи, [latex]B[/latex] на Python, [latex]C[/latex] на Pascal, [latex]X[/latex] одновременно знают Cи и Python, [latex]Y[/latex] — Python и Pascal, [latex]Z[/latex] — Cи и Pascal. Имея значения [latex]N, A, B, C, X, Y, Z[/latex] установите количество участников, которые программируют на трёх языках программирования.

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

В одной строке через пробел сем действительных чисел [latex]N, A, B, C, X, Y, Z[/latex] значения которых не превышают [latex]100[/latex].

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

Единственное число – количество участников, которые программируют на трёх языках программирования.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	100 40 50 60 15 20 25	10
2	100 50 60 60 20 40 25	15
3	80 50 40 60 20 30 25	5
4	80 50 40 60 0 0 0	0
5	40 20 30 0 5 0 10	5

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

import java.util.*;
import java.lang.*;
 
class Main
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int a = input.nextInt();
		int b = input.nextInt();
		int c = input.nextInt();
		int x = input.nextInt();
		int y = input.nextInt();
		int z = input.nextInt();
		if (x + y + z == 0)
		{
    	     System.out.print(0);
    	}
    	else
    	{
    	     System.out.print((x + y + z) - (a + b + c - n));
    	}
 
	}
}

import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n = input.nextInt();

int a = input.nextInt();

int b = input.nextInt();

int c = input.nextInt();

int x = input.nextInt();

int y = input.nextInt();

int z = input.nextInt();

if (x + y + z == 0)

{

System.out.print(0);

}

else

{

System.out.print((x + y + z) - (a + b + c - n));

}

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

Алгоритм решения данной задачи состоит в том, чтоб найти разность между числом участников, что одновременно знают по два языка $(X + Y + Z)$, и числом, что показывает на сколько языков больше чем людей (разностью между общим количеством языков и участников) $(A + B + C — N)$. Тем самым, мы найдем количество людей, которые знают одновременно 3 языка. Его также можно объяснить используя диаграмму Эйлера-Венна, на которой отмечено семь областей. Из условия следует, что:

$\begin {cases} x_1 &+ &x_2 &+ &x_3 &+ &x_4 &+ &x_5 &+ &x_6 &+ &x_7 &=N \newline x_1 &+ & & & &&x_4 &+ & & &x_6 &+ &x_7 &=A \newline & & &&x_3 &+ &x_4 &+ &x_5 &+ & & &x_7 &=B\newline & &x_2 &+ & & & & &x_5 &+ &x_6 &+ &x_7 &=C \newline & & &&& &x_4 && && &+ &x_7 &=X \newline & & & & && & &x_5 & & &+ &x_7 &=Y \newline & & & & & & & & & &x_6 &+ &x_7 &=Z \end{cases}$

Нам нужно найти количество участников в [latex]x_7[/latex] области (области одновременного пересечения всех трех кругов). И получается, что:

$(X + Y + Z)-(A + B + C — N)=x_7$

Если же после ввода данных, окажется, что количество людей знающих два языка равно нулю $(X + Y + Z == 0)$, то программа выведет, что людей знающих одновременно три языка также нет.

Задача на сайте e-olymp
Код решения в Ideone

e-olymp 7367. Спортсмен

02/12/2018 by Ivan Myasoedov

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое наименьшее количество дней спортсмен пробежит суммарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	9	1
2	45	4
3	324	16
4	1234	28
5	213213123	153

Код программы №1 (с использованием цикла):

import java.util.*;
import java.math.*;

class Main
{
	public static void main (String[] args)
	{
		double S;
		Scanner input = new Scanner(System.in);
        S = input.nextDouble();
        S = Math.ceil((Math.log(S/100+1)/Math.log(1.1)));
        int a = (int) S;
		System.out.print(a);
	}
}

import java.util.*;

import java.math.*;

class Main

{

public static void main (String[] args)

{

double S;

Scanner input = new Scanner(System.in);

S = input.nextDouble();

S = Math.ceil((Math.log(S/100+1)/Math.log(1.1)));

int a = (int) S;

System.out.print(a);

}

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

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

Ссылки

Задача на сайте e-olymp
Код решения в Ideone

Код программы №2(с использованием линейных вычислений):

import java.util.*;
 
class Main
{
	public static void main (String[] args)
	{
		int N, k = 1;
		double S = 10, T = 10;
		Scanner input = new Scanner(System.in);
        N = input.nextInt();
        while (N > T) 
        {
			S = S * 1.1;
			T = S + T;
			k++;
		}
		System.out.print(k); 
	}
}

import java.util.*;

class Main

{

public static void main (String[] args)

{

int N, k = 1;

double S = 10, T = 10;

Scanner input = new Scanner(System.in);

N = input.nextInt();

while (N > T)

{

S = S * 1.1;

T = S + T;

k++;

}

System.out.print(k);

}

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).

Ссылки

Задача на сайте e-olymp
Код решения в Ideone №2