e-olymp 7365. Молоко и пирожок

01/01/2019 by Артем Чернобровкин

Задача

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее [latex]30 [/latex] кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость [latex]200 [/latex] мл, а упаковки молока — [latex]0,9 [/latex] л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

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

В первой строке задано целое число [latex]n[/latex] [latex](0 < n ≤ 100)[/latex]. В следующей строке идут [latex]n[/latex] положительных действительных чисел – массы первоклассников.

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

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

Тесты

#	Входные данные	Выходные данные
1	4 30 36 29 47	1 1
2	5 30 36 29 47 26	1 2
3	8 30 36 29 47 26 27 30 31	1 3
4	1 29	1 1
5	5 26 27 28 29 25	2 5

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

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


class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		DecimalFormat format = new DecimalFormat();
        format.setDecimalSeparatorAlwaysShown(false);
		double children ;
		double cakes = 0 ;
		double milk = 0; 
		double child ;
		Scanner in= new Scanner(System.in);
		children= in.nextDouble();
    	while (in.hasNextDouble()){
    		child= in.nextDouble();
        	if ( child < 30) {
            	cakes++; 
            	milk += 2;
        	}
		}
    	System.out.print(format.format(Math.ceil(milk/9)));
    	System.out.print(" ");
    	System.out.print(format.format(cakes));
    	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.text.DecimalFormat;

class Main

