e-olymp 1290. Номерной знак

28/11/2020 by Таня Осипенко

Задача

Международный номерной регистрационный знак легкового автомобиля состоит из $A$ арабских цифр и $B$ больших букв латинского алфавита. Будем считать, что для обеспечения уникальности номера разрешено использовать любую последовательность букв и цифр.
Сколько существует различных таких номеров?

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

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

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

Единственное число — ответ к задаче.

Тесты

№	Входные данные	Выходные данные
1	3 3	17576000
2	2 5	67600000
3	7 1	80318101760
4	1 1	260
5	26 26	615611958020715731079667428840020377600000000000000000000000000

Код

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

class Main
{
	public static void main (String[] args) 
	{
		Scanner sc = new Scanner(System.in);
        int b = sc.nextInt(); //букв в знаке
        int a = sc.nextInt(); //цифр в знаке
        BigInteger LETTERS = BigInteger.valueOf(26); //кол-во букв в алфавите
        BigInteger let = BigInteger.valueOf(1); 
        for(int i = 0; i < b; i++){
        	let = let.multiply(LETTERS); //возведение 26 в степень b
        }
        System.out.print(let); // вывод результата
        for(int i = 0; i < a; i++){
        	System.out.print(0); //добавление к результату а нулей
        }
	}
}

import java.math.*;

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

Scanner sc = new Scanner(System.in);

int b = sc.nextInt(); //букв в знаке

int a = sc.nextInt(); //цифр в знаке

BigInteger LETTERS = BigInteger.valueOf(26); //кол-во букв в алфавите

BigInteger let = BigInteger.valueOf(1);

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

let = let.multiply(LETTERS); //возведение 26 в степень b

}

System.out.print(let); // вывод результата

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

System.out.print(0); //добавление к результату а нулей

}

Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Числа, возникающие при возведении в степень, слишком велики для типа long, поэтому в коде используется дополнительный тип для больших целочисленных значений из пакета java.math — BigInteger.

Следует также отметить, что домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

Ссылки

Задача на сайте e-olymp
Код решения на ideone

e-olymp 4439. Возведение в степень

17/09/2020 by Владислав Гринькив

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 100	1
2	2 10	1024
3	3 7	2187
4	8 9	134217728
5	10 10	10000000000
6	100 9	1000000000000000000

Код

class Main{
  public static long pow(long a, long b){
    if(b == 0){ 
      return 1; 
    } 
    if(b % 2 == 0){ 
      return pow(a * a, b / 2); 
    } 
    return a * pow(a, b - 1);
  }
  public static void main (String[] args){
    java.util.Scanner in = new java.util.Scanner(System.in);
    long a = in.nextLong(), b = in.nextLong();
    System.out.println(pow(a,b));
  }
}

class Main{

public static long pow(long a, long b){

if(b == 0){

return 1;

}

if(b % 2 == 0){

return pow(a * a, b / 2);

}

return a * pow(a, b - 1);

}

public static void main (String[] args){

java.util.Scanner in = new java.util.Scanner(System.in);

long a = in.nextLong(), b = in.nextLong();

System.out.println(pow(a,b));

}

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

e-olymp 1206. f91

09/09/2020 by Владислав Гринькив

Задача

МакКарти — известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию $f_{91}$, которая определена для всякого натурального числа $n$ следующим образом:

Если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;

Если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.

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

Натуральное число $n$, не большее $1000000$.

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

Значение $f_{91}\left(n\right)$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5	91
2	27	91
3	91	91
4	100	91
5	102	92
6	180	170

Код

class Main{
	public static long func(long n){
		if(n <= 100){
			return 91;
		}
		else {
			return n - 10;
		}
	}
	public static void main (String[] args){
		java.util.Scanner in = new java.util.Scanner(System.in);
		long num = in.nextInt();
		System.out.println(func(num));
	}
}

class Main{

public static long func(long n){

if(n <= 100){

return 91;

}

else {

return n - 10;

}

public static void main (String[] args){

java.util.Scanner in = new java.util.Scanner(System.in);

long num = in.nextInt();

System.out.println(func(num));

}

Решение

Для решения задачи создадим функцию $f_{91}\left(n\right)$ которая в зависимости от значения $n$ будет выдавать нам разные значение, а имеено:
если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;
если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.
Так же, мы можем проследить законномерность того, что если $n\leqslant100$ функция $f_{91}\left(n\right)$ будет выдавть $91$, заметив это можно будет заменить сложную, но при этом красивую рекурсивную функцию на более простое и практичное решение и получить следущие соотношение:
$f_{91}\left(n\right) = \begin{cases} 91, & n\leqslant100;\\\ n-10, & n\geqslant101; \end{cases}$

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

Ю4.8

24/02/2019 by Глеб Брошко

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

В массиве [latex]C(m)[/latex] заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним — полусуммой соседних с ним элементов.

Алгоритм решения

1.Инициализируем переменную [latex]n[/latex], которая будет размером массива и сам массив [latex]a[/latex];
2.С помощью ввода задаем длину массива;
3.С помощью цикла и ввода заполняем массив;
3.Меняем каждый третий элемент начиная со второго;
4.Находим полусумму двух предыдущих элементов;
5.Берем число стоящее перед числом кратным трем;
6.Заменяем его на полусумму стоящих рядом элементов.

Тесты

Кол-во элементов	Элементы	Результат
3	5 9 1	5 3 7
6	8 7 6 9 4 0	8 7 7,5 9 4,5 6,5
9	2 5 7 3 6 9 4 6	2 4,5 3,5 3 6 4,5 4 5,5 5

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;						// Инициализируем переменную n;
		double a[];					// Инициализируем массив a;
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();				//Вводим размер массива;
		a = new double[n];						
		for(int i = 0; i < n ; ++i){
			a[i] = sc.nextInt();			//Вводим элементы массива;
		}
		if(n >= 3){
			for(int i = 2; i < n; i+=3){
				double tmp = a[i - 1];
				a[i - 1] = (a[i] + a[i - 2])/2;	//Находим полусумму двух предыдущих элементов;
				a[i] = (tmp + a[i - 2])/2;	//Заменяем число кратное трем на полусумму стоящих рядом элементов;
			}
			for(int i = 0; i < n ; ++i){
			System.out.println(a[i]);
			}
		}
		sc.close();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n; // Инициализируем переменную n;

double a[]; // Инициализируем массив a;

Scanner sc = new Scanner(System.in);

n = sc.nextInt(); //Вводим размер массива;

a = new double[n];

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

a[i] = sc.nextInt(); //Вводим элементы массива;

}

if(n >= 3){

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

double tmp = a[i - 1];

a[i - 1] = (a[i] + a[i - 2])/2; //Находим полусумму двух предыдущих элементов;

a[i] = (tmp + a[i - 2])/2; //Заменяем число кратное трем на полусумму стоящих рядом элементов;

}

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

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

}

sc.close();

}

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

А701б

24/02/2019 by Глеб Брошко

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

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] c [latex]n[/latex] элементами. Получить вектор \[A^{2} \cdot b\]

Алгоритм решения

Считываем матрицу. Возводим ее в квадрат ( перемножение матрицы осуществляется при помощи циклов). Считываем вектор. Умножаем матрицу на вектор. Выводим ответ.

Фактически, умножение матриц пишется по определению. Сумма произведений элементов строки на элементы столбцов.

Тесты

