e-olymp 266. Сравнение

27/12/2018 by Даниил Крутоголов

Сравнение

Сравните два числа A и B.

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

Во входном файле задано два целых неотрицательных числа A и B $(A, B <= 10^{10000})$ каждое в своей строке.

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

В выходной файл выведите <, если A < B, = , если A = B и >, если A > B.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$2$ $1$	$>$
2	$1$ $2$	$<$
3	$1$ $1$	$=$

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		String x, y;
		x = in.next();
		y = in.next();
		if (x.length() > y.length() ){
			System.out.print('>');
		}
		else if (x.length() < y.length() ){
			System.out.print('<');
		}
		else {
			int i = 0;
			while (i < x.length() && x.charAt(i) == y.charAt(i)){
				i++;
			}
		if (i == x.length()) System.out.print('=');
		else if (x.charAt(i) < y.charAt(i)) System.out.print('<');
		else System.out.print('>');
		}
	}
}

import java.util.Scanner;

class Main

{

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

{

Scanner in = new Scanner(System.in);

String x, y;

x = in.next();

y = in.next();

if (x.length() > y.length() ){

System.out.print('>');

}

else if (x.length() < y.length() ){

System.out.print('<');

}

else {

int i = 0;

while (i < x.length() && x.charAt(i) == y.charAt(i)){

i++;

}

if (i == x.length()) System.out.print('=');

else if (x.charAt(i) < y.charAt(i)) System.out.print('<');

else System.out.print('>');

}

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

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

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 313. A + B

27/12/2018 by Даниил Крутоголов

A + B

Пете задали домашнее задание: найти сумму 2-х натуральных чисел A и B.

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

В первой строке задано количество заданных Пете примеров N, а далее следует N строк в формате A+B, где A и B — 2 заданных натуральных числа, между ними без пробелов символ выполнения действия сложения «+».
Соответствие входных данных указанному формату гарантируется (см. пример входных данных). Входные данные не превышают $10^{500}$. $(0 < N <= 250)$

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

В N строках вывести искомые суммы.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$2$ $5+3$ $14818641113280510+52467$	$8$ $14818641113332977$
2	$1$ $0+0$	$0$
3	$3$ $1+1$ $1+2$ $1+3$	$2$ $3$ $4$
4	$2$ $123123123 + 321321321$ $321321321 + 123123123$	$444444444$ $444444444$

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

import java.util.Scanner;
import java.math.BigInteger;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.nextLine();
		while(n-- > 0){
			String s = scan.nextLine();
			int k = s.indexOf('+');
			System.out.println(new BigInteger(s.substring(0, k)).add(new BigInteger(s.substring(k+1))));
		}
	}
}

import java.util.Scanner;

import java.math.BigInteger;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

scan.nextLine();

while(n-- > 0){

String s = scan.nextLine();

int k = s.indexOf('+');

System.out.println(new BigInteger(s.substring(0, k)).add(new BigInteger(s.substring(k+1))));

}

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

Для решения данной задачи будем использовать класс BigInteger, поскольку в наших вычислениях могут получиться числа, превышающие максимальное значение класса Long. k-тым элементом обозначим символ «+». Далее, складываем все элементы до k-того элемента и после него, переводя эти числа в объект класса BigInteger.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 7623. Счастливые случаи

16/12/2018 by Даниил Крутоголов

Счастливые случаи

Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

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

В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.

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

Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$1$ $1$ $4$	$4$
2	$2$ $4$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$	$12$
3	$3$ $2$ $10$ $10$ $10$ $10$ $4$ $5$	$13$
4	$2$ $2$ $1$ $2$ $3$ $4$	$12$
5	$0$ $0$	$0$

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int w = 0, a, b, l, d;
		Scanner scan = new Scanner(System.in);
		int r = scan.nextInt();
		int c = scan.nextInt();
		int[][] x = new int [r][r];
		for (int i = 0; i < r; i++) 
			x[i] = new int[c];
		for (int i = 0; i < r; i++){
			for (int j = 0; j < c; j++){
				x[i][j] = scan.nextInt();
			}
		}
		for (int i = 0; i < r; i++){
			for (int j = 0; j < c; j++){
				a = b = l = d = 1;
			for (int q = 0; q < i; q++){
				if (x[i][j] <= x[q][j])
					a = 0;
			}
			for (int q = i+1; q < r; q++){
				if (x[i][j] <= x[q][j])
					 b = 0;
			}
			for (int k = 0; k < j; k++){
				if (x[i][j] <= x[i][k])
					l = 0;
			}
			for (int k = j+1; k < c; k++){
				if (x[i][j] <= x[i][k])
					d = 0;
			}
			w+= a + b + l + d;
			}
		}
		System.out.print(w);
	}
}

