Category Archives: 2. Алгоритмы с ветвлением

Алгоритмы с ветвлением предполагают наличие «точек принятия решения» в которых происходит выбор пути по которому пойдёт вычислительный процесс. После исключения из практики программирования операторов перехода goto (из-за запутывания кода и сложности его восприятия человеком), ветвление стало самым «нежелательным» элементом программирования. Однако пока его использование неизбежно. Но старайтесь не злоупотреблять им. Всегда хорошо продумывайте структуру ветвлений и делайте ее читаемой.
Для реализации ветвления в Java обычно используют условный оператор (if, if-else) или оператор выбора или оператор-переключатель (switch). Оператор switch обычно используют, когда нужно разветвить вычислительный процесс на количество веток более чем две. Практически это множественный оператор условного перехода на одну из меток в программе в зависимости от значения некоторого выражения. Этим он кардинально отличается от условного оператора в котором ветки полностью изолированы друг от друга. Т.е. после перехода на соответствующую метку, программа продолжает выполняться дальше по всем записанным ниже веткам. Для изменения такого поведения приходится в нужных местах расставлять оператор break. Потренируйтесь в написании оператора переключателя на этой несложной задаче.
Близкой к операторам ветвления является тернарная условная операция ?:. Однако цель её использования несколько иная. Тернарная условная операция возвращает значение своего второго или третьего операнда в зависимости от истинности логического выражения, которое стоит на месте первого операнда. Т.е. фактически ветвление происходит внутри скрытой от нас реализации этой операции, но не в нашей программе. Не используйте условный оператор там, где можно использовать тернарную условную операцию. Например, если необходимо напечатать слова «четный»/»нечетный» в зависимости от значения числа, то условному оператору здесь не место.

Задачи

Даны действительные числа [latex]x[/latex], [latex]y[/latex]. Получить [latex]\max (x, y)[/latex].
Даны действительные числа [latex]x[/latex], [latex]y[/latex]. Получить [latex]\min (x, y)[/latex].
Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Получить [latex]\max (x, y,z)[/latex].
Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Получить [latex]\min (x, y,z)[/latex].
Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Проверить, выполняются ли неравенства [latex]x < y < z[/latex].
Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Вывести наименьшее и наибольшее из них. Если наименьших или наибольших чисел окажется несколько, то укажите в скобках количество.
Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Могут ли они быть длинами сторон некоторого треугольника?
Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex], задающие длины сторон некоторого треугольника. Будет ли треугольник остроугольным, тупоугольным или прямоугольным? Какой из трёх случаев самый маловероятный
Четырёхугольник [latex]ABCD[/latex] задан на плоскости целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Из характеристик указать наиболее частную.
Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин на плоскости, определить имеют ли они общие точки.
Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин на плоскости.
Банк предлагает три вида депозитов на 3 месяца ([latex]p_3%[/latex] годовых), на 6 месяцев ([latex]p_6%[/latex] годовых) и на 12 месяцев ([latex]p_12%[/latex] годовых). Какой депозит принесёт больше дохода при многолетнем вложении.
По заданным значениям температуры [latex]t[/latex] и давления [latex]p[/latex] определите в каком состоянии находится вода. Для решения воспользуйтесь фазовой диаграммой воды и её приближённым описанием.
Четырёхугольник [latex]ABCD[/latex] в трёхмерном пространстве задан целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник, точки не лежат в одной плоскости. Из характеристик указать наиболее частную.
Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин в трёхмерном пространстве, определить имеют ли они общие точки.
Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин в четырёхмерном пространстве.

e-olymp 2999. Функция — 10

20/11/2018 by Валерия Ларикова

Задача

Дана функция, аргументы которой – неотрицательные целые числа [latex]m[/latex] и [latex]n[/latex] [latex](m \leqslant n):[/latex]

$$f(m,n)=\begin{cases} 1, \text{ npu } m=0 \\\\ f(m-1,n-1)+f(m,n-1), \text{ npu } 0<m<n \\\\ 1, \text{ npu } m=n \end{cases}$$