[latex]n[/latex]	[latex]A[/latex]	[latex]b[/latex]	Результат
3	1 1 1 1 1 1 1 1 1	5 5 5	45 45 45
5	1 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5	8 1 8 1 8	8 4 72 16 200
2	1 0 0 1	2 2	2 2

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		double matr1[][];
		double matr2[][];
		double vet1[];
		double vet2[];
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		matr1 = new double[n][n];  //Матрица А 
		matr2 = new double[n][n]; // Матрица А^2
		vet1 = new double[n];  //Вектор данный по условию (вектор b)
		vet2 = new double[n];  //Конечный вектор
 
		for(int i = 0;i < n;i++){
			for(int j = 0; j < n; j++) // Инициализация матрицы А
				matr1[i][j] = sc.nextInt();
		}
 
		for(int i = 0; i < n;i++){
			for(int j = 0;j < n;j++){  //Возведение матрицы А в квадрат
				matr2[i][j] = 0;
				for(int p = 0;p < n;p++)
					matr2[i][j] += (matr1[i][p]*matr1[p][j]);
			}
		}
 
		for(int i = 0; i < n; i++)                //Инициализация вектора
			v
			et1[i] = sc.nextInt();
 
		for(int i = 0;i < n;i++){
			vet2[i] = 0;
			for(int j=0; j<n; j++){
				vet2[i] += matr2[i][j]*vet1[j]; //Умножение матрицы на вектор
			}
		}
 
		for(int i = 0; i < n; i++)
			System.out.println(vet2[i]);       //Вывод вектора
 
		sc.close();
 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n;

double matr1[][];

double matr2[][];

double vet1[];

double vet2[];

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

matr1 = new double[n][n]; //Матрица А

matr2 = new double[n][n]; // Матрица А^2

vet1 = new double[n]; //Вектор данный по условию (вектор b)

vet2 = new double[n]; //Конечный вектор

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

for(int j = 0; j < n; j++) // Инициализация матрицы А

matr1[i][j] = sc.nextInt();

}

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

for(int j = 0;j < n;j++){ //Возведение матрицы А в квадрат

matr2[i][j] = 0;

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

matr2[i][j] += (matr1[i][p]*matr1[p][j]);

}

for(int i = 0; i < n; i++) //Инициализация вектора

et1[i] = sc.nextInt();

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

vet2[i] = 0;

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

vet2[i] += matr2[i][j]*vet1[j]; //Умножение матрицы на вектор

}

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

System.out.println(vet2[i]); //Вывод вектора

sc.close();

}

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

Ю1.19

24/02/2019 by Глеб Брошко

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

Найти координаты вершины параболы \[y = ax^{2}+bx+c\]

Алгоритм решения

Мы знаем координаты вершины параболы вычисляются по формулам:

1) \[x_{0} = — \frac{b}{2 \cdot a}\] 2) \[y_{0} = ax_{0}^{2}+bx_{0}+c\]

(Для простоты в программе [latex]x_{0}[/latex] и [latex]y_{0}[/latex] заменены на [latex]x[/latex] и [latex]y[/latex] соответственно).

Теперь учтем ситуации в проработке которых могут возникнуть сложности:
Если [latex]a=0[/latex], то график [latex]y(x)[/latex] не является параболой, о чем на должен проинформировать компилятор. Это все проблемы связанные с графиком.

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

Тесты

№	[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]x[/latex]	[latex]y[/latex]	Комментарий
-1	-2	-3	1	-4	Пройден
0	2	2	—	—	Не пройден так график [latex]y(x)[/latex] не является параболой и программа оповещает об ошибке
1	0	4	0	4	Пройден
2	1	3	-0.25	2.875	Пройден

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double a, b, c, x, y;
		double h;
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		x = b/(2*a);    	// находим первую координату вершины параболы и нам остаётся только умножить результат на -1
 
		if( a != 0 ){			// "только если уравнение задает на графике параболу..."
			if(x!=0) x*=-1; 	// в типе double  0 -- иногда получает свойства числа со знаком, поэтому дабы при b == 0 мы не получили  x == -0 нам нужно умножить x на (-1) только если x != 0
		}
		else{					// если а == 0, то график y(x) не является параболой ==> выводим на экран "Error" и закрываем программу
			 System.out.println("Error");
			 sc.close();
		} 
 
	    	y = a*x*x + b*x + c;    // находим вторую координату вершины параболы
	    	System.out.println(x);
		System.out.println(y);
		sc.close();
 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double a, b, c, x, y;

double h;

Scanner sc = new Scanner(System.in);

a = sc.nextInt();

b = sc.nextInt();

c = sc.nextInt();

