e-olymp112.Торт

27/12/2018 by Илья Черноморец

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

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

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

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $1000$.

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

Вывести время в часах, за которое толстяки вместе могут съесть торт. Результат округлить до двух десятичных знаков.

Тесты

$t_1$	$t_2$	$t_3$	$t$
3	3	3	1.00
4	67	50	3.51
228.22	8	2.28	1.76
1577	157.7	15.77	14.21

С ветвлением

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		double t1 = i.nextDouble();
		double t2 = i.nextDouble();
		double t3 = i.nextDouble();
		double t;
		t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);
		if(t1*t2*t3 == 0) System.out.println(t);
		else System.out.printf("%.2f",t);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

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

double t1 = i.nextDouble();

double t2 = i.nextDouble();

double t3 = i.nextDouble();

double t;

t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);

if(t1*t2*t3 == 0) System.out.println(t);

else System.out.printf("%.2f",t);

}

Без ветвления

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		double t1 = i.nextDouble();
		double t2 = i.nextDouble();
		double t3 = i.nextDouble();
		double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;
		System.out.printf("%.2f",t);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

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

class Main

{

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

{

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

double t1 = i.nextDouble();

double t2 = i.nextDouble();

double t3 = i.nextDouble();

double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;

System.out.printf("%.2f",t);

}

Решение с ветвлением

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t_1}-\frac{t}{t_2}-\frac{t}{t_3}=0;$
$\frac{t}{t_1}+\frac{t}{t_2}+\frac{t}{t_3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t\left(t_1t_2+t_2t_3+t_1t_3\right)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Решение без ветвления

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $\left(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}\right)$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков.

Ссылки

Ссылка на E-olymp
Ссылка на решение

e-olymp 51. К-домино

25/12/2018 by Александра Филистович

Задача

Работник отдела технического контроля любил выбраковывать «доминошки», которые содержали одинаковые значения. Так как на предприятии, выпускающем [latex]K[/latex]-домино, этого не знали, к нему постоянно поступали претензии на сумму, равную стоимости [latex]K[/latex]-домино. Стоимость [latex]K[/latex]-домино составляла ровно столько гривен, сколько было в купленном покупателем наборе доминошек.Для того, чтобы его не уволили с работы, работник ОТК выбраковывал иногда не только все не любимые «доминошки», а несколько больше, но не более половины гарантированно выбраковыванных.Зная сумму претензии, пришедшей на предприятие, установите, какой из наборов [latex]K[/latex]-домино был куплен покупателем.

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

Единственное число [latex]S[/latex] – сумма претензии, пришедшей на предприятие, [latex]S ≤ 2000000000[/latex].

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

Единственное число – индекс [latex]K[/latex] купленного покупателем [latex]K[/latex]-домино.

№	Входные данные	Выходные данные
1	5	3
2	10	4
3	1000000	1414
4	555666777888	1054198
5	13	5

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		long s = scan.nextLong();
                //применяем формулу и округляем число вниз
		double k = Math.floor(Math.sqrt(2 * s + 1));
                //переводим double в int
		int ans = (int) k;
		System.out.println (ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

long s = scan.nextLong();

//применяем формулу и округляем число вниз

double k = Math.floor(Math.sqrt(2 * s + 1));

//переводим double в int

int ans = (int) k;

System.out.println (ans);

}

Решение

[latex]K[/latex]-домино — набор домино с минимальным количеством точек на одной из половин доминошки.
Количество дублей, то есть количество точно выбракованных доминошек — [latex]k[/latex]+1. Общее количество доминошек [latex]k[/latex]-домино:$$(k+1){{k+2}\over{2}}$$
Пусть работник дополнительно выбраковывал [latex]e[/latex] доминошек. [latex]s[/latex] — сумма претензии, тогда имеем:

[latex]k+1+e+s= (k+1){{k+2}\over{2}}[/latex]
[latex]k^2<=2s+1[/latex]
[latex]k=[\sqrt{2s+1}][/latex]

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp 1482. Умножение матриц

24/12/2018 by Томас Пасенченко

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где:
$$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

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

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

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

В первой строке вывести размерность итоговой матрицы $C$: $n_c$ и $m_c$. В последующих $n_c$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $-1$.

Тесты

Входные данные	Выходные данные
2 3 1 3 4 5 -2 3 3 3 1 3 2 2 1 3 0 -1 1	2 3 7 2 15 1 10 7
3 3 1 5 3 2 6 1 7 -1 -3 3 2 3 6 -1 1 3 1	3 2 7 14 3 19 13 38
4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2 4 4 1 0 0 0 0 1 0 0 0 0 1 0	4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2
3 3 5 7 -1 8 9 3 0 -6 17 2 3 7 -15 1 8 8 2	-1
2 3 57 -49 31 89 11 -37 3 1 19 -19 0	2 1 2014 1482

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

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int na = scanner.nextInt();
		int ma = scanner.nextInt();
		int[][] a = new int[na][ma];
		for (int i = 0; i < na; i++) {
			for (int j = 0; j < ma; j++) {
            			a[i][j] = scanner.nextInt();
			}
		}
		int nb = scanner.nextInt();
		int mb = scanner.nextInt();
		if (ma != nb) {
			System.out.print(-1);
			return;
		}
		int[][] b = new int[nb][mb];
		for (int i = 0; i < nb; i++) {
			for (int j = 0; j < mb; j++) {
				b[i][j] = scanner.nextInt();
			}
		}
		int[][] c = new int[na][mb];
		for (int i = 0; i < na; i++) {
			for (int j = 0; j < mb; j++) {
				for (int r = 0; r < ma; r++) {
					c[i][j] += a[i][r] * b[r][j];
				}
			}
		}
		System.out.print(na + " " + mb + "\n");
		for (int i = 0; i < na; i++) {
			for (int j = 0; j < mb; j++) {
				System.out.print(c[i][j]);
				if (j + 1 != mb) System.out.print(" ");
			}
			System.out.print("\n");
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int na = scanner.nextInt();

int ma = scanner.nextInt();

int[][] a = new int[na][ma];

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

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

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

}

