e-olymp 2814. Быстрое возведение в степень

31/03/2019 by Никита Пушкин

Задача

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $x$ и $n$, где $n$ — положительное целое число.
Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.
Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

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

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

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

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

#	Входные данные	Выходные данные
1	23	SSXSXSX
2	1
3	16	SSSS
4	1000000	SXSXSXSSXSSSSSXSSSXSSSSSS
5	2018	SXSXSXSXSXSSSSXS

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long n, k = 0, c = 0;
		Scanner S = new Scanner (System.in);
		n = S.nextLong();
		while (n > 1){
			long bit = n & 1;
			n >>= 1;
			k <<= 1;
			k |= bit;
			c += 1;
		}
		while (c != 0) {
			long bit = k & 1;
			k >>= 1;
			if (bit == 0) System.out.print("S");
			else System.out.print("SX");
			c -= 1;
		}
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long n, k = 0, c = 0;

Scanner S = new Scanner (System.in);

n = S.nextLong();

while (n > 1){

long bit = n & 1;

n >>= 1;

k <<= 1;

k |= bit;

c += 1;

}

while (c != 0) {

long bit = k & 1;

k >>= 1;

if (bit == 0) System.out.print("S");

else System.out.print("SX");

c -= 1;

}

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

Условие задачи можно найти на 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 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 1078. Степень строки

04/07/2017 by Хоба Юрий

Постановка задачи

Обозначим через [latex]a\cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a=[/latex] «abc» и [latex]b=[/latex] «def», то [latex]a\cdot b=[/latex] «abcdef».
Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

[latex]a^{0}=[/latex] «» (пустая строка)
[latex]a^{n+1}=a\cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

№	Входные данные	Выходные данные
1	abcabcabc	3
2	aaaaaaaaaa	10
3	ollollo	1
4	pjpjpjpj	4

Посмотреть работу программы на примере приведенных выше тестов можно на сайте ideone.

Решение

import java.util.*;

class task6 
{
	static public int StringPow(final String str)
	{
		int size = str.length();
		int pow = 1;
		for (int i=1; i<=size/2; i++)
		{
			if (size % i != 0)
				continue;
			String sub1 = new String(str.substring(0, i));
			boolean found = true;
			for (int j = i; j < size; j+=i)
			{
				String sub2 = new String(str.substring(j, j+i));
				if (!sub1.equals(sub2))
				{
					found = false;
					break;
				}
			}
			if (found)
			{
				pow = (size/i);
				break;
			}
		}
		return pow;
	}
	
	static public void main (String[] argv)
	{
		String str;
		Scanner in = new Scanner(System.in);
		while (in.hasNext())
		{
			str = in.nextLine();
			System.out.println(StringPow(str));
		}
		in.close();
	}
}

import java.util.*;

class task6

{

static public int StringPow(final String str)

{

int size = str.length();

int pow = 1;

for (int i=1; i<=size/2; i++)

{

if (size % i != 0)

continue;

String sub1 = new String(str.substring(0, i));

boolean found = true;

for (int j = i; j < size; j+=i)

{

String sub2 = new String(str.substring(j, j+i));

if (!sub1.equals(sub2))

{

found = false;

break;

}

if (found)

{

pow = (size/i);

break;

}

return pow;

}

static public void main (String[] argv)

{

String str;

Scanner in = new Scanner(System.in);

while (in.hasNext())

{

str = in.nextLine();

System.out.println(StringPow(str));

}

in.close();

}

Описание решения

Получая строку str из потока ввода, вызываем функцию static public int StringPow(final String str) и передаем полученную строку в качестве входного параметра. Функция StringPow возвращает значение типа int — наибольшую степень строки, которую программа и передаст в поток вывода в качестве выходных данных.

Минимальной степенью строки может быть число [latex]1[/latex] — в том случае, если в заданной строке [latex]s[/latex] нет повторяющихся подстрок. Максимальной же степенью строки может быть количество символов, из которых строка состоит — в том случае, если строка состоит из одного повторяющегося символа. В этом случае этот символ и будет считаться повторяющейся подстрокой.

Получив в качестве входного аргумента строку str, предположим внутри тела функции StringPow, что степень данной строки равна [latex]1[/latex] ( int pow = 1;) на тот случай, если бо́льшую степень найти не удастся.

Так как нужно найти число повторений подстроки минимального размера в строке str, будем проверять все подстроки размером от [latex]1[/latex] символа до size/2, где size — длина строки. Строка не может состоять из повторяющейся подстроки размером меньше [latex]1[/latex] или больше половины строки. Отсюда цикл for (int i=1; i<=size/2; i++).

Сразу будем отсеивать подстроки, из повторений которых строка не может состоять из-за несоответствия количества символов строки и подстроки ( if (size % i != 0) continue;). К примеру, строка длиной [latex]8[/latex] символов не может состоять из повторений подстроки длиной [latex]3[/latex] символа.

Запоминаем эту подстроку String sub1 = new String(str.substring(0, i));, а затем будем сравнивать с каждой следующей подстрокой такого же размера String sub2 = new String(str.substring(j, j+i)); во внутреннем цикле, предполагая перед этим, что мы нашли нужную нам подстроку ( boolean found = true;); если сверяемые подстроки различаются ( if (!sub1.equals(sub2))) — значит рассматриваемая подстрока sub1 искомой подстрокой не является. Прерываем действие внутреннего цикла и переходим к следующей подстроке, длиной на 1 символ больше. Если же строка полностью состоит из подстроки sub1 находим степень строки — число повторений подстроки в строке, иначе говоря, делим размер строки на размер подстроки ( pow = (size/i);).

Посмотреть решение задания можно на сайте e-olymp.

java@Cat

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

Tag Archives: степень

e-olymp 2814. Быстрое возведение в степень

Задача

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

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

Тесты

Решение

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

Задача

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

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

Тесты

Код задачи

Решение

Ссылки

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

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 1078. Степень строки

Постановка задачи

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

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

Тесты

Решение

Описание решения