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 1507. История Лаурела-Харди

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

Задача

Лаурел и Харди — два известных киногероя $50$-ых. Они известны своей разницей в весе, как можно увидеть на картинке. Если Вы еще не разобрались, кто из них кто, то я добавлю, что Лаурел легче. В свои юношеские годы Лаурел и Харди любили играть со странными качелями, и когда качели находились в равновесии, то Харди всегда был у земли. Мы рассмотрим двумерную версию качель.

Качели, которыми пользовались Лаурел и Харди, представляют собой часть окружности радиуса $r$, как показано на картинке (они закрашены серым и имеют вид буквы $D$). Харди сел на точку $B$ (самая правая точка качель), а Лаурел сел на точку $A$ (самая левая точка отрезка $AB$). $d = EF$ — расстояние между центром отрезка $AB$ и дуги $AFB$. То есть $E$ — середина отрезка $AB$, а $F$ — середина дуги $AFB$. $MN$ — основа качель, является горизонтальной прямой. $BD = h_1$ — расстояние от Харди до земли. Вам необходимо найти расстояние от Лаурела до земли (обозначаемое $h_2 = AC$).

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

Первая строка содержит количество тестов $N \space (0 < N ≤ 1000)$. Каждая из следующих $N$ строк представляет собой отдельный тест, который имеет следующий формат:

Каждая строка содержит три целых числа $r \space (10 ≤ r ≤ 100), \space$ $d \space (5 ≤ d ≤ r), \space$ $h_1 \space (5 ≤ h_1 ≤ d)$. Значение этих чисел приведено выше.

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

Для каждого теста в отдельной строке вывести его номер и действительной число — значение $h_2$. Это число должно содержать четыре десятичных знака. Формат вывода приведен в примере.

Тесты

Входные данные	Выходные данные
2 10 10 10 10 7 6	Case 1: 10.0000 Case 2: 8.0342
3 12 7 7 11 11 8 54 12 6	Case 1: 7.0000 Case 2: 14.0000 Case 3: 19.7383
5 94 21 12 23 9 8 5 4 3 2 2 1 43 26 20	Case 1: 32.1226 Case 2: 10.0439 Case 3: 5.0440 Case 4: 3.0000 Case 5: 32.4231

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

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);
		
		short N = in.nextShort();
		double r, d, h_1, a, b;
		for (int i = 1; i <= N; i++){
			r = in.nextDouble();
			d = in.nextDouble();
			h_1 = in.nextDouble();
			out.print("Case " + i + ": ");
			a = Math.asin((r - h_1) / r) - Math.asin((r - d) / r);
			if (a == 0){
				out.format("%.4f%n", h_1);
			}
			else{
				b = 2 * Math.sqrt(r*r - (r - d) * (r - d)) + h_1 / Math.sin(a);
				out.format("%.4f%n", b * Math.sin(a));
			}
		}
		
		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);

short N = in.nextShort();

double r, d, h_1, a, b;

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

r = in.nextDouble();

d = in.nextDouble();

h_1 = in.nextDouble();

out.print("Case " + i + ": ");

a = Math.asin((r - h_1) / r) - Math.asin((r - d) / r);

if (a == 0){

out.format("%.4f%n", h_1);

}

else{

b = 2 * Math.sqrt(r*r - (r - d) * (r - d)) + h_1 / Math.sin(a);

out.format("%.4f%n", b * Math.sin(a));

}

out.flush();

}

Решение

Для лучшего понимания решения данной задачи, я построил к ней чертеж, который вы можете видеть сверху. Но прежде чем приступить непосредственно к объяснению решения, я хотел бы обратить внимание на то, что мой рисунок (даже без дополнительных построений) немного отличается от данного нам в условии. Эти различия преднамеренны и метод решения справедлив для обоих рисунков.

В $10$ строке введем число $N$ из входного потока, а в $12$ — запустим цикл, который будет работать $N$ раз. Далее за каждый проход цикла будем читать по $3$ следующих числа из входного потока и выводить на экран номер текущего теста. Перед тем, как идти дальше, разберемся в рисунке. Так как по условию отрезок $EF$ делит сегмент $AFB$ пополам, то по свойствам хорд и дуг окружности, он является частью радиуса $r$ нашей окружности с центром в точке $O$ и перпендикулярен хорде $AB$, что и показано на чертеже. Кроме того, я дорисовал радиусы $OA$ и $OB$ окружности к соответствующим точкам и начертил отрезок $BH$, как продолжение $AB$, от точки $B$ до прямой $MN$. Также, я построил прямоугольный треугольник $\triangle OGB$, в котором катет $OG = r-BD$.
Достроив все необходимые отрезки, легко заметить, что мы имеем прямоугольный треугольник $\triangle ACH$ с катетом $AC$, длину которого нам и нужно найти по условию задачи. Предлагаю сделать это, воспользовавшись формулой $AC = AH \cdot \sin(\angle AHC)$. Найдем значения сомножителей.

Из рисунка очевидно, что $\angle AHC = \angle BHD = \angle EBG = \angle OBG-\angle OBE.$
Сначала найдем $\angle OBG$. Для этого рассмотрим треугольник $\triangle OGB$. Длины его гипотенузы и противолежащего к искомому углу катета нам уже известны, так что можем сразу найти $\angle OBG = \arcsin \frac{OG}{OB}$.
Теперь найдем $\angle OBE$. Рассмотрим прямоугольный треугольник $\triangle OEB$. В нем противолежащий искомому углу катет $OE = r-d$, а гипотенуза $OB = r$. Значит, $\angle OBE = \arcsin \frac{OE}{OB}$.
В итоге остаётся только найти разницу этих углов, которая и будет являться величиной искомого $\angle AHC$. В коде же значение этого угла считается в $17$ строке и присваивается переменной a .

Стоит заметить, что если $\angle OBG-\angle OBE = 0$, то длины отрезков $AC$ и $BD$, очевидно, совпадают. В таком случае можем сразу вывести на экран $h_2 = h_1$, как мы и поступили в $19$ строке, и перейти к нахождению $AC$ уже для следующего тестового случая.

Если же величина $\angle AHC$ отлична от $0$, то нам все еще предстоит посчитать длину гипотенузы $AH$ треугольника $\triangle ACH$. Она состоит из хорды $AB$ и отрезка $BH$.
Сперва найдем длину хорды. Известно, что $OF$ делит ее на $2$ одинаковых по длине отрезка, значит, следует опять рассмотреть треугольник $\triangle OEB$. Длину его гипотенузы и одного из катетов мы уже находили, так что просто применим теорему Пифагора и найдем $EB = \sqrt{OB^2-OE^2}$. Тогда $AB = 2 \cdot EB$.
Для нахождения длины $BH$, рассмотрим треугольник $\triangle BDH$, в котором этот отрезок является гипотенузой. Длину катета $BD$ и величину угла $\angle BHD$ мы уже знаем, значит, можем применить формулу $BH = \frac{BD}{\sin(\angle BHD)}$.
Сложим найденные значения длин хорды $AB$ и отрезка $BH$, чтобы получить $AH$. В коде эта длина находится в $22$ строке и присваивается переменной b .

Теперь остается только подставить найденные значения в ранее приведенную формулу и получить наконец длину $h_2$, которую выведем на экран в $23$ строке.

Ссылки

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

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++