e-olymp 2470. Проверка на неориентированность

27/12/2018 by Валерия Ларикова

Задача

По заданной квадратной матрице [latex]n×n[/latex] из нулей и единиц определить, может ли она быть матрицей смежности простого неориентированного графа. Напомним, что простой граф не содержит петли и мультиребра.

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

В первой строке задано число [latex](1 \leqslant n \leqslant 100).[/latex] Затем идут [latex]n[/latex] строк по [latex]n[/latex] элементов в каждой — описание матрицы смежности.

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

Вывести [latex]YES,[/latex] если граф простой неориентированный, и [latex]NO[/latex] в противном случае.

Тесты

#	Входные данные	Выходные данные
1	3 0 1 1 1 0 1 1 1 0	YES
2	3 0 1 1 1 0 1 0 1 0	NO
3	3 0 1 0 1 1 1 0 1 0	NO
4	4 1 1 1 1 1 0 1 1 1 1 0 1	NO
5	4 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0	YES

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main
{
	public static void main(String[] args)  throws IOException
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int a[][] = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				a[i][j] = in.nextInt();
				if ((i == j) && (a[i][j] == 1)) {
					System.out.print("NO");
					return;
				}
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if (a[i][j] != a[j][i]) {
					System.out.print("NO");
					return;
				}
			}
		}
		System.out.print("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main(String[] args) throws IOException

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int a[][] = new int[n][n];

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

for(int j = 0; j < n; j++) {

a[i][j] = in.nextInt();

if ((i == j) && (a[i][j] == 1)) {

System.out.print("NO");

return;

}

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

for(int j = 0; j < n; j++) {

if (a[i][j] != a[j][i]) {

System.out.print("NO");

return;

}

System.out.print("YES");

}

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

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j] = a[j][i].[/latex] Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия. Для этого воспользуемся обычными двумерными массивами. Затем проверим является ли граф простым. Если [latex]a[i][j] = 1,[/latex] то граф содержит петлю, следовательно простым не является. Затем проверим матрицу на симметричность, т. е. выполняется ли условие [latex]a[i][j] = a[j][i].[/latex] Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, то это означает, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится [latex]«NO».[/latex] Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим [latex]«YES».[/latex]

Ссылки

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

e-olymp 44. Единицы

27/12/2018 by Валерия Ларикова

Задача

В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?

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

Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]

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

Искомое количество единиц.

Тесты

#	Входные данные	Выходные данные
1	7	6
2	22	10
3	90	13
4	157	16
5	985	21

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.lang.Math;
 