Вычислить значение функции.

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

Два целых неотрицательных числа [latex]n[/latex] и [latex]m[/latex] [latex](0 \leqslant n, m \leqslant 20).[/latex]

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

Выведите искомое значение заданной функции [latex]f(m, n).[/latex]

Тесты

#	Входные данные	Выходные данные
1	4 2	6
2	7 7	1
3	12 0	1
4	15 5	3003
5	10 6	210

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m, d;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		d = func(m, n); 
		System.out.print(d);
	}
	public static int func (int m, int n){
		if (m == 0 || m == n) return 1;
		else return func(m - 1, n - 1) + func(m, n - 1);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int n, m, d;

Scanner in = new Scanner(System.in);

n = in.nextInt();

m = in.nextInt();

d = func(m, n);

System.out.print(d);

}

public static int func (int m, int n){

if (m == 0 || m == n) return 1;

else return func(m - 1, n - 1) + func(m, n - 1);

}

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

Для того, чтобы решить задачу, нам необходимо составить алгоритм, который будет вычислять значение заданной функции в зависимости от значения её аргументов. Для этого создадим специальную функцию func(). Строки 16 — 19 кода составляют тело функции. Программа выбирает, какую операцию ей нужно выполнить, в зависимости от определенного условия:

Если [latex]m = 0[/latex] или [latex]m = n[/latex], то программа возвращает единицу.
Если [latex]m < n[/latex], то программа вычисляет значение функции по формуле [latex]f(m-1,n-1)+f(m,n-1)[/latex]

Затем в главной функции вызываем нашу вспомогательную функцию func() с помощью новой переменной [latex]d[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 2370. Автоматизированная Телефонная Станция

18/11/2018 by Карина Миловская

Задача

В Санкт-Петербурге телефонные номера имеют формат “XXX — XX — XX” , где первые три цифры представляют собой индекс Автоматизированной Телефонной Станции (АТС). Каждая АТС имеет в точности $10000$ уникальных телефонных номеров. Петр только что приобрел новую квартиру и хочет установить телефонную линию. По его мнению телефонный номер является счастливым, если значение арифметического выражения, которое он собой представляет, равно нулю. Например, телефонный номер $102—40—62$ является счастливым $\left ( 102 — 40 — 62 = 0\right )$, а номер $157—10—47$ таковым не является $\left ( 157 — 10 — 47 \neq 0\right )$.
Петр знает индекс АТС, которая обслуживает его дом. Он хочет подсчитать количество счастливых номеров, которое она может иметь.

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

Единственное целое число $n$ — индекс АТС Петра $\left ( 100 \leq n \leq 999 \right )$.

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

Одно число — количество счастливых телефонных номеров, которые имеются у АТС Петра.

Тесты

Входные данные	Выходные данные
$196$	3
$239$	$0$
$101$	$98$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, res = 0;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		if(n &lt; 199) {
			res = 199 - n;
		}
		else {
			res = 0;
		}  
		System.out.print(res);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int n, res = 0;

Scanner in = new Scanner(System.in);

n = in.nextInt();

if(n < 199) {

res = 199 - n;

}

else {

res = 0;

}

System.out.print(res);

}

Решение

Рассмотрим случай, когда номер абонентской группы Петра $100,$ тогда счастливых номеров будет $ 99 \left ( 99+1, 98+2, \dots \right ).$ Далее рассмотрим случай, когда индекс $101,$ теперь количество счастливых номеров — $98 \left ( 99+2, 98+3, \dots \right ).$ В этом случае, если первые $2$ цифры после индекса и последние $2$ цифры номера будут равны $01,$ то этот номер уже не будет являться счастливым номером. Теперь на замену счастливому номеру $100 — 50 — 50$ идут $2$ счастливых номера: $101 — 50 — 51$ и $101 — 51 — 50.$ Суммарно количество счастливых номеров уменьшилось на $1.$ Пользуясь данной логикой, в каждой последующей абонентской группе будет на $1$ счастливый номер меньше. Для $n < 198$ счастливых номеров не будет. Следовательно, количество счастливых телефонных номеров, которые имеются у АТС Петра мы можем вычислить по формуле $199 — n$.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp-7410.Маршрутне таксі