import java.util.Scanner;

class Main

{

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

{

int w = 0, a, b, l, d;

Scanner scan = new Scanner(System.in);

int r = scan.nextInt();

int c = scan.nextInt();

int[][] x = new int [r][r];

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

x[i] = new int[c];

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

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

x[i][j] = scan.nextInt();

}

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

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

a = b = l = d = 1;

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

if (x[i][j] <= x[q][j])

a = 0;

}

for (int q = i+1; q < r; q++){

if (x[i][j] <= x[q][j])

b = 0;

}

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

if (x[i][j] <= x[i][k])

l = 0;

}

for (int k = j+1; k < c; k++){

if (x[i][j] <= x[i][k])

d = 0;

}

w+= a + b + l + d;

}

System.out.print(w);

}

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

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

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 165. Симметрия

16/12/2018 by Даниил Крутоголов

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]10[/latex]	[latex]2[/latex]
2	[latex]116[/latex]	[latex]3[/latex]
3	[latex]1[/latex]	[latex]1[/latex]
4	[latex]454[/latex]	[latex]2[/latex]
5	[latex]12301230[/latex]	[latex]2[/latex]

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		double k;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = (int)(Math.log(n)/Math.log(2));
		k = (double)(Math.log(n)/Math.log(2));
		while (m != k){
			n = (int)(n - (Math.pow(2,m)));
			m = (int)(Math.log(n)/Math.log(2));
			k = (double)(Math.log(n)/Math.log(2));
		}
	System.out.print(m + 1);
	}
}

import java.util.Scanner;

class Main

{

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

{

int n, m;

double k;

Scanner scan = new Scanner(System.in);

n = scan.nextInt();

m = (int)(Math.log(n)/Math.log(2));

k = (double)(Math.log(n)/Math.log(2));

while (m != k){

n = (int)(n - (Math.pow(2,m)));

m = (int)(Math.log(n)/Math.log(2));

k = (double)(Math.log(n)/Math.log(2));

}

System.out.print(m + 1);

}

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 52. Сыр для Анфисы

03/12/2018 by Даниил Крутоголов

Сыр для Анфисы

Готовя обед для Анфисы — символа 2008 года, хозяин использовал для разрезания сыра специальный нож, который разрезал сыр на одинаковые прямоугольные паралелепипеды с основанием в виде квадрата со стороной [latex]a[/latex] и высотой [latex]b[/latex].
Но Анфиса, как и подобает даме года, любила употреблять сыр несколько меньших размеров, для чего она всегда разрезала предложенный кусочек деликатеса на две части, предварительно установив его строго вертикально квадратом к столу. При разрезании нож всегда размещался по диагонали квадрата, но Анфисе не всегда удавалось разрезать кусочек пополам, так как плоскость лезвия ножа образовывала двугранный угол [latex]z^o[/latex] с плоскостью основания.
Найти площадь [latex]s[/latex] созданного Анфисой сечения.

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

Целые числа [latex]a[/latex], [latex]b[/latex], [latex]z[/latex], не превышающие [latex]90^o[/latex].

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

Площадь [latex]s[/latex] образованного сечения с точностью до трех десятичных знаков.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]3[/latex] [latex]90[/latex]	[latex]8.485[/latex]
2	[latex]2[/latex] [latex]4[/latex] [latex]0[/latex]	[latex]0.000[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex]	[latex]0.501[/latex]
4	[latex]1[/latex] [latex]1[/latex] [latex]100[/latex]	[latex]1.615[/latex]
5	[latex]3[/latex] [latex]10[/latex] [latex]48[/latex]	[latex]6.725[/latex]

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

import java.util.Scanner;
import java.lang.Math;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double a, b, z, s;
		Scanner scan = new Scanner(System.in);
		a = scan.nextDouble();
		b = scan.nextDouble();
		z = scan.nextDouble();
		if ((1 / (Math.tan (z * Math.PI / 180)) > a / Math.sqrt(2) / b) && (z != 0) && (z != 90)){
        	s = a * a / 2 / Math.cos (z * Math.PI / 180);
		}
		else if (z == 0) {
        	s = 0;
		}
		else if (z == 90) {
        	s = a * b * Math.sqrt(2);
		}
		else {
        	s = (a * Math.sqrt(2) - b * 1 / (Math.tan (z * Math.PI / 180))) * b / Math.sin (z * Math.PI / 180);
		}
		System.out.printf("%.3f", s);
	}
}

