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 1288. n-значные числа

05/12/2020 by Владислав Стасюк

Задача:

Сколько натуральных $n$ -значных чисел начинаются с цифры $a$ или цифры $b$?

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

Заданы три целых числа: натуральное $n$ [latex](0 \lt n \leqslant 10^6)[/latex] и целые $a$ и $b$. Все данные, как и само условие задачи, заданы в десятичной системе счисления.

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

Вывести количество натуральных $n$ -значных чисел, которые начинаются с цифры $a$ или цифры $b$.

Тесты:

ВВОД	ВЫВОД
3 3 4	200
1 2 2	1
4 0 0	0
10 9 9	1000000000

Код (Вариант 1):

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

class Main
{
  public static void main (String[] args)
  {
    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        int a = sc.nextInt(); 
        int b = sc.nextInt(); 
        String s = new String();
        if(a + b == 0){
          System.out.print(0);
        } else{
          if((a == b) | (a * b == 0)) System.out.print(1);
        else System.out.print(2);
          for (int i = 0; i < n - 1; i++){
            s += '0';
        } 
     } System.out.print(s);
 }

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int a = sc.nextInt();

int b = sc.nextInt();

String s = new String();

if(a + b == 0){

System.out.print(0);

} else{

if((a == b) | (a * b == 0)) System.out.print(1);

else System.out.print(2);

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

s += '0';

}

} System.out.print(s);

}

Код (Вариант 2):

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