05/11/2018 by Даниель Савчак

Задача

У годину пік на зупинку одночасно під’їхали три маршрутних таксі, які слідують по одному маршруту, в які тут же набилися пасажири. Водії виявили, що кількість людей у різних маршрутках різна, і вирішили пересадити частину пасажирів так, щоб у кожній маршрутці було порівну пасажирів. Потрібно визначити, яку найменшу кількість пасажирів доведеться при цьому пересадити.

Вхідні дані

Три натуральних числа, що не перевищують [latex]100[/latex] — кількості пасажирів у першій, другій і третій маршрутках відповідно.

Вихідні дані

Виведіть одне число — найменшу кількість пасажирів, яку потрібно пересадити. Якщо це неможливо, виведіть слово [latex]IMPOSSIBLE[/latex] (великими літерами).

Тести

Вхідні дані	Вихідні дані
[latex]1[/latex] [latex]1[/latex] [latex]4[/latex]	[latex]2[/latex]
[latex]1[/latex] [latex]2[/latex] [latex]4[/latex]	[latex]IMPOSSIBLE[/latex]
[latex]1[/latex] [latex]3[/latex] [latex]5[/latex]	[latex]2[/latex]
[latex]9[/latex] [latex]3[/latex] [latex]9[/latex]	[latex]4[/latex]

Код програми

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int m1,m2,m3,x;
		m1 = in.nextInt();
		m2 = in.nextInt();
		m3 = in.nextInt();
		if ( ( m1 + m2 + m3 ) % 3 == 0 ) 
		{
			if ( m1 != m2 && m1 != m3 && m2 != m3 ) 
			{
				System.out.print(Math.max ( Math.max ( m1 , m2 ) , m3 ) - ( ( m1 + m2 + m3 ) / 3 ));
			}
			else if ( m1 == m2 ) 
			{ 
            	x = ( m3 - ( m1 + m2 + m3 ) / 3 );
            	if ( x < 0 ) 
            	{ 
                	System.out.print(-x); 
            	} 
            	else System.out.print(x);
    		}
    		else if ( m1 == m3 ) { 
            	x = ( m2 - ( m1 + m2 + m3 ) / 3 );
            	if ( x < 0 ) 
            	{ 
                	System.out.print(-x);
            	} 
            	else System.out.print(x);
    		}
    		else if ( m2 == m3 ) { 
            	x = ( m1 - ( m1 + m2 + m3 ) / 3 );
            	if ( x < 0 ) 
            	{ 
                	System.out.print(-x); 
            	} 
            	else System.out.print(x);
            }
		}
		else System.out.print("IMPOSSIBLE");
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

import java.lang.Math;

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

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int m1,m2,m3,x;

m1 = in.nextInt();

m2 = in.nextInt();

m3 = in.nextInt();

if ( ( m1 + m2 + m3 ) % 3 == 0 )

{

if ( m1 != m2 && m1 != m3 && m2 != m3 )

{

System.out.print(Math.max ( Math.max ( m1 , m2 ) , m3 ) - ( ( m1 + m2 + m3 ) / 3 ));

}

else if ( m1 == m2 )

{

x = ( m3 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 )

{

System.out.print(-x);

}

else System.out.print(x);

}

else if ( m1 == m3 ) {

x = ( m2 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 )

{

System.out.print(-x);

}

else System.out.print(x);

}

else if ( m2 == m3 ) {

x = ( m1 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 )

{

System.out.print(-x);

}

else System.out.print(x);

}

else System.out.print("IMPOSSIBLE");

}

Рішення завдання