x = b/(2*a); // находим первую координату вершины параболы и нам остаётся только умножить результат на -1

if( a != 0 ){ // "только если уравнение задает на графике параболу..."

if(x!=0) x*=-1; // в типе double 0 -- иногда получает свойства числа со знаком, поэтому дабы при b == 0 мы не получили x == -0 нам нужно умножить x на (-1) только если x != 0

}

else{ // если а == 0, то график y(x) не является параболой ==> выводим на экран "Error" и закрываем программу

System.out.println("Error");

sc.close();

}

y = a*x*x + b*x + c; // находим вторую координату вершины параболы

System.out.println(x);

System.out.println(y);

sc.close();

}

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

ML11

24/02/2019 by Глеб Брошко

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

Определить время падения камня на поверхность земли с высоты [latex]h[/latex].

Алгоритм решения

Для начала оговорим трактовку условия задачи.

1. Поскольку в условии ничего не говорится про начальную скорость камня, будем считать ее равной нулю.
2. Аналогично в условии ничего не говорится про точность результата. От этого зависит как округление до определенного количества знаков после запятой в выводе, так и то, с какой точностью следует указать ускорение свободного падения, поскольку каноны физики требуют, чтобы ответ на физическую задачу указывался с точностью наимение точно указанного в условии данного. В данном решении я взял значение [latex]g[/latex] свойственное Одессе с точностью 4 значка после запятой. Соответственно, ответ будет выводиться с такой же точностью.
3. Предполагается что высота и время должны указываться в СИ

Тогда наша рабочая формула выглядит следующим образом: \[\sqrt{\frac{2 \cdot h}{g}},\] где \[g = 9.8075 \frac{m}{s^{2}}\] Вводить в программе [latex]g[/latex], как отдельную переменную или константу нет смысла, т.к. она используется только раз. Поэтому в коде вместо [latex]g[/latex] стоит просто ее значение.

Тесты

№	Высота (м)	Время (сек)
1	0	0
2	5	1.0098
3	20	2.0195
4	80	4.0391

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double h;
		Scanner sc = new Scanner(System.in);
    		h = sc.nextInt();
    		double p = Math.sqrt(2*h/9.8075);
    		System.out.printf("%.4f", p);
		sc.close();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double h;

Scanner sc = new Scanner(System.in);

h = sc.nextInt();

double p = Math.sqrt(2*h/9.8075);

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

sc.close();

}

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

e-olymp 419. Задача 3n + 1

19/02/2019 by Александра Филистович

Задача

Рассмотрим следующий алгоритм генерации последовательности чисел:

input n
print n
if n = 1 then STOP
if n is odd then n = 3 * n + 1
else n = n / 2
GOTO 2

input n

print n

if n = 1 then STOP

if n is odd then n = 3 * n + 1

else n = n / 2

GOTO 2

Например, для [latex]n = 22[/latex] будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n = 1[/latex] для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых [latex]0 < n < 1,000,000[/latex].
Длиной цикла числа [latex]n[/latex] будем называть количество сгенерированных чисел в последовательности включая [latex]1[/latex]. В приведенном примере длина цикла числа [latex]22[/latex] равна [latex]16[/latex].
Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.

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

Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше [latex]1000000[/latex] и больше [latex]0[/latex]. Считайте, что для вычислений достаточно использовать [latex]32[/latex] битный целочисленный тип.

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

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

Тесты