{

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

{

DecimalFormat format = new DecimalFormat();

format.setDecimalSeparatorAlwaysShown(false);

double children ;

double cakes = 0 ;

double milk = 0;

double child ;

Scanner in= new Scanner(System.in);

children= in.nextDouble();

while (in.hasNextDouble()){

child= in.nextDouble();

if ( child < 30) {

cakes++;

milk += 2;

}

System.out.print(format.format(Math.ceil(milk/9)));

System.out.print(" ");

System.out.print(format.format(cakes));

}

Решение

Для решения задачи мы должны узнать: сколько упаковок молока и пирожков нужно для детей.
Чтобы узнать количество пирожков мы заводим счетчик, который увеличивает на единицу, если появился подходящий ребенок.
А для молока будем использовать целые числа (0,2 домножим на 10 и 0,9 также домножим на 10). Будем считать сколько всего тратится молока, затем поделим на 9 и узнаем сколько пачек молока нужно. Результат подсчета количества молока может не быть целым, соответственно придется округлять вверх.
Рассмотрим аспекты синтаксиса:

Функция округления вверх:

Math.ceil();

1	Math.ceil();

В результате выполнения программы мы получим данные в виде [latex]n.0[/latex], где [latex]n[/latex]- любое целое число. Ответ является правильным, но, при проверке кода с помощью сайта e-olymp, мы сталкиваемся с проблемой, что во всех тестах ошибка. Для того, чтобы этого избежать используем:

Java

DecimalFormat format = new DecimalFormat(); format.setDecimalSeparatorAlwaysShown(false); format.format(Math.ceil(milk/9));

1
2
3
4

DecimalFormat format = new DecimalFormat();
format.setDecimalSeparatorAlwaysShown(false);

format.format(Math.ceil(milk/9));

из библиотеки java.text.DecimalFormat;
Данная ошибка возникла из-за того, что был использован тип double.

Ссылки

Задача на e-olymp

Код задачи на ideone

e-olymp 4764. Степени вершин

28/12/2018 by Артем Чернобровкин

Задача

Простой неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

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

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

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

Выведите [latex]n[/latex] чисел — степени всех вершин.

Тесты

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

Код задачи

import java.util.*;
public class Main
{
  public static void main(String[] args)

  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    //массив, в котором содержатся степени вершин
    int deg[] = new int[n];
    //Чтение матрицы смежности
    //и если есть ребро, то увеличиваем степень на 1
    for(int i = 0; i < n; i++)
    {
    	for(int j = 0; j < n; j++)

		 {
			int value = in.nextInt();
			if (value == 1)
    		{
    			deg[i]++;
    		}
		 }
    }
    //вывод результата
    for(int i = 0; i < n; i++)
    {
      System.out.println(deg[i]);     
    }
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

//массив, в котором содержатся степени вершин

int deg[] = new int[n];

//Чтение матрицы смежности

//и если есть ребро, то увеличиваем степень на 1

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

{

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

{

int value = in.nextInt();

if (value == 1)

{

deg[i]++;

}

//вывод результата

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

{

System.out.println(deg[i]);

}

Решение

В ячейке [latex]deg[i][/latex] будем подсчитывать степень вершины [latex]i[/latex], которая равна количеству единиц в i-ой строки матрицы смежности.
Для неориентированного графа степень вершины — это количество всех инцидентных ей ребер.
Граф [latex]G=(V,U)[/latex] может быть задан матрицей смежности. Это квадратная матрица размерности [latex]n\times n[/latex], где [latex]n=\left |V \right | [/latex]. Матрица смежности неориентированного графа симметрична. Элементы матрицы смежности определяются следующим образом.
1- если [latex]i[/latex]-тая и [latex]j[/latex]-тая вершины графа смежны
0- иначе
[latex] a_{ij}=\left\{\begin{matrix}
1\\
0
\end{matrix}\right.\\[/latex]

Ссылки

Задача на e-olymp

Код задачи на ideone

e-olymp 2197. Антипалиндром

27/12/2018 by Артем Чернобровкин

Задача

Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка [latex]s[/latex]. Найдите её наибольшую по длине подстроку, не являющуюся палиндромом.

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

Входной файл содержит строку [latex]s[/latex]. Она состоит только из строчных букв латинского алфавита, не пуста, её длина не превышает 100000 символов.

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

В выходной файл выведите ответ на задачу, если ответов несколько — выберите лексикографически минимальный. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.

Тесты

#	Входные данные	Выходные данные
1	abba	abb
2	aaaaaaa	NO SOLUTION
3	abcghgcba	abcghgcb
4	abaaabbb	abaaabbb

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static boolean Function(String s)
	{
		for (int i = 1; i < s.length(); i++)
		{
			if (s.charAt(i) != s.charAt(0)) return false;
		}
		return true;
	}
 
	public static boolean palindrom(String s)
	{
		for (int i = 0; i < s.length()/2; i++)
		{
			if (s.charAt(i) != s.charAt(s.length() - i - 1)) return false;
		}
		return true;
	}
 
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in=new Scanner(System.in);
		String s = in.nextLine();
		if (Function(s)) System.out.println("NO SOLUTION");
		else
		{
			if (!palindrom(s)) System.out.println(s);
			else
			{
				if (s.charAt(0) < s.charAt(1)) System.out.println(s.substring(0, s.length() - 1));
				else System.out.println(s.substring(1));
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static boolean Function(String s)

{

for (int i = 1; i < s.length(); i++)

{

if (s.charAt(i) != s.charAt(0)) return false;

}

return true;

}

public static boolean palindrom(String s)

{

for (int i = 0; i < s.length()/2; i++)

{

if (s.charAt(i) != s.charAt(s.length() - i - 1)) return false;

}

return true;

}

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

{

Scanner in=new Scanner(System.in);

String s = in.nextLine();

if (Function(s)) System.out.println("NO SOLUTION");

else

{

if (!palindrom(s)) System.out.println(s);

else

{

if (s.charAt(0) < s.charAt(1)) System.out.println(s.substring(0, s.length() - 1));

else System.out.println(s.substring(1));

}

Решение

Проверка на строку, состоящую из одинаковых символов
Проверка на палиндром
Вывод в лексикографическом порядке

Ссылки

Задача на e-olymp

Код задачи на ideone

e-olymp 47. Паркет из треугольников

27/12/2018 by Артем Чернобровкин

Задача

Прямоугольную комнату размерами [latex] m [/latex] на [latex] n [/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex] a [/latex] на паркетину [latex] b [/latex].

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

Во входном файле в первой сроке через пробел заданы значения [latex]m[/latex], [latex]n[/latex] [latex]\left ( 1\leqslant n,m\leqslant 100 \right )[/latex], а во второй — [latex] a [/latex] и [latex] b [/latex].

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

Искомое количество шагов

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
3	5 4 15 22	3
5	3 2 6 12	2

Код 1

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


class Main
{
	public static void swap(int A, int B) {
		int C = A;
		A = B;
		B = C;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		int vertSize;
		int horSize;
    	int firstNumber;
    	int lastNumber;
    	Scanner in = new Scanner(System.in);
    	horSize = in.nextInt();
		vertSize = in.nextInt();
		firstNumber = in.nextInt();
		lastNumber= in.nextInt();
    	if (firstNumber > lastNumber){
    		int C = firstNumber;
			firstNumber = lastNumber;
			lastNumber = C;
    	} 
    //вычисление координат
    	int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    	int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    	int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    	int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    	int[] Search= new int[2 * horSize];
    	Search[firstNumberx - 1] = 0;
    	int step = 1;
    	for (int i = firstNumberx - 2; i >= 0; i--){
        	Search[i] = step++;
    	}
    	step = 1;
    	for (int i = firstNumberx; i < 2 * horSize; i++){
        	Search[i] = step++;
    	}
    	//сравнение по у
    	for (int j = firstNumbery; j < lastNumbery; j++) {
        	for (int i = 1; i < 2 * horSize; i += 2) {
            	Search[i - 1] = Search[i] + 1;
            	Search[i] += 2;
            //определение значения на предпоследнем элементе
            	if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                	Search[i - 2] = Search[i];
            	}
        	}
    	}
    System.out.println(Search[lastNumberx - 1]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void swap(int A, int B) {

int C = A;

A = B;

B = C;

}

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

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

Scanner in = new Scanner(System.in);

horSize = in.nextInt();

vertSize = in.nextInt();

firstNumber = in.nextInt();

lastNumber= in.nextInt();

if (firstNumber > lastNumber){

int C = firstNumber;

firstNumber = lastNumber;

lastNumber = C;

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int[] Search= new int[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

for (int i = firstNumberx; i < 2 * horSize; i++){

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

for (int i = 1; i < 2 * horSize; i += 2) {

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

Search[i] += 2;

//определение значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

System.out.println(Search[lastNumberx - 1]);

}

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Следующим шагом будет определение позиции [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Положим, что [latex]x[/latex] — это позиция в строке, а [latex]y[/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем массив, переменные в котором будет иметь тип [latex]int[/latex] , а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex]int[/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции [latex]Search[firstNumberx — 1][/latex] стояло количество шагов, совершенных в ходе решения.

Код 2

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long m, n, a, b;
		Scanner in = new Scanner(System.in);
		m = in.nextLong();
		n = in.nextLong();
		a = in.nextLong();
		b = in.nextLong();
    	long dm = ((a + 1)/2 - 1) %m - ((b + 1)/2 - 1) % m;
    	long dn = (a - 1)/(2 * m) - (b - 1)/(2 * m);
    	long o = dm * dn < 0? Math.min(Math.abs(dm), Math.abs(dn)) : 0;
    	long k = dm > 0? 1: -1;
    	a += 2*k*o*(m - 1);
    	System.out.print( ((a + b) % 2 == 0? 0: Math.max(a, b) % 2 == 0? 1: -1) + 2*(Math.abs(dm) + Math.abs(dn) - o));

	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long m, n, a, b;

Scanner in = new Scanner(System.in);

m = in.nextLong();

n = in.nextLong();

a = in.nextLong();

b = in.nextLong();

long dm = ((a + 1)/2 - 1) %m - ((b + 1)/2 - 1) % m;

long dn = (a - 1)/(2 * m) - (b - 1)/(2 * m);

long o = dm * dn < 0? Math.min(Math.abs(dm), Math.abs(dn)) : 0;

long k = dm > 0? 1: -1;

a += 2*k*o*(m - 1);

System.out.print( ((a + b) % 2 == 0? 0: Math.max(a, b) % 2 == 0? 1: -1) + 2*(Math.abs(dm) + Math.abs(dn) - o));

}

Ссылки

Задача на e-olymp

Код_1 задачи на ideone

Код_2 задачи на ideone

e-olymp 926. Формула Герона

16/09/2018 by Артем Чернобровкин

Задача

Задано стороны [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex] и диагональ [latex]f[/latex] выпуклого четырехугольника. Определить площадь четырехугольника, используя вспомогательную функцию вычисления площади треугольника по формуле Герона.

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

В одной строке задано [latex]5[/latex] действительных чисел [latex] a, b, с, d, f [/latex] [latex]( 0 < a, b, c, d, f \leqslant 100 )[/latex], как показано на рисунке.

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

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

Тесты

#	Входные данные	Выходные данные
1	2 2 2 2 2	3.4641
2	7 7 5 6 2	11.6120
3	9 5 3 2 4	2.9047
4	5 7 2 3 4	12.7027
5	7 8 6 2 5	22.0043

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double a,b,c,d,f,p1,p2,S1,S2,S;
    	 	Scanner in = new Scanner(System.in);
		a = in.nextDouble();
		b = in.nextDouble();
		c = in.nextDouble();
		d = in.nextDouble();
		f = in.nextDouble();
		p1=(a+b+f)/2;
		p2=(c+d+f)/2;
		S = Math.sqrt(p1*(p1-a)*(p1-b)*(p1-f)) +  Math.sqrt(p2*(p2-c)*(p2-d)*(p2-f));
		System.out.printf("%.4f",S);
	 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

double a,b,c,d,f,p1,p2,S1,S2,S;

Scanner in = new Scanner(System.in);

a = in.nextDouble();

b = in.nextDouble();

c = in.nextDouble();

d = in.nextDouble();

f = in.nextDouble();

p1=(a+b+f)/2;

p2=(c+d+f)/2;

S = Math.sqrt(p1*(p1-a)*(p1-b)*(p1-f)) + Math.sqrt(p2*(p2-c)*(p2-d)*(p2-f));

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

}

Решение

Воспользуемся формулой Герона [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)}[/latex] для каждого из двух треугольников

Сложим полученные результаты

Важно отметить, что в условие задана точность вычисления. Укажем это в соответствующем месте вывода :

Java

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

1

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

Ссылки

Задача на e-olymp

Код задачи на ideone