class Main
{
	public static int max = 5001;
	static int [] x = new int[max];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k;
		x[1] = 1;
		x[2] = 2;
		for (int i = 3; i <= n; i++) {
			x[i] = x[i-1]+1;
			for (int j = 2; j <= Math.sqrt(n); j++) {
				if(i % j == 0) {
					k = x[j] + x[i/j];
					if( k < x[i]) x[i] = x[j] + x[i/j];
				}
			}
		}
		System.out.println(x[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

public static int max = 5001;

static int [] x = new int[max];

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k;

x[1] = 1;

x[2] = 2;

for (int i = 3; i <= n; i++) {

x[i] = x[i-1]+1;

for (int j = 2; j <= Math.sqrt(n); j++) {

if(i % j == 0) {

k = x[j] + x[i/j];

if( k < x[i]) x[i] = x[j] + x[i/j];

}

System.out.println(x[n]);

}

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

Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.

Ссылки

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

e-olymp 2803. МаркЕрованные кубики

26/12/2018 by Валерия Ларикова

Задача

У Витека есть набор кубиков, на котором изображены английские буквы, причём как маленькие, так и большие. Недавно мама подарила ему ещё и набор кубиков с цифрами, в результате чего Витек научился быстро считать в пределах [latex]10-[/latex]ти. А вот папа имел неосторожность подарить ему набор разноцветных маркеров, после чего Витек начал экспериментировать с кубиками с цифрами: он зарисовывал очередную цифру и на её месте рисовал цифру на единицу большую. Так как он прекрасно понимал, что цифры [latex]10[/latex] не существует, он вместо числа [latex]10[/latex] всегда писал цифру [latex]0.[/latex]

Учтите, что иногда мама звала Витека покушать и он не успевал завершить начатую работу и написать новую цифру – в этом случае кубик навсегда оставался пустым, такие кубики обозначены символом пробела.

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

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

Единственная строка, состоящая из описанных выше символов. Длина строки не превышает [latex]255[/latex] символов.

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

Единственная строка – результат работы Вашей программы.

Тесты

#	Входные данные	Выходные данные
1	abc1234567890ABC	abc2345678901ABC
2	fgrt7645gft5	fgrt8756gft6
3	65748909674	76859010785
4	6ASD4890gf9674	7ASD5901gf0785
5	RFT768S7dfr	RFT879S8dfr

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String str = bufferedReader.readLine();
		char[] s = str.toCharArray();
		for(int i = 0; i < str.length(); i++) {
			if(s[i]>='0' && s[i]<'9'){
				s[i]++;
			}
			else if(s[i]=='9') s[i]='0';
		}
		System.out.println(s);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

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

String str = bufferedReader.readLine();

char[] s = str.toCharArray();

for(int i = 0; i < str.length(); i++) {

if(s[i]>='0' && s[i]<'9'){

s[i]++;

}

else if(s[i]=='9') s[i]='0';

}

System.out.println(s);

}

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

Для решения задачи вводим строку [latex]str[/latex] и преобразовываем её в массив символов. Так как у Витека есть кубики с буквами и цифрами, то проверяем, является ли элемент строки числом. Если да, то увеличиваем значение символа на [latex]1,[/latex] а если это [latex]9,[/latex] то заменяем её на [latex]0.[/latex]

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 2666. Половина

24/12/2018 by Валерия Ларикова

Задача

Напишите программу, заполняющую массив [latex]n × n[/latex] следующим образом: на побочной диагонали стоят нули, выше диагонали двойки, ниже единицы.

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

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

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

Выведите массив, заполненный по указанному правилу.

Тесты

#	Входные данные	Выходные данные
1	2	20 01
2	3	220 201 011
3	4	2220 2201 2011 0111
4	5	22220 22201 22011 20111 01111
5	10	2222222220 2222222201 2222222011 2222220111 2222201111 2222011111 2220111111 2201111111 2011111111 0111111111

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[][] arr = new int [20][20];
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				if(i + j == n - 1) arr[i][j] = 0;
				else if (i + j < n - 1) arr[i][j] = 2;
				else arr[i][j] = 1;
			}
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				System.out.print(arr[i][j]);
			}
		System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] arr = new int [20][20];

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

for (int j = 0; j < n; j++){

if(i + j == n - 1) arr[i][j] = 0;

else if (i + j < n - 1) arr[i][j] = 2;

else arr[i][j] = 1;

}

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

for (int j = 0; j < n; j++){

System.out.print(arr[i][j]);

}

System.out.println();

}

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

Для решения задачи создадим двумерный массив, количество строк и столбцов которого не превышают [latex]20.[/latex] Заполнять его будем при помощи двойного цикла, как указано в решении задачи. Введем следующие обозначения:

[latex]i + j = n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит на побочной диагонали;
[latex]i + j > n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит ниже побочной диагонали;
[latex]i + j < n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит выше побочной диагонали.

Далее заполняем массив в соответствии с введеными обозначениями и условием задачи, а затем выводим его на экран. Задача решена.

Ссылки

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

e-olymp 7809. Утренняя зарядка

24/12/2018 by Валерия Ларикова

Задача

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

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

Единственная строка входного файла содержит последовательность чисел, записанных через пробел, означающие цвет футболки. Цвет — число в диапазоне от [latex]0[/latex] до [latex]9.[/latex] Всего в строке не более, чем [latex]10^6[/latex] чисел.

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

В выходной файл нужно вывести единственное число — количество эстетических пар, которые можно сложить.

Тесты

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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String p = bufferedReader.readLine();
		long s=0;
		long[] x= {0,0,0,0,0,0,0,0,0,0};
		for(int i = 0; i < p.length(); i++) {
			char n = p.charAt(i);
			if(n =='0') x[0]++;
			else if(n =='1') x[1]++;
			else if(n =='2') x[2]++;
			else if(n =='3') x[3]++;
			else if(n =='4') x[4]++;
			else if(n =='5') x[5]++;
			else if(n =='6') x[6]++;
			else if(n =='7') x[7]++;
			else if(n =='8') x[8]++;
			else if(n =='9') x[9]++;
		}
		for(int i = 0; i < 10; i++)
			if (x[i]>1) s+=x[i]/2;
		System.out.print(s);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

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

String p = bufferedReader.readLine();

long s=0;

long[] x= {0,0,0,0,0,0,0,0,0,0};

for(int i = 0; i < p.length(); i++) {

char n = p.charAt(i);

if(n =='0') x[0]++;

else if(n =='1') x[1]++;

else if(n =='2') x[2]++;

else if(n =='3') x[3]++;

else if(n =='4') x[4]++;

else if(n =='5') x[5]++;

else if(n =='6') x[6]++;

else if(n =='7') x[7]++;

else if(n =='8') x[8]++;

else if(n =='9') x[9]++;

}

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

if (x[i]>1) s+=x[i]/2;

System.out.print(s);

}

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

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

Ссылки

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

e-olymp 7368. Средний балл для фигуристов

09/12/2018 by Валерия Ларикова

Задача

Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n \leqslant 10, 0 < m \leqslant 100)[/latex] для каждого из фигуристов.

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

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

Тесты

#	Входные данные	Выходные данные
1	5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8	8.33 5.33 9.00 8.50
2	6 3 6 7 6 5 4 3 9 8 5 5 6 5 7 6 4 1 2 2	5.25 7.00 3.50
3	4 5 6 7 8 6 9 8 5 4 7 6 7 5 4 3 9 3 7 8 7 6	7.00 6.50 6.00 4.00 7.00
4	4 4 7 7 2 3 9 8 3 3 5 4 9 7 4 3 2 6	3.00 8.00 6.00 3.50
5	8 5 4 5 6 7 7 4 9 8 3 5 6 6 7 8 5 9 7 6 3 9 3 7 9 7 5 6 4 3 7 7 5 7 9 8 4 6 7 9 9 4	6.60 6.17 6.75 5.00 7.00

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

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

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    double n, m;
    double x, min = 100, max = -100, sum = 0, a = 0, b = 0;
    Scanner in = new Scanner(System.in);
    n = in.nextDouble();
    m = in.nextDouble();
    for (int i = 0; i < m; i++){
      for (int j = 0; j < n; j ++){
        x = in.nextDouble();
        if (max == x) a++;
        if (max < x) {
          if (max != min) sum += a*max;
          a = 1;
          max = x;
        }
        if ( min == x) b++;
        if (min > x) {
          if (max != min) sum += b*min;
          b = 1;
          min = x;
        }
      if (x!= min && x != max) sum += x;
      }
      if(i == m-1) System.out.printf("%.2f", sum / (n - a - b));
      else System.out.printf("%.2f ", sum / (n - a - b));
      sum = a = b = 0;
      min = 100;
      max = -100;
    }
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

double n, m;

double x, min = 100, max = -100, sum = 0, a = 0, b = 0;

Scanner in = new Scanner(System.in);

n = in.nextDouble();

m = in.nextDouble();

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

for (int j = 0; j < n; j ++){

x = in.nextDouble();

if (max == x) a++;

if (max < x) {

if (max != min) sum += a*max;

a = 1;

max = x;

}

if ( min == x) b++;

if (min > x) {

if (max != min) sum += b*min;

b = 1;

min = x;

}

if (x!= min && x != max) sum += x;

}

