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 903. Первая или последняя?

06/07/2016 by Эдуард Брагар

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

Задано трехзначное число. Какая цифра в нем больше: первая или последняя?

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

Одно трехзначное число.

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

Вывести большую из указанных цифр. В случае их равенства вывести знак “=” (без кавычек).

	Входные данные	Результат
1	328	8
2	956	9
3	384	4
4	672	6
5	588	8
6	733	7
7	797	=
8	555	=

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

class Ideone {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		int a=Math.abs(in.nextInt());
		int b = a%10;
		a /= 100;
		System.out.print((a == b ? "=" : (a > b ? a: b)));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

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

Scanner in = new Scanner(System.in);

int a=Math.abs(in.nextInt());

int b = a%10;

a /= 100;

System.out.print((a == b ? "=" : (a > b ? a: b)));

}

e-olymp.com
ideone.com

Пояснение:

Для того чтобы определить первую цифру[latex](a)[/latex]трехзначного числа [latex]n[/latex] необходимо найти целую часть от деления этого числа на сто, воспользовавшись формулой [latex] a=\frac{n}{100}.[/latex] Чтобы определить вторую цифру [latex](b)[/latex] необходимо найти остаток от деления числа на десять, воспользовавшись формулой [latex]b=n%10[/latex] . Затем необходимо проверить равны ли эти цифры, если нет-найти большую.

e-olymp 911. Квадратное уравнение

06/07/2016 by Игорь Варламов

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

Составить программу для решения квадратного уравнения [latex]ax^2 + bx + c = 0,[/latex] [latex](a\neq0).[/latex]

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

В одной строке задано три целых числа – коэффициенты квадратного уравнения соответственно a,b и c. Значения коэффициентов не превышают по модулю 100.

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

В одной строке вывести в случае отсутствия корней сообщение “No roots” (без кавычек), в случае, если решение содержит один корень вывести сначала сообщение “One root:” (без кавычек), а далее через пробел сам корень, в случае наличия двух корней вывести сначала сообщение “Two roots:” (без кавычек), а далее через пробел сначала меньший, а потом больший корень. Гарантируется, что в случае наличия решений все корни целочисленные.

Тесты

Входные данные	Выходные данные
1 -5 6	Two roots: 2 3
1 10 25	One root: -5
1 2 3	No roots
2 6 7	No roots
1 -2 1	One root: 1
1 6 9	One root: -3
3 -7 10	No roots

Код:

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