int nb = scanner.nextInt();

int mb = scanner.nextInt();

if (ma != nb) {

System.out.print(-1);

return;

}

int[][] b = new int[nb][mb];

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

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

b[i][j] = scanner.nextInt();

}

int[][] c = new int[na][mb];

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

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

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

c[i][j] += a[i][r] * b[r][j];

}

System.out.print(na + " " + mb + "\n");

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

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

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

if (j + 1 != mb) System.out.print(" ");

}

System.out.print("\n");

}

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C$.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Умножение матриц на Wikipedia

e-olymp 446. Ровные делители

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

Задача

Натуральное число $m$ называется ровным делителем числа $n$, если частное и остаток от деления $n$ на $m$ равны. По заданному натуральному числу $n$ найти количество его ровных делителей.

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

Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.

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

Выведите искомое количество ровных делителей числа $n$.

Тесты

Входные данные	Выходные данные
5	1
20	2
200	6
653	1
5982	4

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

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);
		
		long n = in.nextLong();
		long q = 0;
		for (int m = 1; m <= n; m++)
			if (n / m == n % m)
				q += 1;
		out.print(q);
		
		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);

long n = in.nextLong();

long q = 0;

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

if (n / m == n % m)

q += 1;

out.print(q);

out.flush();

}

Решение

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

Ссылки

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

e-olymp 58. Биллиард

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

Задача

Биллиард представляет собой прямоугольник размерами $M \times N$, где $M$ и $N$ — натуральные числа. Из верхней левой лузы вылетает шар под углом $45^{\circ}$ к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

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

Во входной строке два числа $M$ и $N$, $1 ≤ M, N ≤ 2000000000$. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. $M$ — горизонтальная сторона биллиарда, $N$ — вертикальная сторона биллиарда.

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

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные	Выходные данные
2 1	1 2
5 6	9 4
12 33	13 2
156 156	0 3
654 236	443 4

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

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

public class Main
{
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      PrintWriter out = new PrintWriter(System.out);
	
      long m = in.nextLong();
      long n = in.nextLong();
      BigInteger bi1, bi2, bi3;
      bi1 = BigInteger.valueOf(m);
      bi2 = BigInteger.valueOf(n);
      bi3 = bi1.gcd(bi2);
      long g = bi3.longValue();
      m /= g;
      n /= g;
      out.print((n + m - 2) + " ");
      if(n % 2 == 0 & m % 2 != 0) out.print(4);
      if(n % 2 != 0 & m % 2 != 0) out.print(3);
      if(n % 2 != 0 & m % 2 == 0) out.print(2);
      
      out.flush();
   }
}

import java.io.*;

import java.util.*;

import java.math.*;

public class Main

{

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

long m = in.nextLong();

long n = in.nextLong();

BigInteger bi1, bi2, bi3;

bi1 = BigInteger.valueOf(m);

bi2 = BigInteger.valueOf(n);

bi3 = bi1.gcd(bi2);

long g = bi3.longValue();

m /= g;

n /= g;

out.print((n + m - 2) + " ");

if(n % 2 == 0 & m % 2 != 0) out.print(4);

if(n % 2 != 0 & m % 2 != 0) out.print(3);

if(n % 2 != 0 & m % 2 == 0) out.print(2);

out.flush();

}

Решение

Чтобы решить эту задачу, необходимо сперва найти НОД значений $M$ и $N$ из условия. Для этого, нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали в $3$ строке. Далее, в $17$ строке, введем перемененную g и присвоим ей значение НОД для $M$ и $N$. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

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

e-olymp 2860. Сумма чисел на промежутке

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

Задача

Найти сумму целых чисел на промежутке от $a$ до $b$.

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

Два целых числа $a$ и $b$, по модулю не превышающих $10^9$.

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

Сумма целых чисел на промежутке от $a$ до $b$.

Тесты

Входные данные	Выходные данные
2 5	14
249 318	19845
23 69	2162
124 200	12474
478 653	99528

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

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);
      
      long a = in.nextLong();
      long b = in.nextLong();
      long n, S;
      n = b - a + 1;
      S = (a + b) * n / 2;
      out.print(S);
      
      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);

long a = in.nextLong();

long b = in.nextLong();

long n, S;

n = b - a + 1;

S = (a + b) * n / 2;

out.print(S);

out.flush();

}

Решение

Для того, что бы найти ответ, нам необходимо знание формул прогрессии, так как решением данной задачи является сумма $n$ первых членов арифметической прогрессии. Вычислить её можно по формуле $\displaystyle S_n = \frac{a_1 + a_n}{2} \cdot n$, где $a_1$ — это a из входного потока, а $a_n$ — это b . Тем не менее, мы все ещё не можем применить вышеприведенную формулу, так как нам неизвестно $n$. Выведем же его из формулы $n$-ого члена арифметической прогрессии: $a_n = a_1 + d \cdot (n-1)$, где $d$ — это разность арифметической прогрессии, которая по условию (хоть и негласно) равна единице. Зная это, из последней формулы выведем, что $n = a_n-a_1 + 1$. Теперь же, когда мы знаем все необходимые значения, остается только подсчитать сумму арифметической прогрессии по ранее данной формуле и подать результат на выход.

Ссылки

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