if(i == m-1) System.out.printf("%.2f", sum / (n - a - b));

else System.out.printf("%.2f ", sum / (n - a - b));

sum = a = b = 0;

min = 100;

max = -100;

}

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

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x,[/latex] и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n — a — b.[/latex] А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\displaystyle\frac{sum}{n — a — b}[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 2807. Кубики-3

03/12/2018 by Валерия Ларикова

Задача

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

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

В первой строке задано количество найденных Витеком кубиков [latex]n[/latex] [latex](1 \leqslant n \leqslant 10^5),[/latex] а во второй строке n символов, изображённых на каждом из кубиков

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex]»Ok»,[/latex] если Витек ошибся и ни один из кубиков не потерялся.

Тесты

#	Входные данные	Выходные данные
1	5 abcac	b
2	8 ryirhiyh	Ok
3	3 AVA	V
4	6 DjkjDk	Ok
5	7 LnCsCnL	s

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

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

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s = in.next();
		char res = 0;
		for(int i = 0; i < n; i++)
			res ^= s.charAt(i);
		if (res == 0)
			System.out.println("Ok");
		else 
			System.out.printf("%c\n",res);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String s = in.next();

char res = 0;

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

res ^= s.charAt(i);

if (res == 0)

System.out.println("Ok");

else

System.out.printf("%c\n",res);

}

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

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Воспользуемся оператором присваивания побитового исключающего или, с помощью которого мы будем сравнивать индексы символов, полученные из массива строки. Если количество кубиков четное, то переменная [latex]res[/latex] будет равна нулю, следовательно не один из кубиков не потерялся и мы увидим сообщение с текстом [latex] «Ok»[/latex]. Иначе выводится символ, который изображен на потерянном кубике.

Ссылки

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

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

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

Задача

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

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

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

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

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

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

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

Тесты

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

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int n, m, d;

Scanner in = new Scanner(System.in);

n = in.nextInt();

m = in.nextInt();

d = func(m, n);

System.out.print(d);

}

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

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

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

}

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

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

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

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

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 932. Высота треугольника

19/09/2018 by Валерия Ларикова

Задача

Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].

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

Два целых числа [latex]S[/latex] [latex](0 < S \leqslant 100)[/latex] и [latex]a[/latex] [latex](|a| \leqslant 100)[/latex].

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

Вывести высоту треугольника с точностью до сотых.

Тесты

#	Входные данные	Выходные данные
1	20 7	3.73
2	35 3	7.00
3	12 4	3.29
4	67 9	7.92
5	135 13	11.17

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int s, a;
		double h, dk;
		Scanner in = new Scanner(System.in);
		s = in.nextInt();
		a = in.nextInt();
		dk = Math.sqrt(a*a + 8*s);
		h = (-a + dk) / 2;
		System.out.printf("%.2f",h);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int s, a;

double h, dk;

Scanner in = new Scanner(System.in);

s = in.nextInt();

a = in.nextInt();

dk = Math.sqrt(a*a + 8*s);

h = (-a + dk) / 2;

System.out.printf("%.2f",h);

}

Решение

Для решения задачи нам понадобится формула для нахождения площади треугольника: [latex]S = \frac{1}{2} \cdot h \cdot c[/latex], где [latex]h[/latex] — высота, [latex]c[/latex] — сторона, к которой высота проведена. Вместо [latex]c[/latex] подставим [latex]h+a[/latex] (по условию задачи). Далее приходим к квадратному уравнению [latex]h^2 + a \cdot h — 2 \cdot S = 0[/latex]. Решив его, получим два корня. Второй корень нам не подходит, поскольку он меньше [latex]0[/latex], а длина не может быть отрицательной. Первый корень и будет ответом нашей задачи.

Ссылки

Ссылка на e-olymp

Ссылка на ideone