import java.util.Scanner;

import java.lang.Math;

class Main

{

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

{

double a, b, z, s;

Scanner scan = new Scanner(System.in);

a = scan.nextDouble();

b = scan.nextDouble();

z = scan.nextDouble();

if ((1 / (Math.tan (z * Math.PI / 180)) > a / Math.sqrt(2) / b) && (z != 0) && (z != 90)){

s = a * a / 2 / Math.cos (z * Math.PI / 180);

}

else if (z == 0) {

s = 0;

}

else if (z == 90) {

s = a * b * Math.sqrt(2);

}

else {

s = (a * Math.sqrt(2) - b * 1 / (Math.tan (z * Math.PI / 180))) * b / Math.sin (z * Math.PI / 180);

}

System.out.printf("%.3f", s);

}

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

Для решения данной задачи нам нужно рассмотреть 4 случая:
1) Если [latex]\cot[/latex] заданного угла не будет превышать [latex]\frac{a} {\sqrt{2} \cdot b}[/latex] и также не будет равен [latex]0^o[/latex] и [latex]90^o[/latex], то фигурой сечения получится треугольник. Его площадь мы сможем найти по формуле [latex]s = \frac {a^{2}} {2 \cos (z \cdot \frac {\pi} {180})}[/latex].
2) Заданный угол = [latex]0^o[/latex], следовательно площадь сечения также будет = 0, так как сыр нормально и не порежут.
3) Заданный угол = [latex]90^o[/latex], фигурой сечения будет прямоугольник, площадь которого мы сможем найти по формуле [latex]s = a \cdot b \cdot \sqrt{2}[/latex].
4) В любом другом случае, получится трапеция, площадь которой мы найдем по формуле [latex]s = \frac {a \cdot \sqrt{2} — b \cdot 1} {tan(z \cdot \frac{\pi}{180})} \cdot \frac {b} {sin (z \cdot \frac {\pi}{180})}[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 179. Распределение

02/10/2018 by Даниил Крутоголов

Распределение

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

Напишите программу, которая определяет минимальное количество переводов для перераспределения войск.

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

Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
2 4 2 5 1	1
1 4 4	0
3 2 2 2 4 1 1	2
3 6 3 1 0 0 10	9

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		int size = scan.nextInt();
		long arr1[] = new long [size];
		long arr2[] = new long [size];
		for(int i = 0; i < size; i++){
			arr1[i] = scan.nextInt();
		}
		for(int i = 0; i < size; i++){
			arr2[i] = scan.nextInt();
		}
		long tmp = 0;
		for(int i = 0; i < size; i++){
			tmp+= Math.abs(arr2[i] - arr1[i]);
		}
		System.out.println (tmp / 2);
	}
}

import java.util.Scanner;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

int size = scan.nextInt();

long arr1[] = new long [size];

long arr2[] = new long [size];

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

arr1[i] = scan.nextInt();

}

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

arr2[i] = scan.nextInt();

}

long tmp = 0;

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

tmp+= Math.abs(arr2[i] - arr1[i]);

}

System.out.println (tmp / 2);

}

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

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

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 520. Сумма всех

19/09/2018 by Даниил Крутоголов

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]4[/latex]	[latex]6[/latex]
2	[latex]3[/latex]	[latex]3[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]9[/latex]
4	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex]	[latex]10[/latex]
5	[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]	[latex]0[/latex]

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

import java.util.Scanner;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scanner = new Scanner(System.in);
		long a, sum = 0;
		while (scanner.hasNext()){
			a = scanner.nextLong();
			sum += a;
		}
		System.out.println (sum);
	}
}

import java.util.Scanner;

class Main

{

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

{

Scanner scanner = new Scanner(System.in);

long a, sum = 0;

while (scanner.hasNext()){

a = scanner.nextLong();

sum += a;

}

System.out.println (sum);

}

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

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 7944. Площадь прямоугольника

19/09/2018 by Даниил Крутоголов

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex] [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]1[/latex] [latex]1[/latex]	[latex]1[/latex]
2	[latex]2[/latex] [latex]4[/latex]	[latex]8[/latex]
3	[latex]511[/latex] [latex]428[/latex]	[latex]218708[/latex]
4	[latex]5555[/latex] [latex]4444[/latex]	[latex]24686420[/latex]
5	[latex]11[/latex] [latex]11[/latex]	[latex]121[/latex]

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

import java.util.Scanner;
 
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();
		System.out.println (a * b);
	}
}

import java.util.Scanner;

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

System.out.println (a * b);

}

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

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.