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 130. Прямоугольник

04/10/2018 by Костя Григорян

Задача

Заданы координаты трёх вершин прямоугольника. Найдите координаты четвертой вершины.

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

В единственной строке записано шесть чисел — координаты трёх точек.

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

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

Тесты

Входные данные	Выходные данные
[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]1[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]2[/latex] [latex]0[/latex]
[latex]1\, 4\, 4\, 0\, 0\, 2[/latex]	[latex]5\, 2[/latex]
[latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]-100[/latex]	[latex]-100[/latex] [latex]100[/latex]
[latex]2[/latex] [latex]-1[/latex] [latex]3[/latex] [latex]1[/latex] [latex]-2[/latex] [latex]1[/latex]	[latex]-1[/latex] [latex]3[/latex]
[latex]8\, 0\, 1\, 6\, 0\, 4[/latex]	[latex]9\, 2[/latex]

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

import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int x1 = scanner.nextInt();
		int y1 = scanner.nextInt();
		int x2 = scanner.nextInt();
		int y2 = scanner.nextInt();
		int x3 = scanner.nextInt();
		int y3 = scanner.nextInt();
		if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0) {
			System.out.println((x2+x3-x1)+" "+(y2+y3-y1));
		}
		else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0) {
			System.out.println((x1+x3-x2)+" "+(y1+y3-y2));
		}
		else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0) {
			System.out.println((x1+x2-x3)+" "+(y1+y2-y3));
		}   
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int x1 = scanner.nextInt();

int y1 = scanner.nextInt();

int x2 = scanner.nextInt();

int y2 = scanner.nextInt();

int x3 = scanner.nextInt();

int y3 = scanner.nextInt();

if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0) {

System.out.println((x2+x3-x1)+" "+(y2+y3-y1));

}

else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0) {

System.out.println((x1+x3-x2)+" "+(y1+y3-y2));

}

else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0) {

System.out.println((x1+x2-x3)+" "+(y1+y2-y3));

}

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

Прямоугольник

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [latex]x_4=x_1+x_3-x_2[/latex] и [latex]y_4=y_1+y_3-y_2[/latex]. Но мы не знаем какая из входных вершин противоположна четвертой, а какие — прилежащие. Так как наша фигура это прямоугольник, то противоположная вершина будет при угле [latex]90^{\circ}[/latex]. Произведение перпендикулярных векторов дает [latex]0[/latex]. Перебрав три варианта произведения векторов, заданных входными вершинами, находим вершину при угле [latex]90^{\circ}[/latex]. Остальные две, соответственно, будут прилежащими. Находим координаты четвертой вершины по формуле, заданной выше.

Ссылки

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

e-olymp 19. The degree of symmetry

07/07/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

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

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

Одно натуральное число [latex]n < 2\cdot10^9.[/latex]

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

Вывести степень симметрии числа [latex]n[/latex].

Тесты:

Ввод	Вывод
123322	2
100	1
1010	0
1234321	4
1234567891	1

Код на Java:

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

class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int i = 0;
		int j = 0;
		int num[] = new int[10];
		if (n == 0) {
			num[0] = 0;
		} else {
			while (n > 0) {
				num[j] = n % 10;
				n /= 10;
				j++;
			}
			j--;
		}
		int count = 0;
		while (i <= j) {
			if (num[i] == num[j]) count++;
			i++;
			j--;
		}
		System.out.print(count);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

int i = 0;

int j = 0;

int num[] = new int[10];

if (n == 0) {

num[0] = 0;

} else {

while (n > 0) {

num[j] = n % 10;

n /= 10;

j++;

}

j--;

}

int count = 0;

while (i <= j) {

if (num[i] == num[j]) count++;

i++;

j--;

}

System.out.print(count);

}

Алгоритм:

Вначале считываем число. Затем раскладываем его по цифрам внутри массива (в обратном порядке, но для нашей задачи порядок цифр значения не имеет):

if (n == 0) {
	num[0] = 0;
} else {
	while (n > 0) {
		num[j] = n % 10;
		n /= 10;
		j++;
	}
	j--;
}

if (n == 0) {

num[0] = 0;

} else {

while (n > 0) {

num[j] = n % 10;

n /= 10;

j++;

}

j--;

}

Затем подсчитываем собственно степень симметрии, двигаясь внутри массива от крайних цифр к центру, а после выводим результат:

int count = 0;
while (i <= j) {
	if (num[i] == num[j]) count++;
	i++;
	j--;
}
System.out.print(count);

int count = 0;

while (i <= j) {

if (num[i] == num[j]) count++;

i++;

j--;

}

System.out.print(count);

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

java@Cat

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

Tag Archives: симметрия

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

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 130. Прямоугольник

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 19. The degree of symmetry

Условие

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

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

Тесты:

Код на Java:

Алгоритм:

Ссылки: