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

03/01/2019 by Кирилл Бондаренко

Задача. Проверка на неориенитрованность

Условие задачи
По заданной квадратной матрице $n\times n$ из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

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

Входной файл содержит число $n(1\leq n\leq 100)$ — размер матрицы, и затем $n$ строк по $n$ чисел, каждое из которых равно $0$ или $1$ — саму матрицу.

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

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
3 0 1 1 1 0 1 1 1 0	YES
3 0 1 0 1 0 1 1 1 0	NO
3 0 1 0 1 1 1 0 1 0	NO
4 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1	NO

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = n*n;
		int [] G = new int [k];
		for (int i = 0; i < G.length; i++) {
			G[i] = in.nextInt();
		}
		int j = 0, c = 0, s = 0;
		boolean f = true;
		for (int i = 0; i < k; i++) {
			if (G[i] != G[j]) {
				f=false;
				break;
			}
			if (c == n - 1) {
				c = 0;
				s++;
				j = s;
			} else {
				j = j + n;
				c++;
			}
		}
		for (int i = 0; i < k; i = i + n + 1) {
			if (G[i] != 0) {
				f = false;
				break;
			}
		}
		if (f) System.out.print("YES"); else System.out.print("NO");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main {

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

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = n*n;

int [] G = new int [k];

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

G[i] = in.nextInt();

}

int j = 0, c = 0, s = 0;

boolean f = true;

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

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

f=false;

break;

}

if (c == n - 1) {

c = 0;

s++;

j = s;

} else {

j = j + n;

c++;

}

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

if (G[i] != 0) {

f = false;

break;

}

if (f) System.out.print("YES"); else System.out.print("NO");

}

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

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

e-olymp 441. Наиболее круглое число

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

Наиболее круглое число

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

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

В первой строке входных данных задано количество чисел $N$ $(1 ≤ N ≤ 100)$. Каждая из последующих $N$ строк содержит одно число в пределах от $1$ до $10^{9}$.

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

Вывести наиболее круглое число среди заданных $N$ чисел.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
4 71200 10 200 10001	200
5 711 1 2 10001 234567	1
10 7 1 2 1 2 3 4 6 8 9	1
4 100000 200000 500000 800000	100000

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;
		Scanner in = new Scanner(System.in);
		e = in.nextInt();
		while (e -- > 0) {
        	n = in.nextInt();
			if (p <= n){
				m = n;
				k = 0;
				while ((n % 10) == 0) {
					//считает нули
					n = n / 10;
					k ++;
				}
				if (maxk < k) {
					maxn = m;
					maxk = k;
					p = 1;
					for (int i = 1; i < maxk; i ++) {
						p *= 10;
					}
				} else if (maxk == k) {
					if(maxn > m) maxn = m;
				}
			}
		}
		System.out.print(maxn);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main

{

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

{

int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;

Scanner in = new Scanner(System.in);

e = in.nextInt();

while (e -- > 0) {

n = in.nextInt();

if (p <= n){

m = n;

k = 0;

while ((n % 10) == 0) {

//считает нули

n = n / 10;

k ++;

}

if (maxk < k) {

maxn = m;

maxk = k;

p = 1;

for (int i = 1; i < maxk; i ++) {

p *= 10;

}

} else if (maxk == k) {

if(maxn > m) maxn = m;

}

System.out.print(maxn);

}

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

Имеет смысл проверять каждое введенное число: не является ли оно меньше либо равно чем $p$, где $p$ — наименьшее число с количеством нулей равным $maxk$. $maxk$ — текущее наибольшее количество нулей. Для того, чтобы найти $p$, мы в цикле умножаем $1 maxk$-раз на $10$. Очевидно, что $p$ нужно менять только тогда, когда меняется $maxk$, также следует до цикла полагать $p = 1$. Для того чтобы $p$ не умножалось на $10$ лишнее количество раз. Таким образом мы отсеиваем заведомо негодные числа и ускоряем код.
Положим $maxn$ — наиболее круглое число.
Так как по условию числа не могут быть больше чем $10^{9}$, имеет смысл изначально поставить переменную $maxn = 10^{9}$. Это делается для того случая, когда во всех числах $m$ не будет нулей и нужно будет выбрать наименьшее. Если мы положим в переменную $maxn$ любое другое число то $maxn$ может быть меньше чем $m$ и мы не сможем выбрать ответ так как все $m$ будут больше его.

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

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

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

Единицы

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

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

Одно целое число $n$ $(0 ≤ n ≤ 2 \cdot 10^{9})$.

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

Вывести количество единиц в двоичной записи числа $n$.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
20	2
0	0
1	1
5	2
2000000000	13

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int k=0, n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		while (n > 0){   
			k += (n % 2);
			n = n / 2;
		}
		System.out.print(k);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main

{

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

{

int k=0, n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

while (n > 0){

k += (n % 2);

n = n / 2;

}

System.out.print(k);

}

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

Алгоритм заключается в последовательном делении заданного числа $n$ на $2$ и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц $k$ равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас $k$. Если остаток равен единице то мы получим $k+1$ что нам и требуется.

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

e-olymp 1610. Зайцы в клетках

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

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

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

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

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

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

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

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

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

Тесты

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

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

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main

{

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

{

int n, m;

double k;

Scanner in = new Scanner(System.in);

n = in.nextInt();

m = in.nextInt();

k = m / n;

if (k >= 1){

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

System.out.print(k1);

}

else System.out.print(1);

}

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

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

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

e-olimp 57. Бабочка-санитар

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

Задача

e-olimp 57. Бабочка-санитар

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.
Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами $X_{1}$ $Y_{2}$, бабочка перелетала в точку с координатами $X_{2}$, $Y_{2}$, $Z_{2}$, расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.
Какую оптическую силу $D$ имели крылышки-линзы бабочки в этот момент?

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

В первой строке 2 числа: координаты $X_{1}$, $Y_{1}$ обертки от конфетки. Во второй – 3 числа: координаты $X_{2}$, $Y_{2}$, $Z_{2}$ бабочки в момент сжигания обертки.
Все входные данные целые числа, не превышающие по модулю 1000.

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

Единственное число – оптическая сила крылышек-линз D, вычисленная с точностью до 3-х знаков после запятой за правилами математических округлений.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
10 20 10 20 100	0.010
600 400 300 867 409	0.001
30 50 1000 1000 1000	0.001
60 21 11 44 -7	0.018

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double x1, y1, z1, x, y, S;
		Scanner in = new Scanner(System.in);
		x = in.nextInt();
		y = in.nextInt();
		x1 = in.nextInt();
		y1 = in.nextInt();
		z1 = in.nextInt();
		S = Math.sqrt((x1 - x)*(x1 - x) + (y1-y)*(y1-y) + z1*z1);
		System.out.printf("%.3f", 1/S);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main

{

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

{

double x1, y1, z1, x, y, S;

Scanner in = new Scanner(System.in);

x = in.nextInt();

y = in.nextInt();

x1 = in.nextInt();

y1 = in.nextInt();

z1 = in.nextInt();

S = Math.sqrt((x1 - x)*(x1 - x) + (y1-y)*(y1-y) + z1*z1);

System.out.printf("%.3f", 1/S);

}

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

$F=\sqrt{(x-x_{1})^{2} + (y-y_{1})^{2} + z^{2}}$ — формула для нахождения расстояния между двумя точками пространства. По этой формуле находим фокусное расстояние между крыльями-линзами и бумажкой. Оптическая сила линзы $\frac{1}{F}$, где $F$ — фокусное расстояние.

System.out.printf("%.3f", 1/S);

18	System.out.printf("%.3f", 1/S);

Этой строкой кода мы выводим оптическую силу линзы с точностью до трех знаков после запятой.
Условие задачи на e-olimp
Код решения ideon

java@Cat

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

Author Archives: Кирилл Бондаренко

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

Задача. Проверка на неориенитрованность

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

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

Тесты

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

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

e-olymp 441. Наиболее круглое число

Наиболее круглое число

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

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

Тесты

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

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

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

Единицы

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

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

Тесты

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

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

e-olymp 1610. Зайцы в клетках

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

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

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

Тесты

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

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

e-olimp 57. Бабочка-санитар

Задача

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

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

Тесты

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

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