class Ideone{
	public static void main (String[] args) throws java.lang.Exception{
		int a,b,c,d;
		Scanner x = new Scanner(System.in);
		a = x.nextInt();
		b = x.nextInt();
		c = x.nextInt();
		d = (b*b)-(4*a*c);
		if(d > 0){
			double x1,x2;
			x1 = (-b+Math.sqrt(d))/(2*a);
			x2 = (-b-Math.sqrt(d))/(2*a);
			System.out.print("Two roots: "+((x1 > x2)?x2:x1)+" "+((x1>x2)?x1:x2));
		} else if (d == 0){
			System.out.print("One root: " +(-b/(2*a)));
		} else {
			System.out.print("No roots");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

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

int a,b,c,d;

Scanner x = new Scanner(System.in);

a = x.nextInt();

b = x.nextInt();

c = x.nextInt();

d = (b*b)-(4*a*c);

if(d > 0){

double x1,x2;

x1 = (-b+Math.sqrt(d))/(2*a);

x2 = (-b-Math.sqrt(d))/(2*a);

System.out.print("Two roots: "+((x1 > x2)?x2:x1)+" "+((x1>x2)?x1:x2));

} else if (d == 0){

System.out.print("One root: " +(-b/(2*a)));

} else {

System.out.print("No roots");

}

Решение:
Для того чтобы его решить надо сначала найти дискриминант: [latex]d=b^2-4ac[/latex], а потом подставить его в следующие формулы для нахождения действительных корней квадратного уравнения: [latex]x_1=\frac{-b+\sqrt d}{2a}[/latex] и [latex]x_2=\frac{-b-\sqrt d}{2a}[/latex]. Однако для квадратного уравнения существует 3 варианта ответов зависящие от дискриминанта. Все 3 варианта расписаны в if-блоках, где сначала проверяется дискриминант и от его значения уже определяется сколько корней у нас будет. После этого выводятся корни, гарантированно целочисленные, или надпись “No roots”, если их нет.

Решение на e-olymp
Решение на ideone

e-olymp 905. Какой треугольник?

01/07/2016 by Ирина Литвиненко

Задача взята с сайта www.e-olymp.com

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

Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон.

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

В единственной строке задано [latex]3[/latex] целых числа – длины сторон треугольника. Длины сторон не превышают [latex]100[/latex].

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

В единственной строке вывести [latex]1[/latex], если треугольник равносторонний, [latex]2[/latex] если равнобедренный и [latex]3[/latex] если разносторонний.

Код

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

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

		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		int c = scanner.nextInt();
		int result;
		
		/*if (a == b && b == c && a == c) {
			System.out.print(1);
		}
		else if (a == b || b == c || a == c) {
			System.out.print(2);
		}
		else {
			System.out.print(3);
		}*/
		
		result = (a == b && b == c && a == c) ? 1 : (a == b || b == c || a == c) ? 2 : 3;
		
		System.out.print(result);

	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

Scanner scanner = new Scanner(System.in);

int a = scanner.nextInt();

int b = scanner.nextInt();

int c = scanner.nextInt();

int result;

/*if (a == b && b == c && a == c) {

System.out.print(1);

}

else if (a == b || b == c || a == c) {

System.out.print(2);

}

else {

System.out.print(3);

}*/

result = (a == b && b == c && a == c) ? 1 : (a == b || b == c || a == c) ? 2 : 3;

System.out.print(result);

}

www.ideone.com

№	Входные данные	Выходные данные
1	3 3 3	1
2	3 4 3	2
3	3 4 5	3

Решение

Для решения задачи нам нужно уметь определять виды треугольников. Нам даны равносторонний, равнобедренный и разносторонний треугольники. У равностороннего треугольника все стороны равны, у равнобедренного равны лишь два бедра, а у разностороннего – стороны не равны.

Для начала задаем три переменные [latex]a[/latex], [latex]b[/latex] и [latex]c[/latex], которые равны сторонам треугольника. Вводим их произвольно. Для того, чтобы определить какой это треугольник мы задаем параметры :

если [latex]a=b=c[/latex], то есть все стороны равны, то у нас равносторонний треугольник;
если [latex]a=b[/latex] или [latex]b=c[/latex], или [latex]a=c[/latex], то есть две из трех сторон треугольника равны, то у нас равнобедренный треугольник;
если [latex]a\neq b\neq c[/latex], стороны не равны, то у нас разносторонний треугольник.

e-olymp 4. Two circles

01/07/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Определить количество точек пересечения двух окружностей.

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

Шесть чисел: x1, y1, r1, x2, y2, r2, где x1, y1, x2, y2 — координаты центров окружностей, а r1, r2 — их радиусы. Все числа — действительные, не превышают 10⁹, заданы не более чем с тремя знаками после запятой.

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

Количество точек пересечения. Если точек пересечения бесконечно много, то вывести -1.

Тесты:

X₁	Y₁	R₁	X₂	Y₂	R₂	N
0	0	5	5	0	1	2
0	0	5	0	0	6	1
0	1	6	0	3	6	2

Код на Java:

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 x1 = scan.nextDouble(), y1 = scan.nextDouble(), r1 = scan.nextDouble();
		double x2 = scan.nextDouble(), y2 = scan.nextDouble(), r2 = scan.nextDouble();
		double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
		double rads = r1 + r2;
		if (range == 0 && r1 == r2) {
			System.out.print(-1);
		}
		else if (range == rads || range + r1 == r2 || range + r2 == r1) {
			System.out.print(1);
		}
		else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){
			System.out.print(0);
		}
		else {
			System.out.print(2);
		}
	}
}

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 x1 = scan.nextDouble(), y1 = scan.nextDouble(), r1 = scan.nextDouble();

double x2 = scan.nextDouble(), y2 = scan.nextDouble(), r2 = scan.nextDouble();

double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

double rads = r1 + r2;

if (range == 0 && r1 == r2) {

System.out.print(-1);

}

else if (range == rads || range + r1 == r2 || range + r2 == r1) {

System.out.print(1);

}

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){

System.out.print(0);

}

else {

System.out.print(2);

}

Ход решения:

Высчитываем расстояние между центрами окружностей по формуле: $Range$ = $\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2}$ . Вычисление в одну строку:

double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

1	double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

Далее рассчитываем суму радиусов окружностей.
Если центры совпадают (Range = 0) и длины радиусов равны, значит, совпадают и окружности:

if (range == 0 && r1 == r2) {
	System.out.print(-1);
}

if (range == 0 && r1 == r2) {

System.out.print(-1);

}