class Main
{
  public static void main (String[] args)
  {
    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        int a = sc.nextInt(); 
        int b = sc.nextInt();
        int cond1 = a != b ? 1 : 0;
        int cond2 = a * b > 0 ? 1 : 0;
        String s = new String();
        System.out.print(cond1 + cond2);
        for(int i = 1; i  0; ++i) System.out.print(0);
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int a = sc.nextInt();

int b = sc.nextInt();

int cond1 = a != b ? 1 : 0;

int cond2 = a * b > 0 ? 1 : 0;

String s = new String();

System.out.print(cond1 + cond2);

for(int i = 1; i 0; ++i) System.out.print(0);

}

Решение:

Среди однозначных чисел с каждой цифры начинается только одно число.
Среди двухзначных чисел с одной цифры начинается уже десять чисел.
Среди трехзначных — сто и так далее. Легко заметить закономерность, что в количестве чисел, начинающихся с определенной цифры, единица всегда остается, а к ней приписывают $n-1$ нулей, где $n$ — количество разрядов.
Если мы ищем количество чисел начинающихся уже с двух разных цифр, то единица меняется на двойку, а количество нулей сохраняется.

Отсюда и решение задачи — последовательная проверка всех вариантов и вывод ответа.

P.S. Данное решение не проходит тесты 12-19 на сайте e-olymp. Это происходит из-за того, что в этих тестах результат — это число с большим количеством нулей, а язык Java тратит много времени на их вывод. То есть, тесты не выполняются только из-за времени работы. Решение этой задачи на языке С++ проходит без проблем все тесты.

Ссылки:

Задача на e-olymp
Решение №1 ideone
Решение №2 ideone

e-olymp 9107. Не разделяйте атом!

25/11/2020 by Владислав Шиманский

Задача

Два сумасшедших (и злых) ученых, профессор Зум и доктор Ужасный, только что получили [latex] n [/latex] атомов очень редкого элемента, которым они хотят поделиться между собой. Они решили сыграть в следующую игру:

Сначала профессор делит атомы на две непустые группы. Затем доктор берет одну группу и использует ее для своих злых целей, а другую разделяет на две непустые части. Затем профессор берет одну из частей и снова делит другую на две части, возвращая ее доктору. Игра продолжается — с каждым ходом ученый берет одну из частей и разделяет другую — пока один из игроков не будет вынужден разделить один атом. Это приводит к взрыву, и неудачный сплиттер проигрывает игру (вероятно, с его жизнью).

Зная количество атомов [latex] n [/latex], определите, кто из злодеев выживет в игре.

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

Первая строка содержит количество тестов [latex] z [/latex] [latex]left(1 leqslant zleqslant50right)[/latex] . Далее следуют описания тестов.

Каждый тест содержит одно целое число [latex] n [/latex] [latex]left(1 leqslant n leqslant10^{6}right)[/latex] — начальное количество атомов.

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

Для каждого теста выведите строку, содержащую один символ: ‘A‘, если профессор выиграет игру, и ‘B‘, если победит доктор

Тесты

№	Входные данные	Выходные данные
1	2 5 6	B A
2	2 2 17	A B
3	2 11 15	B B
4	2 12 16	A A
5	3 101 110 111	B A B

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

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

class Main
{
	public static void main(String args[]) {
    int z;
    int n= 0;
    Scanner input = new Scanner(System.in);
    z = input.nextInt();
	for(int i=0;i&lt;z;i++){
    	n = input.nextInt();
    	if (n % 2 == 0 )
        	System.out.println("A");
    	else
        	System.out.println("B");
	}
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main(String args[]) {

int z;

int n= 0;

Scanner input = new Scanner(System.in);

z = input.nextInt();

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

n = input.nextInt();

if (n % 2 == 0 )

System.out.println("A");

else

System.out.println("B");

}

Решение

Решение задачи сводиться к проверке начального количества атомов ([latex]n[/latex]), которое они хотят поделить между собой, на чётность и нечётность. По условию мы знаем, что профессор первый делит атомы на две непустые группы, следовательно, он может воспользоваться преимуществом первого хода и задавать тон игре. Для победы профессора нужно сделать так, чтоб доктор разделил последний атом, что приведёт к его проигрышу. Значит, для победы нужно чётное количество атомов, так как только при этом случае он может придерживаться стратегии и делить на две непустые группы с нечётным количеством атомов (это может быть [latex]1[/latex] и [latex]n — 1[/latex]) до тех пор, пока его противнику не достанется [latex]1[/latex], что приведёт к взрыву (при нечётном количестве атомов, невозможно с первого хода поделить на две нечётные непустые группы).
Для проверки на чётность и нечётность, необходимо проверить равен ли нулю остаток от деления начального количества атомов ([latex]n[/latex]) на [latex]2[/latex], используя условный оператор.

Ссылки

e-olymp 1142. Деление на ноль или…

30/09/2020 by Лаура Казарян

Задача

Как известно, делить на ноль нельзя. А может еще на что-то делить нельзя? Это Вам и предстоит выяснить.

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

В единственной строке задано два целых знаковых 32-битовых числа $a$ и $b$.

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

Выведите значение частного, полученного в результате деления $a$ на $b$. Если деление произвести невозможно, вывести ERROR.

Тесты

№	Входные данные	Выходные данные
1	8 4	2
2	6 0	ERROR
3	0 4	0
4	613 18	34
5	9197 10000	0

Код

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

class Main
{
	public static void main (String[] args) 
	{
		Scanner sc = new Scanner(System. in );
        long a = sc.nextInt(); 
        long b = sc.nextInt(); 
        if(b != 0) System.out.print(a/b);
        else System.out.print("ERROR");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

Scanner sc = new Scanner(System. in );

long a = sc.nextInt();

long b = sc.nextInt();

if(b != 0) System.out.print(a/b);

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

}

Решение

В задаче, единственной невозможной операцией является деление на ноль. Это условие можно проверить с помощью условных операторов if и else. Также, так как $a$ и $b$ являются целыми 32-битными числами, необходимо использовать тип переменных long.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

e-olymp 8680. Чётные соседи

19/09/2020 by Аліна Малихіна

Условие задачи

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

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

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2
2	9 3 6 3 5 2 9 1 2 5	0
3	3 2 1 2	1
4	6 13 24 54 66 44 77	2
5	4 100 224 666 222	2

Программный код

public class Main
{
	public static void main(String[] args) {
		java.util.Scanner Javain = new java.util.Scanner(System.in);
	    int i=1, n, prev, pres, fut, count = 0;
        n = Javain.nextInt();
        prev = Javain.nextInt(); //вводим предыдущий элемент
        pres = Javain.nextInt(); //вводим текущий элемент
        while (i <= n - 2) {
            fut = Javain.nextInt();
            if (prev % 2 == 0 && fut % 2 == 0) 
                count++;
                prev = pres; //приравниваем предыдущий к текущему
                pres = fut; //приравниваем текущий к будущему
                i++;
        }
        System.out.print(count); 
	}
}

public class Main

{

public static void main(String[] args) {

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

int i=1, n, prev, pres, fut, count = 0;

n = Javain.nextInt();

prev = Javain.nextInt(); //вводим предыдущий элемент

pres = Javain.nextInt(); //вводим текущий элемент

while (i <= n - 2) {

fut = Javain.nextInt();

if (prev % 2 == 0 && fut % 2 == 0)

count++;

prev = pres; //приравниваем предыдущий к текущему

pres = fut; //приравниваем текущий к будущему

i++;

}

System.out.print(count);

}

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

Задача на e-olymp
Код программы на Ideone
Засчитанное решение

e-olymp 4439. Возведение в степень

17/09/2020 by Владислав Гринькив

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 100	1
2	2 10	1024
3	3 7	2187
4	8 9	134217728
5	10 10	10000000000
6	100 9	1000000000000000000

Код

class Main{
  public static long pow(long a, long b){
    if(b == 0){ 
      return 1; 
    } 
    if(b % 2 == 0){ 
      return pow(a * a, b / 2); 
    } 
    return a * pow(a, b - 1);
  }
  public static void main (String[] args){
    java.util.Scanner in = new java.util.Scanner(System.in);
    long a = in.nextLong(), b = in.nextLong();
    System.out.println(pow(a,b));
  }
}

class Main{

public static long pow(long a, long b){

if(b == 0){

return 1;

}

if(b % 2 == 0){

return pow(a * a, b / 2);

}

return a * pow(a, b - 1);

}

public static void main (String[] args){

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

long a = in.nextLong(), b = in.nextLong();

System.out.println(pow(a,b));

}

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

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

e-olymp 8891. Ровно одно условие из двух

15/09/2020 by Владислав Стасюк

Задача

Для заданного целого числа $n$ вывести YES, если выполняется ровно одно из следующих условий и NO в противном случае.

число $n$ четное.
число $n$ отрицательное и кратное трем.

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

Одно целое число $n$.

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

Вывести YES или NO в зависимости от выполнения условий.

Тесты

ВВОД	ВЫВОД
22	YES
7	NO
-30	NO
-9	YES
0	YES

Код

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


class Main
{
    public static void main (String[] args)
    {
        int n;
        Scanner in = new Scanner(System.in);
        n = in.nextInt();

        System.out.println((n%2 == 0) == (n%3 == 0 & n<0)? "NO": "YES");
    }
}

import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args)

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

System.out.println((n%2 == 0) == (n%3 == 0 & n<0)? "NO": "YES");

}

Решение

Если оба условия выполняются или оба не выполняются, то нужно вывести «NO», а иначе — «YES».

В первом случае проверяем четность числа $n$.
Во втором случае проверяем кратность трем и является ли $n$ отрицательным.
В обеих случаях исключаем варианты, когда оба условия могли бы выполнятся, то есть исключаем отрицательные числа и кратность трем для первого, и четность числа для второго случая.

Ссылки

e-olymp
ideone

e-olymp 8663. Задача про множення

14/09/2020 by Эвелина Алексютенко

Задача

На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [latex]N[/latex]. Допоможіть розв’язати задачу.

Вхідні дані

Одне число [latex]N(1\leqslant N\leqslant 2\times 10^{9})[/latex].

Вихідні дані

Максимальний добуток цифр серед чисел, що не перевищують [latex]N[/latex].

Тести

Вхідні дані	Вихідні дані
57	36
1000	729
7999	5103
28994	10368
4876	2268

Код програми

import java.util.Scanner;
public class Main {
	static int multiplication(int x) {
		    int mul = 1;
		    while(x != 0) {
		        mul *= x % 10;
		        x /= 10;
		    }
		    return mul;
	}
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int maxmul = multiplication(n);
		int copy = n;
		int i = 10;
		while(n!= 0) {
			int temporary_number = (copy / (i / 10)) % 10;
			int left = copy / i;
			int right = copy % (i / 10);
			if(temporary_number != 9) {
				temporary_number = 9;
				copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;
			}
			n /= 10;
			i *= 10;
			int mul = multiplication(copy);
			if(maxmul < mul) maxmul = mul;
		}
		System.out.println(maxmul);
	}
	
}

import java.util.Scanner;

public class Main {

static int multiplication(int x) {

int mul = 1;

while(x != 0) {

mul *= x % 10;

x /= 10;

}

return mul;

}

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int maxmul = multiplication(n);

int copy = n;

int i = 10;

while(n!= 0) {

int temporary_number = (copy / (i / 10)) % 10;

int left = copy / i;

int right = copy % (i / 10);

if(temporary_number != 9) {

temporary_number = 9;

copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;

}

n /= 10;

i *= 10;

int mul = multiplication(copy);

if(maxmul < mul) maxmul = mul;

}

System.out.println(maxmul);

}

Алгоритм

Складність задачі полягає в обмеженості у часі.

Знайдемо добуток цифр заданого числа.
Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
Порівнюємо поточний добуток з максимальним.

Приклад:

Приклад розкладу числа на різних етапах алгоритму:

Посилання

Задача на e-olymp
Зарахований розв’язок
Код на ideone

e-olymp 8352. Такси

14/09/2020 by Виктория Крачилова

Условие задачи

В час пик на остановку одновременно подъехали три маршрутных такси, следующие по одному маршруту, в которые тут же набились пассажиры. Водители обнаружили, что количество людей в разных маршрутках разное, и решили пересадить часть пассажиров так, чтобы в каждой маршрутке было поровну пассажиров. Требуется определить, какое наименьшее количество пассажиров придется при этом пересадить.

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

Три натуральных числа, не превосходящих $100$ — количество пассажиров в первой, второй и третьей маршрутках соответственно.

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

Выведите одно число — наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово IMPOSSIBLE (заглавными буквами).

Тесты

№	Ввод	Вывод
1	1 2 3	1
2	6 7 4	IMPOSSIBLE
3	18 10 2	8
4	54 10 96	IMPOSSIBLE
5	27 27 27	0

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int b1 = i.nextInt();
		int b2 = i.nextInt();
		int b3 = i.nextInt();
		if ((b1 + b2 + b3) % 3 != 0) {
			System.out.println("IMPOSSIBLE");
		}
		else {
			int average; // среднее арифметическое
			int count = 0; // наименьшее количество пассажиров, которое требуется пересадить
			average = (b1 + b2 + b3) / 3;
			if (b1 > average) count += b1 - average;
			if (b2 > average) count += b2 - average;
			if (b3 > average) count += b3 - average;
			System.out.println(count);
		}
	}
}

class Main

{

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

{

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

int b1 = i.nextInt();

int b2 = i.nextInt();

int b3 = i.nextInt();

if ((b1 + b2 + b3) % 3 != 0) {

System.out.println("IMPOSSIBLE");

}

else {

int average; // среднее арифметическое

int count = 0; // наименьшее количество пассажиров, которое требуется пересадить

average = (b1 + b2 + b3) / 3;

if (b1 > average) count += b1 - average;

if (b2 > average) count += b2 - average;

if (b3 > average) count += b3 - average;

System.out.println(count);

}

Решение

Мы сможем рассадить пассажиров поровну в три маршрутки только тогда, когда их общее количество кратно трем. Если это условие не выполняется, выводим на экран слово IMPOSSIBLE.

Иначе вычисляем среднее арифметическое исходного количества пассажиров каждой маршрутки по формуле: $\frac{b_{1}+b_{2}+b_{3}}{3}$ и находим минимальное количество пересаживаемых пассажиров, суммируя только положительные отклонения от среднего арифметического.

Ссылки

e-olymp 365. Рамка

14/09/2020 by Александр Рапчинский

Задача

Василий и Петр игрались на уроке. На прямоугольном листке бумаги в клеточку Василий по линях сетки рисует отрезок, параллельный одной из сторон листка, и рамку прямоугольной формы. Он шепчет на ухо Петру координаты концов отрезка и координаты двух противоположных углов рамки, а Петр старается быстро определить длину части отрезка, оказавшуюся внутри рамки. У него это плохо получалось, и он написал программу, которая это делала всегда правильно. Напишите её и вы.

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

Заданы через пробел $8$ чисел — координаты начала и конца отрезка и координаты противоположных углов рамки. Координаты — целые числа, не превышающие по модулю $35000$.

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

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

Тесты

№	Входные данные	Выходные данные
1	4 1 9 1 2 3 5 -2	1
2	2 2 6 2 4 4 7 1	2
3	3 2 3 5 4 3 6 2	0
4	1 2 5 2 2 5 4 1	2

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

class Main
{	
	static int distance(int a, int b, int c, int d)
	{
		int ans = 0;
		if (a > b) 
		{
			int temp = a;
			a = b;
			b = temp;
		}
		if (c > d)
		{
			int temp = c;
			c = d;
			d = temp;
		}
		if (b < c || a > d) 
		{
			ans = 0;
		} 
		else 
		{
			int l = 0, r = 0;
			l = Math.max(a, c);
			r = Math.min(b, d);
			ans = r - l;
		}
		return ans;
	}
	public static void main (String[] args) 
	{
		java.util.Scanner in = new java.util.Scanner(System.in);
		int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
		int x3 = in.nextInt(), y3 = in.nextInt(), x4 = in.nextInt(), y4 = in.nextInt();
		if (x1 != x2) 
		{
			System.out.println(y1 < Math.max(y3, y4) && y1 > Math.min(y3, y4) ? distance(x1, x2, x3, x4) : 0); 
		}
		else 
		{
			System.out.println(x1 < Math.max(x3, x4) && x1 > Math.min(x3, x4) ? distance(y1, y2, y3, y4) : 0);
		}
	}
}

class Main

{

static int distance(int a, int b, int c, int d)

{

int ans = 0;

if (a > b)

{

int temp = a;

a = b;

b = temp;

}

if (c > d)

{

int temp = c;

c = d;

d = temp;

}

if (b < c || a > d)

{

ans = 0;

}

else

{

int l = 0, r = 0;

l = Math.max(a, c);

r = Math.min(b, d);

ans = r - l;

}

return ans;

}

public static void main (String[] args)

{

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

int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();

int x3 = in.nextInt(), y3 = in.nextInt(), x4 = in.nextInt(), y4 = in.nextInt();

if (x1 != x2)

{

System.out.println(y1 < Math.max(y3, y4) && y1 > Math.min(y3, y4) ? distance(x1, x2, x3, x4) : 0);

}

else

{

System.out.println(x1 < Math.max(x3, x4) && x1 > Math.min(x3, x4) ? distance(y1, y2, y3, y4) : 0);

}

Решение

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

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

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

Обозначим искомую длину как $ans$, тогда $ans = min(x_{2}, x_{4})-max(x_{1}, x_{3})$.

Для ординат $ans = min(y_{2}, y_{4})-max(y_{1}, y_{3})$.

Ссылки

Условие задачи на e-olymp

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

e-olymp 8283. Музыка

13/09/2020 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

import java.util.Scanner;

class Main {
	public static void main (String[] args) {
		int counter = 1;
		Scanner in = new Scanner(System.in);
		int quantity = in.nextInt();
		int instrument = in.nextInt();
		if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
			System.out.print(0);
		} else if (quantity == instrument) {
			for (int num = 1; num % quantity != 0; num += 6) {
				if (num != 1 && num % quantity == 1){
					System.out.print(0);
					System.exit(0);
				} else {
					counter++;
				}
			}
			System.out.print(counter);
		} else {
			for (int num = 1; num % quantity != instrument; num += 6) {
				if (num != 1 && num % quantity == 1) {
					System.out.print(0);
					System.exit(0);
				} else {
					counter++;
				}
			}
			System.out.print(counter);
		}
	}
}

import java.util.Scanner;

class Main {

public static void main (String[] args) {

int counter = 1;

Scanner in = new Scanner(System.in);

int quantity = in.nextInt();

int instrument = in.nextInt();

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

System.out.print(0);

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1){

System.out.print(0);

System.exit(0);

} else {

counter++;

}

System.out.print(counter);

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

System.out.print(0);

System.exit(0);

} else {

counter++;

}

System.out.print(counter);

}

Решение

Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:

Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp