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 7612. Алекс и квадраты оригами

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

Задача

Алекс любит оригами — японское искусство складывания из бумаги. Большинство конструкций оригами начинаются с квадратного листа бумаги. Алекс собирается сделать подарок для своей матери. Подарочная конструкция требует три одинаковых квадратных листа бумаги, но у Алекса имеется только один прямоугольный лист. Он может из него вырезать квадраты, стороны которых должны быть параллельны сторонам листа. Помогите Алексу определить максимально возможный размер квадратов, который он способен вырезать.

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

В одной строке два целых числа [latex] h [/latex] и [latex] w [/latex] [latex] \left ( 1\leqslant h,w\leqslant 1000 \right ) [/latex] — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex] h \times w[/latex] так, чтобы их стороны были параллельны сторонам листа.
Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные	Выходные данные
30 11	10.0000
8 3	2.6667
210 297	105.0000
60 59	29.5000
250 100	83.3333

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

import static java.lang.Math.max;
import java.util.Scanner;
class Main
{
	public static void main (String[] args)
	{
		double ans = 0;
		Scanner scanner = new Scanner(System.in);
		double h = scanner.nextDouble();
		double w = scanner.nextDouble();
		//swapping value of two numbers without using temp variable
		if(w < h) {
			w = w + h;
			h = w - h;
			w = w - h;
		}
		ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );
		System.out.printf("%.4f", ans);
	}
}

import static java.lang.Math.max;

import java.util.Scanner;

class Main

{

public static void main (String[] args)

{

double ans = 0;

Scanner scanner = new Scanner(System.in);

double h = scanner.nextDouble();

double w = scanner.nextDouble();

//swapping value of two numbers without using temp variable

if(w < h) {

w = w + h;

h = w - h;

w = w - h;

}

ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );

System.out.printf("%.4f", ans);

}

import static java.lang.Math.max;
import java.util.Scanner;
class Main
{
	public static void main (String[] args)
	{
		double tmp = 0, ans = 0;
		Scanner scanner = new Scanner(System.in);
		double h = scanner.nextDouble();
		double w = scanner.nextDouble();
		if(w < h) {
			tmp = h;
			h = w;
			w = tmp;
		}
		if(w >= 3 * h) {
			ans = h;
		}
		else {
			 ans = Math.max(h/2, w/3);
		}
		System.out.printf("%.4f", ans);
	}
}

import static java.lang.Math.max;

import java.util.Scanner;

class Main

{

public static void main (String[] args)

{

double tmp = 0, ans = 0;

Scanner scanner = new Scanner(System.in);

double h = scanner.nextDouble();

double w = scanner.nextDouble();

if(w < h) {

tmp = h;

h = w;

w = tmp;

}

if(w >= 3 * h) {

ans = h;

}

else {

ans = Math.max(h/2, w/3);

}

System.out.printf("%.4f", ans);

}

Алгоритм решения`

Допустим, что [latex] w [/latex] всегда больше чем [latex] h [/latex] . Из условия следует, что варианта расположения данных квадратов два: . В первом случае ответом будет [latex] \max\left ( \frac{h}{2}, \frac{w}{3} \right ) [/latex]. Во втором же, ответом будет [latex] h [/latex] .

Детали реализации

В первой версии программы используется тернарный оператор: ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );
В обоих версиях программы имя метода max() становится видимым благодаря оператору статического импорта: import static java.lang.Math.max;. Также мы импортируем класс Scanner: import java.util.Scanner;
Для вывода ответа с точностью не меньше трех десятичных знаков используется форматирование чисел с плавающей точкой.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

e-olymp 8893. Каждое условие из двух

12/09/2020 by Олег Сторожев

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

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

Число $n$ кратное трем;
Число $n$ четное и двухзначное.

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

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

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

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

Тесты

№	Входные данные	Выходные данные
1	12	YES
2	27	NO
3	-12	YES
4	60	YES
5	10	NO
6	00000012	YES

Код

using namespace std;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;

public class Ideone{
	public static void main (String[] args) throws java.lang.Exception{
		int n;
		Scanner myObj = new Scanner(System.in);
		n = myObj.nextInt();
		if (Math.abs(n) >= 10 && Math.abs(n) < 100 && n % 6 == 0){
        		System.out.print("YES");
         }
         else {
               System.out.print("NO");
         }
	}
}

using namespace std;

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

public class Ideone{

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

int n;

Scanner myObj = new Scanner(System.in);

n = myObj.nextInt();

if (Math.abs(n) >= 10 && Math.abs(n) < 100 && n % 6 == 0){

System.out.print("YES");

}

else {

System.out.print("NO");

}

Решение

У нас дана целочисленная переменная $n$. Для решения данной задачи надо проверить выполняет ли переменная все условия чтобы выводилось YES.

Для начала надо проверить является ли переменная двухзначным числом (то есть в диапазоне от 10 до 99 включительно). С отрицательными знаками делаем то же самое (от -10 до -99 включительно)
Смотрим, является ли переменная кратной трем. Для этого остаток от деления переменной на три должен равняться нулю.
Смотрим, является ли переменная четной. Для этого остаток от деления переменной на два должен равняться нулю.

Если выполняются все условия, то выводим YES, в остальных случаях NO. Задача решена

Ссылки

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

e-olymp 9081. Автомобілі

10/09/2020 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$, $v_2$, $v_3$, $t_1$, $t_2$, $t_3$. Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

public class Main {

    public static void main(String[] args) {
        java.util.Scanner jin = new java.util.Scanner(System.in);
            int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
            int t1, t2, t3; // Час, який вони їхали
            int s1, s2, s3; // І відстань
            int max_; // Також, змінну, де буде зберігатися максимальна відстань
            v1 = jin.nextInt(); t1 = jin.nextInt(); // Прочитуємо швидкість і час для кожного водія
            v2 = jin.nextInt(); t2 = jin.nextInt();
            v3 = jin.nextInt(); t3 = jin.nextInt();
            s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
            s2 = v2 * t2;
            s3 = v3 * t3;
            max_ = Math.max(Math.max(s1, s2), s3); // Виявляємо максимальну відстань
            if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
                System.out.print("1 "); // Виводимо номер відповідного водія
            if ( s2 == max_ )
                System.out.print("2 ");
            if ( s3 == max_ )
                System.out.print(3);
            
        }
}

public class Main {

public static void main(String[] args) {

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

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

v1 = jin.nextInt(); t1 = jin.nextInt(); // Прочитуємо швидкість і час для кожного водія

v2 = jin.nextInt(); t2 = jin.nextInt();

v3 = jin.nextInt(); t3 = jin.nextInt();

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = Math.max(Math.max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

System.out.print("1 "); // Виводимо номер відповідного водія

if ( s2 == max_ )

System.out.print("2 ");

if ( s3 == max_ )

System.out.print(3);

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$. Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.

Посилання

e-olymp 1206. f91

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

Задача

МакКарти — известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию $f_{91}$, которая определена для всякого натурального числа $n$ следующим образом:

Если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;

Если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.

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

Натуральное число $n$, не большее $1000000$.

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

Значение $f_{91}\left(n\right)$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5	91
2	27	91
3	91	91
4	100	91
5	102	92
6	180	170

Код

class Main{
	public static long func(long n){
		if(n <= 100){
			return 91;
		}
		else {
			return n - 10;
		}
	}
	public static void main (String[] args){
		java.util.Scanner in = new java.util.Scanner(System.in);
		long num = in.nextInt();
		System.out.println(func(num));
	}
}

class Main{

public static long func(long n){

if(n <= 100){

return 91;

}

else {

return n - 10;

}

public static void main (String[] args){

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

long num = in.nextInt();

System.out.println(func(num));

}

Решение

Для решения задачи создадим функцию $f_{91}\left(n\right)$ которая в зависимости от значения $n$ будет выдавать нам разные значение, а имеено:
если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;
если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.
Так же, мы можем проследить законномерность того, что если $n\leqslant100$ функция $f_{91}\left(n\right)$ будет выдавть $91$, заметив это можно будет заменить сложную, но при этом красивую рекурсивную функцию на более простое и практичное решение и получить следущие соотношение:
$f_{91}\left(n\right) = \begin{cases} 91, & n\leqslant100;\\\ n-10, & n\geqslant101; \end{cases}$

Ссылки

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

e-olymp 219. Центральное отопление

28/03/2019 by Никита Пушкин

Задача

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 800333-90-06*. Для простоты Пин решил купить простые батареи. Согласно таблице 14.1.3 этого ГОСТа, каждая батарея обогревает определённый объём воздуха — ровно [latex]d[/latex] кубометров. Комната, которую собирается для своего друга обогреть Пин, имеет следующие размеры:

• высота [latex]a[/latex],

• ширина [latex]b[/latex],

• длина [latex]c[/latex].

Определите минимальное количество батарей, которое необходимо купить Пину. Учтите только, что если в домике у Кар Карыча температура будет ниже, чем по ГОСТу, Кар Карыч никогда не поправится.

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

Четыре целых числа [latex]a, b, c, d (a, b, c \leq 10^{5}, d \leq 2 \cdot 10^{9})[/latex].

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

Выведите минимальное количество батарей, которое необходимо купить Пину.

Тесты

#	Входные данные	Выходные данные
1	2 3 4 2	12
2	4 5 7 3	47
3	75 61 88 50	8052
4	986 764 390 54	5440529
5	1 1 1 2000000	1

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long  a, b, c, d, v;
		Scanner in = new Scanner (System.in);
		a=in.nextLong();
		b=in.nextLong();
		c=in.nextLong();
		d=in.nextLong();
		v = a * b * c;
		System.out.println(( v + d - 1 ) / d);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

long a, b, c, d, v;

Scanner in = new Scanner (System.in);

a=in.nextLong();

b=in.nextLong();

c=in.nextLong();

d=in.nextLong();

v = a * b * c;

System.out.println(( v + d - 1 ) / d);

}

Алгортм решения

Находим объём комнаты по заданным сторонам по формуле [latex]V=a \cdot b \cdot c[/latex].
Делим полученный объём на объём, обогреваемый одной батареей.
Округляем при необходимости полученный ответ вверх, чтобы найти минимальное количество батарей.

Округление

Если разделить объём [latex]V[/latex] на [latex]d[/latex] нацело, то в остатке у нас может получиться [latex]0, 1, 2, \ldots , d-1[/latex]. Добавив [latex]d-1[/latex] к объёму [latex]V[/latex] мы получим в делении нацело остатки [latex]d-1, d, d+1, \ldots , 2d-2[/latex]. Первое число [latex]d-1<d[/latex], поэтому при делении нацело оно даёт [latex]0[/latex]. Остальные числа больше либо равны [latex]d[/latex], но меньше [latex]2d[/latex], значит любое из них при делении нацело на [latex]d[/latex] даст [latex]1[/latex].

Условие задачи можно найти на e-olymp
Код решения — ideone

Ю1.19

24/02/2019 by Глеб Брошко

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

Найти координаты вершины параболы \[y = ax^{2}+bx+c\]

Алгоритм решения

Мы знаем координаты вершины параболы вычисляются по формулам:

1) \[x_{0} = — \frac{b}{2 \cdot a}\] 2) \[y_{0} = ax_{0}^{2}+bx_{0}+c\]

(Для простоты в программе [latex]x_{0}[/latex] и [latex]y_{0}[/latex] заменены на [latex]x[/latex] и [latex]y[/latex] соответственно).

Теперь учтем ситуации в проработке которых могут возникнуть сложности:
Если [latex]a=0[/latex], то график [latex]y(x)[/latex] не является параболой, о чем на должен проинформировать компилятор. Это все проблемы связанные с графиком.

Это все сложности которые могут повстречаться на на пути реализации данной программы, так ничего не мешает нам написать данную программу.

Тесты

№	[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]x[/latex]	[latex]y[/latex]	Комментарий
-1	-2	-3	1	-4	Пройден
0	2	2	—	—	Не пройден так график [latex]y(x)[/latex] не является параболой и программа оповещает об ошибке
1	0	4	0	4	Пройден
2	1	3	-0.25	2.875	Пройден

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double a, b, c, x, y;
		double h;
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		x = b/(2*a);    	// находим первую координату вершины параболы и нам остаётся только умножить результат на -1
 
		if( a != 0 ){			// "только если уравнение задает на графике параболу..."
			if(x!=0) x*=-1; 	// в типе double  0 -- иногда получает свойства числа со знаком, поэтому дабы при b == 0 мы не получили  x == -0 нам нужно умножить x на (-1) только если x != 0
		}
		else{					// если а == 0, то график y(x) не является параболой ==> выводим на экран "Error" и закрываем программу
			 System.out.println("Error");
			 sc.close();
		} 
 
	    	y = a*x*x + b*x + c;    // находим вторую координату вершины параболы
	    	System.out.println(x);
		System.out.println(y);
		sc.close();
 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double a, b, c, x, y;

double h;

Scanner sc = new Scanner(System.in);

a = sc.nextInt();

b = sc.nextInt();

c = sc.nextInt();

x = b/(2*a); // находим первую координату вершины параболы и нам остаётся только умножить результат на -1

if( a != 0 ){ // "только если уравнение задает на графике параболу..."

if(x!=0) x*=-1; // в типе double 0 -- иногда получает свойства числа со знаком, поэтому дабы при b == 0 мы не получили x == -0 нам нужно умножить x на (-1) только если x != 0

}

else{ // если а == 0, то график y(x) не является параболой ==> выводим на экран "Error" и закрываем программу

System.out.println("Error");

sc.close();

}

y = a*x*x + b*x + c; // находим вторую координату вершины параболы

System.out.println(x);

System.out.println(y);

sc.close();

}

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

e-olymp 1868. Функция

27/12/2018 by Иван Василевский

Условие задачи
Вычислите функцию:
$$f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}$$
Входные данные
Одно натуральное число $n$ $(1 \leq n \leq 10^{12})$
Выходные данные
Значение $f(n)$ , взятое по модулю $2^{32}$.
Тесты

Входные данные	Выходные данные
10	7
123	229966
1	1
100	136345
51	5092

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.HashMap;
import java.lang.Math;

class Main
{

    private static long mod = 1L << 32;
    public static Map<Long, Long> mp = new HashMap<Long, Long>();

    public static long f(long n) {
        if (n <= 2) {
            return 1;
        }
        if (mp.containsKey(n)) {
            return mp.get(n);
        }
        if (n % 2 == 1) {
            long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;
            mp.put(n, d);
            return mp.get(n);
        }
        long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;
        mp.put(n, o);
        return mp.get(n);
    }


    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        long n;
        n = Long.parseLong(params1[0]);
        System.out.print(f(n));
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Map;

import java.util.HashMap;

import java.lang.Math;

class Main

{

private static long mod = 1L << 32;

public static Map<Long, Long> mp = new HashMap<Long, Long>();

public static long f(long n) {

if (n <= 2) {

return 1;

}

if (mp.containsKey(n)) {

return mp.get(n);

}

if (n % 2 == 1) {

long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;

mp.put(n, d);

return mp.get(n);

}

long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;

mp.put(n, o);

return mp.get(n);

}

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

long n;

n = Long.parseLong(params1[0]);

System.out.print(f(n));

}

Решение задачи
Решение данной задачи стоит начать с написания рекурсивной функции для вычисления функций по условию задачи. Так как рекурсия будет довольно таки сложной и много раз повторяются одни и те же результаты при вызове функции, следовательно, программа будет долгое время обрабатывать нашу задачу. То есть, к примеру, на 5 и 20 итерации, возвращаемые значения функции могут совпасть, что без оптимизации будет просчитываться еще раз, а с оптимизацией функция уже знает, чему равно значение с данными аргументами.Далее, по условию, мы пишем наконец нашу функцию:

Если число, которое ввел пользователь, меньше либо равно двум, то наша функция возвращает значение один.
Если есть значение с таким же ключом, то оно возвращает значение.
Если число, которое ввел пользователь, дает остаток от деления один, то наша функция возвращает значение $f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor)$.
Во всех остальных случаях наша функция возвращает значение $f(n-1)+f(n-3)$.

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

e-olymp 143. Точка и треугольник

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

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

№	Входные данные	Выходные данные
1	2 6 -9 3 8 1 5 11	1
2	-13 10 -12 5 99 80 17 13	0
3	98 -50 -87 7 5 3 23 17	0
4	5 15 7 12 5 3 2 54	1
5	2 2 3 1 1 3 9 11	1

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

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);
		double x0 = scan.nextDouble();
		double y0 = scan.nextDouble();
		double x1 = scan.nextDouble();
		double y1 = scan.nextDouble();
		double x2 = scan.nextDouble();
		double y2 = scan.nextDouble();
		double x3 = scan.nextDouble();
		double y3 = scan.nextDouble();
		double z1,z2,z3;
		z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);
		z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);
		z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);
		if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) System.out.println("1");
		else System.out.println("0");
	}
}

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);

double x0 = scan.nextDouble();

double y0 = scan.nextDouble();

double x1 = scan.nextDouble();

double y1 = scan.nextDouble();

double x2 = scan.nextDouble();

double y2 = scan.nextDouble();

double x3 = scan.nextDouble();

double y3 = scan.nextDouble();

double z1,z2,z3;

z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);

z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);

z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);

if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) System.out.println("1");

else System.out.println("0");

}

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

Ссылки

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

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 1610. Зайцы в клетках

26/12/2018 by Кирилл Бондаренко

Зайцы в клетках

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

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

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

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

В одной строке заданы два натуральных числа $n$ и $m$ $(1 ≤ n, m ≤ 10^{9})$.

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
3 50	17
5 5	1
1070 589	1
20 150	8

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		double k;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		k = m / n;
		if (k >= 1){
			int k1 = (m + n - 1) / n;
			System.out.print(k1);
		}
		else System.out.print(1);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main

{

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

{

int n, m;

double k;

Scanner in = new Scanner(System.in);

n = in.nextInt();

m = in.nextInt();

k = m / n;

if (k >= 1){

int k1 = (m + n - 1) / n;

System.out.print(k1);

}

else System.out.print(1);

}

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

Пусть $n$ — количество клеток, и $m$ — количество зайцев.
Найдем отношение $\frac{m}{n}$. Если это отношение больше либо равно единице то $m\geq n$ и мы имеем ответ. $\frac{m+n-1}{n}$ — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе $m\leq n$ и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

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

Задача

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

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

Тесты

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

Алгоритм решения`

Детали реализации

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

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

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

Тесты

Код

Решение

Ссылки

Завдання

Вхідні дані

Вихідні дані

Тести

Код програми

Пояснення

Посилання

Задача

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

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

Тесты

Код

Решение

Ссылки

Задача

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

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

Тесты

Алгортм решения

Округление

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

Алгоритм решения

Тесты

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

10

7

123

229966

1

1

100

136345

51

5092

Точка и треугольник

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

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

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

Решение

Ссылки

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

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

Тесты

С ветвлением

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

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

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

Ссылки

Зайцы в клетках

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

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

Тесты

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

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