Если расстояние между окружностями равно сумме радиусов, окружности имеют одну общую точку, касаясь друг друга снаружи. Также одна из окружностей может лежать внутри другой и касаться ее изнутри:

else if (range == rads || range + r1 == r2 || range + r2 == r1) {
	System.out.print(1);
}

else if (range == rads || range + r1 == r2 || range + r2 == r1) {

System.out.print(1);

}

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

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){
	System.out.print(0);
}

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){

System.out.print(0);

}

В остальных случаях окружности пересекаются и имеют две общие точки:

else {
	System.out.print(2);
}

else {

System.out.print(2);

}

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

ML 24 Радиус вписанной/описанной в треугольник окружности

01/07/2016 by Сережа Туромша

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

Треугольник задан длинами сторон. Найти радиус вписанной $r$ и описанной $R$ окружностей.

Тесты :

a	b	c	$r$	$R$
3	4	5	1	90
2	2	6	Не существует	Не существует
3.1	4.1	5.1	1.033199	102.970967

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

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner x = new Scanner(System.in);
		double a,b,c ;
		a = x.nextDouble();
		b = x.nextDouble();
		c = x.nextDouble() ;
		if (a + b >= c && b + c >= a && a + c >= b)
		{
			double p = (a + b + c)/2; 	
			double S = Math.sqrt(p * (p - a) * (p - b) * (p - c));
			double r = S/p;
			double R = (a*b*c)/4*S;
			System.out.format("Радиус вписанной окружности равен = %f\n",r);
			System.out.format("Радиус описанной окружности равен = %f ",R);
		}
		else
		{
			System.out.print("Не существует");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone

{

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

{

Scanner x = new Scanner(System.in);

double a,b,c ;

a = x.nextDouble();

b = x.nextDouble();

c = x.nextDouble() ;

if (a + b >= c && b + c >= a && a + c >= b)

{

double p = (a + b + c)/2;

double S = Math.sqrt(p * (p - a) * (p - b) * (p - c));

double r = S/p;

double R = (a*b*c)/4*S;

System.out.format("Радиус вписанной окружности равен = %f\n",r);

System.out.format("Радиус описанной окружности равен = %f ",R);

}

else

{

System.out.print("Не существует");

}

Алгоритм :

Проверяем, или образуют данные стороны треугольник. В треугольнике сумма длин любых двух сторон больше длины третьей (или равна её длине, если треугольник вырожденный)

if (a + b >= c && b + c >= a && a + c >= b)

15	if (a + b >= c && b + c >= a && a + c >= b)

Если условие не выполняется ,сообщаем об этом пользователю :

System.out.print("Не существует");

26	System.out.print("Не существует");

Если треугольник существует, проводим следующие вычисления (Порядок важен). :

Вычисляем полупериметр $p$ треугольника : $p$ = $\frac{a + b + c}{2}$
Находим площадь $S$ по формуле Герона : $S$ = $\sqrt{p(p-a)(p-b)(p-c)}$
Вычисляем радиус $r$ вписанной окружности по формуле : $r$ = $\frac{S}{p}$
Вычисляем радиус описанной окружности $R$ по формуле : $R$ = $\frac{abc}{4S}$

Работающая версия программы на Ideone.con :

Ideone.com

ML 24

01/07/2016 by Дарья Пиндус

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

Треугольник задан длинами сторон. Найти радиус вписанной $r$ и описанной $R$ окружностей.

Тесты :

$a$	$b$	$c$	$r$	$R$
3	4	5	1	2.5
7.5	10	13	2.450117	6.5236096
1	3	4	0	inf
1	1	3	Не существует!	Не существует!

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

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

class Ideone
{
	public static void main (String[] args)
	{
		float a, b, c;
		Scanner scanner = new Scanner(System.in);
		System.out.println("Enter values: ");
		a = scanner.nextFloat();
		b = scanner.nextFloat();
		c = scanner.nextFloat();
		if (a + b >= c || b + c >= a || a + c >= b) {
			float p = (a + b + c) / 2;
			float S = (float) Math.sqrt(p * (p - a) * (p - b) * (p - c));
			float R = (a * b * c) / (4 * S);
			float r = S/p;
			System.out.println("Radius of incircle of triangle = " + r + "\nRadius of excircle of triangle = " + R);     
		} else {
			System.out.println("Wrong input data. Triangle doesn't exist");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

float a, b, c;

Scanner scanner = new Scanner(System.in);

System.out.println("Enter values: ");

a = scanner.nextFloat();

b = scanner.nextFloat();

c = scanner.nextFloat();

if (a + b >= c || b + c >= a || a + c >= b) {

float p = (a + b + c) / 2;

float S = (float) Math.sqrt(p * (p - a) * (p - b) * (p - c));

float R = (a * b * c) / (4 * S);

float r = S/p;

System.out.println("Radius of incircle of triangle = " + r + "\nRadius of excircle of triangle = " + R);

} else {

System.out.println("Wrong input data. Triangle doesn't exist");

}

Алгоритм :

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

if (a + b < c || b + c < a || a + c < b) {
            System.out.println("Wrong input data. Triangle doesn't exist");
        }

if (a + b < c || b + c < a || a + c < b) {

System.out.println("Wrong input data. Triangle doesn't exist");

}

Если треугольник существует, проводим следующие вычисления (порядок сохранен) :

Вычисляем полупериметр $p$ треугольника: $p$ = $\frac{a + b + c}{2}$
Находим площадь $S$ по формуле Герона: $S$ = $\sqrt{p(p-a)(p-b)(p-c)}$
Вычисляем радиус $r$ вписанной окружности по формуле: $r$ = $\frac{S}{p}$
Вычисляем радиус $R$ описанной окружности по формуле: $R$ = $\frac{abc}{4S}$

Работающая версия программы на Ideone.com :
Ideone.com

e-olymp 126. Номер квартиры

30/06/2016 by Артур Тарасов

Задача. Многоквартирный дом имеет [latex]N[/latex] квартир, [latex]P[/latex] подъездов и [latex]Q[/latex] этажей, причем на каждом этаже каждого подъезда имеется одинаковое количество квартир. Определить в каком подъезде и на каком этаже находится квартира с заданным номером [latex]K[/latex].

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

В единственной строке файла записаны значения [latex]N, P, Q, K. 1 \leq K \leq N \leq 1000, P \times Q \leq N.[/latex]

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

В единственную строку файла нужно вывести номер подъезда и этаж, на котором находится квартира с номером [latex]K.[/latex]

Задача взята с сайта e – olymp.

Тесты

Входные данные	Выходные данные
250 5 5 1	1 1
30 2 5 27	2 4
300 3 10 111	2 2
80 5 4 77	5 4
98 7 2 39	3 2
90 3 15 90	3 15

Перед нами была поставлена задача определить в доме с заданным количеством квартир, подъездов и этажей положение конкретной квартиры, а именно указать номер подъезда и этаж. Для дальнейшего хода решения определим две целочисленные переменные – flatEntrance (количество квартир в одном подъезде) и flatFloor (количество квартир на одном этаже). Найдем номер подъезда получив целую часть от деления номера квартиры на количество квартир в одном подъезде. Далее выполняем проверку остатка от деления, если он отличен от нуля, то это указывает на то, что квартира находится уже в следующем подъезде. В таком случае инкрементируем переменную entrance.

Для нахождения номера этажа поступим аналогично. Однако следует проверить не делится ли номер квартиры на количество квартир в одном подъезде нацело, если да – она располагается на последнем этаже. Если этого не сделать, то в последующей формуле получим [latex]0[/latex]. В общем случае номер этажа находим поделив остаток от деления номера квартиры на количество квартир в подъезде на количество квартир на этаже (учитываем, что каждый новый подъезд предполагает продолжение нумерации с первого этажа). И снова выполняем проверку остатка от деления. При надобности инкрементируем переменную floor.

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int N, P, Q, K, flatEntrance, flatFloor, entrance, floor;
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		P = sc.nextInt();
		Q = sc.nextInt();
		K = sc.nextInt();
		flatEntrance = N/P;
    	flatFloor = N/P/Q;
		entrance = K/flatEntrance; 
		if (K%flatEntrance != 0){
			entrance++;
		}
		if (K%flatEntrance == 0){
		    floor = Q;
		}
		else {
		    floor = (K%flatEntrance)/flatFloor; 
		    if (K%flatFloor != 0){
		  	    floor++;
		    }
		}
		System.out.format("%d %d", entrance, floor);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int N, P, Q, K, flatEntrance, flatFloor, entrance, floor;

Scanner sc = new Scanner(System.in);

N = sc.nextInt();

P = sc.nextInt();

Q = sc.nextInt();

K = sc.nextInt();

flatEntrance = N/P;

flatFloor = N/P/Q;

entrance = K/flatEntrance;

if (K%flatEntrance != 0){

entrance++;

}

if (K%flatEntrance == 0){

floor = Q;

}

else {

floor = (K%flatEntrance)/flatFloor;

if (K%flatFloor != 0){

floor++;

}

System.out.format("%d %d", entrance, floor);

}

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

А58а

30/06/2016 by Иоанна Васильева

Задача. Дано действительное число $a$ . Для функции $f\left(x \right)$ , график которой изображен, вычислить $f\left(a \right)$ .

58a

Для решения данной задачи требуется лишь проверка знака числа $a$ . Если $a> 0$ , то $f\left(a \right)$ вычисляется как $-a^{2}$ , а если $a< 0$ , то $f\left(a \right)$ равна $-a$ . При $a=0$ , $f\left(a \right)=0$ .

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

class Ideone{
	public static void main (String[] args){
		Scanner x = new Scanner(System.in);
		int a = x.nextInt();
		int y;
		if(a>0)   y = -a*a;
		else    y = -a;
		System.out.print(y);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

public static void main (String[] args){

Scanner x = new Scanner(System.in);

int a = x.nextInt();

int y;

if(a>0) y = -a*a;

else y = -a;

System.out.print(y);

}

Код на Ideone.

Тест

Входные данные	Выходные данные
-7	7
7	-49
0	0

acm.timus.ru №2002. Тестовое задание

22/12/2015 by Максим Швандт

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время:	0.5 секунды
Память	64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…

Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!

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

«register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
«login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
«logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».

Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!

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

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq n\leq 100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные

Результат

6register vasya 12345

logout vasya

success: new user addedfail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Код

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.TreeMap;
import java.lang.NumberFormatException;

public class Timus2002App
{

   //структура, описывающая атрибуты учетной записи
   public class AccountInfo
   {
      public String password;
      public boolean loggedIn;

      public AccountInfo(String argPassword, boolean argLoggedIn)
      {
         password = argPassword;
         loggedIn = argLoggedIn;
      }
   }

   
   //база данных учетной записи
   public class AccountDatabase
   {
      public static final int OK = 0;
      public static final int NOT_REGISTERED = 1;
      public static final int WRONG_PASSWORD = 2;
      public static final int ALREADY_LOGGED_IN = 3;
      public static final int ALREADY_LOGGED_OUT = 4;

      private TreeMap<String, AccountInfo> map;

      //конструктор
      public AccountDatabase()
      {
         map = new TreeMap<String, AccountInfo>();
      }

      //регистрация новой учетной записи
      public boolean register(String name, String password)
      {
         AccountInfo info = map.get(name);

         if (info != null)
         {
            return false;
         }

         map.put(name, new AccountInfo(password, false));

         return true;
      }

      //вход в систему
      public int login(String name, String password)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if (info != null)
         {
            if (!info.password.equals(password))
            {
               result = WRONG_PASSWORD;
            }
            else if (info.loggedIn)
            {
               result = ALREADY_LOGGED_IN;
            }
            else
            {
               map.put(name, new AccountInfo(info.password, true));
               result = OK;
            }
         }

         return result;
      }

      //выход из системы
      public int logout(String name)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if ( info != null )
         {
            if ( info.loggedIn )
            {
               map.put(name, new AccountInfo(info.password, false));
               result = OK;
            }
            else
            {
               result = ALREADY_LOGGED_OUT;
            }
         }

         return result;
      }

   }

   public static void main(String[] args)
   {
      int loginCount = 0;
      String line = null;
      
      Scanner in = new Scanner(System.in);
      //System.out.println("please enter number of logins: ");
      line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
      try
      {
         loginCount = Integer.parseInt(line.trim());
      }
      catch( NumberFormatException e )
      {
      }
      
      if ( loginCount < 1 || loginCount > 100 )
      {
         System.out.println("**** ERROR: wrong number of logins ****");
         in.close();
         return;
      }
      
      Timus2002App mainObj = new Timus2002App();
      AccountDatabase accounts = mainObj.new AccountDatabase();
      
      for( int i = 0; i < loginCount; i++ )
      {
         //System.out.println("please enter command:");
         
         line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
         if ( line == null || line.isEmpty() )
         {
            System.out.println("**** ERROR: empty input, abort processing ****");
            break;
         }
         
         //превращение введенной строки текста в вектор лексем
         StringTokenizer st = new StringTokenizer(line, " ");
         Vector<String> tokens = new Vector<String>();
         while (st.hasMoreTokens())
         {
            tokens.add( st.nextToken() );
         }

         //превращение вектора лексем в команду с аргументами
         String command   = ( tokens.size() > 0 ) ? tokens.get(0) : null;
         String name      = ( tokens.size() > 1 ) ? tokens.get(1) : null;
         String password  = ( tokens.size() > 2 ) ? tokens.get(2) : null;
         String message = null;
        
        //выполнение команд
         if ( command.equals("register"))
         {
            if ( name != null || password != null )
            {
               if ( accounts.register(name, password) )
               {
                  message = "success: new user added";
               }
               else
               {
                  message = "fail: user already exists";
               }
            }
            else
            {
               message = "fail: missing user name or password";
            }
         }
         else if ( command.equals("login"))
         {
            if ( name != null || password != null )
            {
               switch( accounts.login(name, password) )
               {
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  case AccountDatabase.WRONG_PASSWORD:
                     message = "fail: incorrect password";
                  break;
                  case AccountDatabase.ALREADY_LOGGED_IN:
                     message = "fail: already logged in";
                  break;
                  default:
                     message = "success: user logged in";
                  break;
              }
           }
           else
           {
              message = "fail: missing user name or password";
           }
         }
         else if ( command.equals("logout"))
         {
            if ( name != null )
            {
               switch( accounts.logout(name) )
               {
                  case AccountDatabase.ALREADY_LOGGED_OUT:
                     message = "fail: already logged out";
                  break;
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  default:
                     message = "success: user logged out";
                  break;
               }
            }
            else
            {
               message = "fail: missing user name";
            }
         }
         
         if ( message != null )
         {
            System.out.println(message);
         }
      }
      in.close();
   } 
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

import java.util.Scanner;

import java.util.StringTokenizer;

import java.util.Vector;

import java.util.TreeMap;

import java.lang.NumberFormatException;

public class Timus2002App

{

//структура, описывающая атрибуты учетной записи

public class AccountInfo

{

public String password;

public boolean loggedIn;

public AccountInfo(String argPassword, boolean argLoggedIn)

{

password = argPassword;

loggedIn = argLoggedIn;

}

//база данных учетной записи

public class AccountDatabase

{

public static final int OK = 0;

public static final int NOT_REGISTERED = 1;

public static final int WRONG_PASSWORD = 2;

public static final int ALREADY_LOGGED_IN = 3;

public static final int ALREADY_LOGGED_OUT = 4;

private TreeMap<String, AccountInfo> map;

//конструктор

public AccountDatabase()

{

map = new TreeMap<String, AccountInfo>();

}

//регистрация новой учетной записи

public boolean register(String name, String password)

{

AccountInfo info = map.get(name);

if (info != null)

{

return false;

}

map.put(name, new AccountInfo(password, false));

return true;

}

//вход в систему

public int login(String name, String password)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if (info != null)

{

if (!info.password.equals(password))

{

result = WRONG_PASSWORD;

}

else if (info.loggedIn)

{

result = ALREADY_LOGGED_IN;

}

else

{

map.put(name, new AccountInfo(info.password, true));

result = OK;

}

return result;

}

//выход из системы

public int logout(String name)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if ( info != null )

{

if ( info.loggedIn )

{

map.put(name, new AccountInfo(info.password, false));

result = OK;

}

else

{

result = ALREADY_LOGGED_OUT;

}

return result;

}

public static void main(String[] args)

{

int loginCount = 0;

String line = null;

Scanner in = new Scanner(System.in);

//System.out.println("please enter number of logins: ");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

try

{

loginCount = Integer.parseInt(line.trim());

}

catch( NumberFormatException e )

{

}

if ( loginCount < 1 || loginCount > 100 )

{

System.out.println("**** ERROR: wrong number of logins ****");

in.close();

return;

}

Timus2002App mainObj = new Timus2002App();

AccountDatabase accounts = mainObj.new AccountDatabase();

for( int i = 0; i < loginCount; i++ )

{

//System.out.println("please enter command:");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

if ( line == null || line.isEmpty() )

{

System.out.println("**** ERROR: empty input, abort processing ****");

break;

}

//превращение введенной строки текста в вектор лексем

StringTokenizer st = new StringTokenizer(line, " ");

Vector<String> tokens = new Vector<String>();

while (st.hasMoreTokens())

{

tokens.add( st.nextToken() );

}

//превращение вектора лексем в команду с аргументами

String command = ( tokens.size() > 0 ) ? tokens.get(0) : null;

String name = ( tokens.size() > 1 ) ? tokens.get(1) : null;

String password = ( tokens.size() > 2 ) ? tokens.get(2) : null;

String message = null;

//выполнение команд

if ( command.equals("register"))

{

if ( name != null || password != null )

{

if ( accounts.register(name, password) )

{

message = "success: new user added";

}

else

{

message = "fail: user already exists";

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("login"))

{

if ( name != null || password != null )

{

switch( accounts.login(name, password) )

{

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

case AccountDatabase.WRONG_PASSWORD:

message = "fail: incorrect password";

break;

case AccountDatabase.ALREADY_LOGGED_IN:

message = "fail: already logged in";

break;

default:

message = "success: user logged in";

break;

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("logout"))

{

if ( name != null )

{

switch( accounts.logout(name) )

{

case AccountDatabase.ALREADY_LOGGED_OUT:

message = "fail: already logged out";

break;

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

default:

message = "success: user logged out";

break;

}

else

{

message = "fail: missing user name";

}

if ( message != null )

{

System.out.println(message);

}

in.close();

}

Данная программа представляет собой типичный пример использования таблицы символов, согласно терминологии Coursera. Для доступа к учетным записям используется интерфейс Map, а для реализации самой базы данных учетных записей — объект типа TreeMap. Учетная запись пользователей реализована в виде одного элемента типа Map.entry, где имя пользователя — это ключ, а атрибуты учетной записи — пароль и флаг подключен/отключен — реализованы в виде отдельной структуры AccountInfo, которая является значением этого ключа.

Время работы	Выделено памяти
0.124	1 928 КБ

Ссылка на Ideone: https://ideone.com/3Y2W4z

Binary Heap (двоичная куча)

22/12/2015 by marchelaphil

В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности.

Двоичная куча

Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия:

Значение в любой вершине не меньше чем значение в потомках
Расстояние до корня отличается не более чем на один уровень
Заполняется слева на право

Зафиксируем операции, которые будем проводить над кучей:

Достать максимальный элемент из кучи, не удаляя его
Добавить элемент в кучу
Создать кучу
Отсортировать массив путём превращения его в кучу, а кучи — в отсортированный массив
Узнать размер кучи
Удалить максимальный элемент из кучи

Описание методов

1. Восстановление свойства кучи

Каждый элемент помещается в конец кучи, потом становится на своё место, соответственно свойств кучи.

Сложность: [latex]O(\log(n))[/latex]

2. Возврат максимального элемента

Возвратить содержимое самой верхней вершины.

Сложность: [latex]O(1)[/latex]

3. Удаление максимального элемента

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

Сложность: [latex]O(\log(n))[/latex]

4. Пирамидальная сортировка

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

Сложность: [latex]O(n\log(n))[/latex]

О реализации

Реализуется структура данных с абстрактным типом данных. Для хранения вершин будем использовать ArrayList. Для каждой вершины под номером [latex]i[/latex] её левый сын хранится в [latex]2*i+1[/latex] вершине, а правый — в [latex]2*i+2[/latex] вершине.

Класс содержит следующие методы:

Heap() — конструктор
shiftUp() — восходящее восстановление свойства кучи
shiftDown() — нисходящее восстановление свойства кучи
insert() — добавление элемента в кучу
delete() — удаление первой вершины
size() — размер кучи
isEmpty() — проверка на пустоту
toString() — преобразование в строку
max() — максимальный элемент
print() — вывод кучи на экран

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Heap <T extends Comparable<T> > {
    //arraylist is much better than an array. There is no need to carry about a capacity.
    private ArrayList<T> items;
 
    //construct
    public Heap() {
        items = new ArrayList<T> ();   
    }
 
    //using shiftUp for insert. 
    private void shiftUp () {
        int k = items.size() - 1;
        while (k > 0){
            int curr = (k-1)/2;
            T Item = items.get(k);
            T Parent = items.get(curr);
            if (Item.compareTo(Parent) > 0){
                items.set(k, Parent);
                items.set(curr, Item);
                k = curr;
            }
            else break;
        }
    }
 
    //using shiftDown fo delete
    private void shiftDown() {
        int curr = 0; 
        int leftChild = 2*curr+1;
        while (leftChild < items.size()) {
            int max = leftChild;
            int rightChild = leftChild + 1;
            if (rightChild < items.size()) {
                if (items.get(rightChild).compareTo(items.get(1)) > 0) {
                    ++max;
                }
            }
            if (items.get(curr).compareTo(items.get(max)) < 0) {
                T tmp = items.get(curr);
                items.set(curr, items.get(max));
                items.set(max, tmp);
                curr = max;
                leftChild = 2*curr+1;
            }
            else break;
        }
    }
 
    public void insert(T item) {
        items.add(item);
        shiftUp();
    }
 
    public T delete() throws NoSuchElementException {
        if (items.size() == 0) {
            throw new NoSuchElementException();
        }
        if (items.size() == 1) return items.remove(0);
        T x = items.get(0);
        items.set(0, items.remove(items.size()-1));
        shiftDown();
        return x;
    }
 
    public int size() {
        return items.size();
    }
 
    public boolean isEmpty() {
        return items.isEmpty();
    }
 
    public String toString() {
        return items.toString();
    }
 
    public T max() {
        return items.get(0);
    }
    public void print() {
        for (int i = 0; i < items.size(); i++) {
            System.out.print(items.get(i).toString() + " ");
        }
        System.out.println();
    }
}
 
class Codechef {   
	public static void main (String[] args) {
		Heap <Integer> test = new Heap<Integer> ();
		test.insert(16);
		test.insert(9);
		test.insert(11);
		test.insert(10);
		test.insert(13);
		test.insert(31);
		test.insert(19);
		test.insert(2);
		test.insert(50);
		test.insert(23);
		test.print();
		//To kill some hares in the same time:
		//- isEmpty() works;
		// max() and toString() too
		// so does delete() => shiftDown() works;
		// heapsort :D
		for (;!test.isEmpty();) {
		    System.out.print(test.max().toString() + " ");
		    test.delete();
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

import java.util.*;

import java.lang.*;

import java.io.*;

class Heap <T extends Comparable<T> > {

//arraylist is much better than an array. There is no need to carry about a capacity.

private ArrayList<T> items;

//construct

public Heap() {

items = new ArrayList<T> ();

}

//using shiftUp for insert.

private void shiftUp () {

int k = items.size() - 1;

while (k > 0){

int curr = (k-1)/2;

T Item = items.get(k);

T Parent = items.get(curr);

if (Item.compareTo(Parent) > 0){

items.set(k, Parent);

items.set(curr, Item);

k = curr;

}

else break;

}

//using shiftDown fo delete

private void shiftDown() {

int curr = 0;

int leftChild = 2*curr+1;

while (leftChild < items.size()) {

int max = leftChild;

int rightChild = leftChild + 1;

if (rightChild < items.size()) {

if (items.get(rightChild).compareTo(items.get(1)) > 0) {

++max;

}

if (items.get(curr).compareTo(items.get(max)) < 0) {

T tmp = items.get(curr);

items.set(curr, items.get(max));

items.set(max, tmp);

curr = max;

leftChild = 2*curr+1;

}

else break;

}

public void insert(T item) {

items.add(item);

shiftUp();

}

public T delete() throws NoSuchElementException {

if (items.size() == 0) {

throw new NoSuchElementException();

}

if (items.size() == 1) return items.remove(0);

T x = items.get(0);

items.set(0, items.remove(items.size()-1));

shiftDown();

return x;

}

public int size() {

return items.size();

}

public boolean isEmpty() {

return items.isEmpty();

}

public String toString() {

return items.toString();

}

public T max() {

return items.get(0);

}

public void print() {

for (int i = 0; i < items.size(); i++) {

System.out.print(items.get(i).toString() + " ");

}

System.out.println();

}

class Codechef {

public static void main (String[] args) {

Heap <Integer> test = new Heap<Integer> ();

test.insert(16);

test.insert(9);

test.insert(11);

test.insert(10);

test.insert(13);

test.insert(31);

test.insert(19);

test.insert(2);

test.insert(50);

test.insert(23);

test.print();

//To kill some hares in the same time:

//- isEmpty() works;

// max() and toString() too

// so does delete() => shiftDown() works;

// heapsort :D

for (;!test.isEmpty();) {

System.out.print(test.max().toString() + " ");

test.delete();

}

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

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

Задачи

e-olymp 903. Первая или последняя?

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

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

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

e-olymp 911. Квадратное уравнение

Тесты

e-olymp 905. Какой треугольник?

e-olymp 4. Two circles

Условие

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

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

Тесты:

Код на Java:

Ход решения:

Ссылки:

ML 24 Радиус вписанной/описанной в треугольник окружности

ML 24

e-olymp 126. Номер квартиры

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

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

Тесты

А58а

Тест

acm.timus.ru №2002. Тестовое задание

Условие

Исходные данные

Результат

Пример

Binary Heap (двоичная куча)

Двоичная куча

Описание методов

О реализации

Код