Спочатку відріжемо усі варіанти при яких розподілити пасажирів порівну не вийде так, що коли іх загальна кількість не ділиться націло на [latex]3[/latex] виводимо [latex]IMPOSSIBLE[/latex]. Коли розподілити пасажирів можна, розглядаємо [latex]4[/latex] випадки : коли у різних маршрутках кількість людей різна та коли у будь-яких двох маршрутках кількість однакова. Коли кількість різна, від максимальної кількості людей у трьох маршрутках віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей(у кінці ми маємо отримати це число, як кількість пасажирів у всіх маршрутних таксі), коли у двох маршрутках кількість однакова , то від кількості людей(у маршрутці, де іх більше або менше) віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей. Якщо відповідь менше [latex]0[/latex] то помножуюмо на [latex]-1[/latex].

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

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
Код решения

e-olimp 197. Отрезок и окружности

27/09/2018 by Антон Джашимов

Задача

На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны $1,2,3\dots.$ Также на плоскости задан отрезок, концы которого находятся в точках $(X_{1}, Y_{1})$ и $(X_{2}, Y_{2}).$ Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

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

Первая строка входного файла содержит 4 целых числа $X_{1}, Y_{1}, X_{2}, Y_{2}.$ Эти числа не превосходят $10^{3}$ по абсолютной величине. Заданный отрезок имеет ненулевую длину.

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

В выходной файл выведите ответ на задачу.

Тесты

Входные данные	Выходные данные
-1 -1 1 1	2
-1 1 1 1	1
1 1 2 1	1
-5 -5 5 -5	5
-10 10 -10 10	28

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

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

class Main {
    public static void main(String[] args) throws java.lang.Exception {
        final double e = 10e-8;
        Scanner in = new Scanner(System.in);
        double x1, y1, x2, y2;
        x1 = in .nextDouble();
        y1 = in .nextDouble();
        x2 = in .nextDouble();
        y2 = in .nextDouble();
        double d, a, b;
        d = Math.abs((y2 * x1 - x2 * y1) / Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
        //Растояние до точки на отрезке, ближайщей к началу координат
        a = Math.sqrt(x1 * x1 + y1 * y1);
        //Растояние от начала координат до первой точки
        b = Math.sqrt(x2 * x2 + y2 * y2);
        //Растояние от начала координат до второй точки
        int count = 0;
        if ((2 * x1 * x1 - 2 * x1 * x2 + 2 * y1 * y1 - 2 * y1 * y2 < 0) | (2 * x2 * x2 - 2 * x1 * x2 + 2 * y2 * y2 - 2 * y1 * y2 < 0))
            //проверка первого условия
            count = (int)(Math.max(a, b) + e) - (int)(Math.min(a, b) - e);
        else {
            //второе условие
            count = (int)(a + e) - (int)(d - e);
            count = count + (int)(b + e) - (int)(d - e);
            if ((Math.abs(Math.round(d) - d) < e) & (Math.abs(d) > e)) {
                //проверка крайнего случая
                count--;
            }
        }
        System.out.print(count);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

final double e = 10e-8;

Scanner in = new Scanner(System.in);

double x1, y1, x2, y2;

x1 = in .nextDouble();

y1 = in .nextDouble();

x2 = in .nextDouble();

y2 = in .nextDouble();

double d, a, b;

d = Math.abs((y2 * x1 - x2 * y1) / Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));

//Растояние до точки на отрезке, ближайщей к началу координат

a = Math.sqrt(x1 * x1 + y1 * y1);

//Растояние от начала координат до первой точки

b = Math.sqrt(x2 * x2 + y2 * y2);

//Растояние от начала координат до второй точки

int count = 0;

if ((2 * x1 * x1 - 2 * x1 * x2 + 2 * y1 * y1 - 2 * y1 * y2 < 0) | (2 * x2 * x2 - 2 * x1 * x2 + 2 * y2 * y2 - 2 * y1 * y2 < 0))

//проверка первого условия

count = (int)(Math.max(a, b) + e) - (int)(Math.min(a, b) - e);

else {

//второе условие

count = (int)(a + e) - (int)(d - e);

count = count + (int)(b + e) - (int)(d - e);

if ((Math.abs(Math.round(d) - d) < e) & (Math.abs(d) > e)) {

//проверка крайнего случая

count--;

}

System.out.print(count);

}

Решение

Для начала рассмотрим первое условие. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до начала координат возрастает. Для такого отрезка ответ очевиден — это количество целых чисел между расстояниями от начала координат до обоих концов отрезка. Условие из шестнадцатой строчки кода получилось путем приведения подобных и раскрытия скобок следующих неравенств: $x_{1}^{2}+y_{1}^{2}-x_{2}^{2}-y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0$ и $-x_{1}^{2}-y_{1}^{2}+x_{2}^{2}+y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0.$

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

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее. Также мы добавляем маленькую константу
$\varepsilon = 10^{-8}$ к большему расстоянию до конца отрезка и отнимаем из меньшего, чтобы избежать случая нахождения какой-либо точки отрезка на окружности. В противном случае решение задачи будет работать не корректно.

Ссылки

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

e-olymp 43. Количество участников олимпиады

21/09/2018 by Дима Мороз

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью.

В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d (1 ≤ k, n, m, d ≤ 1000)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$	$n$	$m$	$d$	Выходные данные
2	4	7	3	28
4	5	2	1	20
3	7	5	4	-1
6	6	6	1	-1
2	3	6	4	-1
3	2	5	8	-1

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		float k = in.nextInt(), n = in.nextInt(), m = in.nextInt(), d = in.nextInt(), s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);
		if ((1 / k + 1 / n + 1 / m >= 1) | (Math.floor(s / k) != s / k | Math.floor(s / n) != s / n | Math.floor(s / m) != s / m) | !(Math.floor(s) == s))
			System.out.println(-1);
		else System.out.println(Math.round(s));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

float k = in.nextInt(), n = in.nextInt(), m = in.nextInt(), d = in.nextInt(), s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);