Входные данные	Выходные данные
1 10 100 200 201 210 900 1000	1 10 20 100 200 125 201 210 89 900 1000 174
1 10 10 1	1 10 20 10 1 20
5 25 70 54 38 250	5 25 24 70 54 113 38 250 128

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

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int i, j, ait;
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()) {
			i = scan.nextInt();
			j = scan.nextInt();
			int it, maxIt;
			maxIt = 0;
			for (int a = min(i, j); a <= max(i, j); a++) {
				it = 1;
				ait = a;
				while(ait != 1){
					if(ait % 2 == 1){
						ait = ait * 3 + 1;
					}
					else{
						ait = ait / 2;
					}
					it++;
				}
				if (it > maxIt) {
					maxIt = it;
				}
			}
			System.out.println(i + " " + j + " " + maxIt);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import static java.lang.Math.*;

class Main

{

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

{

int i, j, ait;

Scanner scan = new Scanner(System.in);

while(scan.hasNext()) {

i = scan.nextInt();

j = scan.nextInt();

int it, maxIt;

maxIt = 0;

for (int a = min(i, j); a <= max(i, j); a++) {

it = 1;

ait = a;

while(ait != 1){

if(ait % 2 == 1){

ait = ait * 3 + 1;

}

else{

ait = ait / 2;

}

it++;

}

if (it > maxIt) {

maxIt = it;

}

System.out.println(i + " " + j + " " + maxIt);

}

Решение

Алгоритм, описанный в условии задачи используется для построения сиракузской последовательности. Интересный факт — какое бы число не взять, в конце получаем единицу. Нам же надо посчитать сколько раз должен сработать алгоритм для подсчитывания «длины цикла». Считывая пару чисел из потока ввода я высчитывал «длину цикла» для каждого числа из заданного введенной парой промежутка. После чего сравнивал количество итераций для каждого такого числа и находил максимальное. И так для каждой пары чисел.

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp 1780. Коды Грея

30/01/2019 by Александра Филистович

Задача

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.

Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».

Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].

0
1

Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].

00
01
11
10

Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:

000
001
011
010
110
111
101
100

При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2^n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.

Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k (0 < k < 10^{18})[/latex] в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

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

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

№	Входные данные	Выходные данные
1	3 14 5 12	2 9 7 10
2	10 50	15 43

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static void main (String[] args) throws java.lang.Exception
	{
		String s;
		while ((s = in.readLine()) != null) {
			long k = Long.parseLong(s);
			System.out.println(k ^ (k >> 1));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

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

{

String s;

while ((s = in.readLine()) != null) {

long k = Long.parseLong(s);

System.out.println(k ^ (k >> 1));

}

Решение

Рассмотрим биты числа [latex]n[/latex] и биты числа [latex]G(n)[/latex]. Заметим, что [latex]i[/latex]-ый бит [latex]G(n)[/latex] равен единице только в том случае, когда [latex]i[/latex]-ый бит [latex]n[/latex] равен единице, а [latex]i+1[/latex]-ый бит равен нулю, или наоборот ([latex]i[/latex]-ый бит равен нулю, а [latex]i+1[/latex]-ый равен единице). Таким образом, имеем: [latex]G(n) = n \oplus (n>>1)[/latex], где [latex]\oplus[/latex] — операция «побитовое исключающее ИЛИ», а [latex]>>[/latex] — «побитовый сдвиг вправо».

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp 143. Точка и треугольник

27/12/2018 by Александра Филистович

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

№	Входные данные	Выходные данные
1	2 6 -9 3 8 1 5 11	1
2	-13 10 -12 5 99 80 17 13	0
3	98 -50 -87 7 5 3 23 17	0
4	5 15 7 12 5 3 2 54	1
5	2 2 3 1 1 3 9 11	1

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

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 x0 = scan.nextDouble();
		double y0 = scan.nextDouble();
		double x1 = scan.nextDouble();
		double y1 = scan.nextDouble();
		double x2 = scan.nextDouble();
		double y2 = scan.nextDouble();
		double x3 = scan.nextDouble();
		double y3 = scan.nextDouble();
		double z1,z2,z3;
		z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);
		z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);
		z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);
		if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) System.out.println("1");
		else System.out.println("0");
	}
}

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 x0 = scan.nextDouble();

double y0 = scan.nextDouble();

double x1 = scan.nextDouble();

double y1 = scan.nextDouble();

double x2 = scan.nextDouble();

double y2 = scan.nextDouble();

double x3 = scan.nextDouble();

double y3 = scan.nextDouble();

double z1,z2,z3;

z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);

z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);

z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);

if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) System.out.println("1");

else System.out.println("0");

}

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

Ссылки

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