if ((1 / k + 1 / n + 1 / m >= 1) | (Math.floor(s / k) != s / k | Math.floor(s / n) != s / n | Math.floor(s / m) != s / m) | !(Math.floor(s) == s))

System.out.println(-1);

else System.out.println(Math.round(s));

}

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

Пусть $x$ — количество учеников Пифагора. Тогда $\displaystyle\frac{x}{2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\displaystyle\frac{x}{4}$ — ученики, которые изучают природу, а $\displaystyle\frac{x}{7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.

Получили уравнение вида $\displaystyle\frac{x}{2} + \frac{x}{4} + \frac{x}{7} + 3 = x$, в общем виде $\displaystyle\frac{x}{k} + \frac{x}{m} + \frac{x}{n} + d = x$.
Отсюда выходит, что $\displaystyle\frac{1}{k} + \frac{1}{m} + \frac{1}{n} + dx = 1;$

$\displaystyle\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$

$\displaystyle(mn + kn + km)x + kmnd = kmnx;$

Отсюда получаем формулу $\displaystyle x = \frac{kmnd} {kmn — mn — kn — km}$.

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

Для того, чтобы проверить, является ли переменная x целым числом или нет, используем метод floor() из класса Math.

Помимо этого делаем проверку для суммы чисел $\displaystyle\frac{1}{k}$, $\displaystyle\frac{1}{n}$ и $\displaystyle\frac{1}{m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\displaystyle\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\displaystyle\frac{q}{k}$, $\displaystyle\frac{q}{n}$ и $\displaystyle\frac{q}{m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

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

Mif 2. Максимум из трех

12/12/2017 by Сидоровский Дмитрий

Задача

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Получить [latex]max (x, y, z)[/latex].

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

Действительные числа $latex x,y,z$.

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

[latex]max (x, y, z)[/latex]

Тесты

x	y	z	max
8	3	5	8
9	16	7	16
5	125	150	150

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

class Ideone
{
  public static void main (String[] args) throws java.lang.Exception
  {
    double x, y, z;
    Scanner in = new Scanner(System.in);
    x = in.nextDouble();
    y = in.nextDouble();
    z = in.nextDouble();
    double max = z;
    if ( y > max)
      {
        max = y;
      }
    if ( x > max ) 
      {
        max = x;
      }
    System.out.println(max);
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double x, y, z;

Scanner in = new Scanner(System.in);

x = in.nextDouble();

y = in.nextDouble();

z = in.nextDouble();

double max = z;

if ( y > max)

{

max = y;

}

if ( x > max )

{

max = x;

}

System.out.println(max);

}

Решение

Пусть даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Нужно получить [latex]max(x,y,z)[/latex]. Для этого вводим [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Предполагаем, что $latex z$ хранит максимальное значение. Затем, используя оператор if, сравниваем $latex y, x$. Выводим максимальное значение.

Пример работы программы можно увидеть на ideone.

A60г

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

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть [latex]u[/latex] определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом: [latex] u=\begin{cases}x^(2)-1;\text{if}(x,y)\in D \\\sqrt{\left| x-1\right|};\text{ another case }\end{cases}[/latex] (запись[latex](x,y)\in D[/latex] означает, что точка с координатами [latex]x,y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y[/latex] Определить [latex]u.[/latex]

Тесты:

№	ВХОД		ВЫХОД
	[latex]x[/latex]	[latex]y[/latex]	[latex]u[/latex]
1	0.3	0.3	0.836660
2	1	1	0.000000
3	2	2	1.000000
4	0	0	-1.000000

Код:

import java.util.*;

public class dash {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.printf("Введите x: ");
        float x = in.nextFloat();
        System.out.printf("Введите y: ");
        float y = in.nextFloat();
        float a=x*x+y*y;

        if((y<0)||(a>1)||((x>0)&&(a<0.3)))
        {
            System.out.format("u=%f", Math.sqrt(Math.abs(x-1)));
        } else
        {
            System.out.format("u=%f",x*x-1);
        }
    }
}

import java.util.*;

public class dash {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.printf("Введите x: ");

float x = in.nextFloat();

System.out.printf("Введите y: ");

float y = in.nextFloat();

float a=x*x+y*y;

if((y<0)||(a>1)||((x>0)&&(a<0.3)))

{

System.out.format("u=%f", Math.sqrt(Math.abs(x-1)));

} else

{

System.out.format("u=%f",x*x-1);

}

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex]y<0.[/latex] Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3.

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

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

e-olymp 923. Время года

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

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

Определить название времени года по заданному номеру месяца, используя составные условия.

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

Одно число — номер месяца.

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

Для весенних месяцев вывести Spring, для летних — Summer, для осенних — Autumn и для зимних — Winter.

Тесты

№	Входные данные	Выходные данные
1	5	Spring

Код

import java.util.*;

class Task2
{
	public static void main (String[] args)
	{
		int a=0;
        Scanner in = new Scanner(System.in);
		a = in.nextInt();
        if (a>2 && a<=11) 
		{    
			if (a>=6 && a<=8) System.out.printf("Summer");
            else if (a>=3 && a<=5) System.out.printf("Spring");
			else System.out.printf("Autumn");
		}
		else System.out.printf("Winter");
	}
}

import java.util.*;

class Task2

{

public static void main (String[] args)

{

int a=0;

Scanner in = new Scanner(System.in);

a = in.nextInt();

if (a>2 && a<=11)

{

if (a>=6 && a<=8) System.out.printf("Summer");

else if (a>=3 && a<=5) System.out.printf("Spring");

else System.out.printf("Autumn");

}

else System.out.printf("Winter");

}

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

Для решения данной задачи необходимо использовать переменную с целочисленным значением, которое соответствует порядковому номера месяца (от $latex 1$ до $latex 12$ включительно). Вводим переменную и выводим, какому времени года принадлежит введённый нами месяц, поочерёдно проверяя, какому из условий удовлетворяет переменная.

Посмотреть, как работает программа со входными данными $latex 12$ можно на сайте ideone.