Category Archives: 3. Циклические вычисления

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

Задачи

Найдите сумму цифр в десятичной записи целого числа
Найдите сумму цифр в десятичной записи целого числа, хранящегося при помощи класса java.math.BigInteger
Напишите функцию получения записи заданного числа в сбалансированной троичной системе счисления. (На вход поступает целое значение, на выходе — строка текста.)
Напишите функцию вычисления синуса при помощи разложения в ряд Тейлора и формул приведения. Точность вычисления должна быть максимально возможной для типа данных double.
Напишите функцию вычисления косинуса при помощи разложения в ряд Тейлора и формул приведения. Точность вычисления должна быть максимально возможной для типа данных double.
Напишите функцию вычисления тангенса при помощи разложения в ряд Тейлора и формул приведения. Точность вычисления должна быть максимально возможной для типа данных double.
Напишите функцию вычисления логарифма по натуральному основанию при помощи разложения в ряд Тейлора. Точность вычисления должна быть максимально возможной для типа данных double.

Более сложные задачи

Напишите функцию с тремя целочисленными параметрами [latex]n, m, k[/latex] для вычисления [latex]n^m \mod k[/latex]. Т.е. для вычисления остатка от деления на [latex]k[/latex] числа [latex]n[/latex] в степени [latex]m[/latex]. Постарайтесь сделать алгоритм быстрым.
Составить программу, выводящую на печать первые [latex]n[/latex] знаков числа [latex]\pi[/latex]. Число знаков может быть. Количество знаков задаётся переменной целого типа.
Для заданного натурального [latex]n[/latex] выведите последовательность чисел в которой нулевой элемент показывает сколько раз встретилось в этой же последовательности число ноль. Первый элемент — сколько раз встретилась единица. Второй — двойка и т.д. до [latex]n[/latex]. Обработайте ситуацию, когда такой последовательности нет.

e-olymp 8946. Шаблон

09/09/2020 by Алина Зозуля

Условие

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

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

Одно натуральное число $n$.

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

Вывести изображение $n \times n$.

Тесты

№

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

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

* 
 *

* *

 *

* *

* *

* *

 * *

* *

* *

* * *

 * *

* * *

 * *

* * *

* * *

* *

* * *

* *

* * *

* * *

 * * *

* * *

 * * *

* * *

 * * *

* * *

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long n;
    	String s1 = "", s2 = "";
    	Scanner myObj = new Scanner(System.in);
    	n = myObj.nextLong();

    	for (int i = 0; i < n; i++){//заполняем строки 
	        if (i % 2 == 0){
	            s1 += "*";
	            s2 += " ";
	        }
	        else {
	            s2 += "*";
	            s1 += " ";
	        }
	    }
	    for (int i = 0; i < n; i++){
	        if (i % 2 == 0){//выводим s1, если строка имеет четный номер
	           System.out.println(s1);
	        }
	        else System.out.println(s2);//выводим s2, если строка имеет нечетный номер
	    }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

long n;

String s1 = "", s2 = "";

Scanner myObj = new Scanner(System.in);

n = myObj.nextLong();

for (int i = 0; i < n; i++){//заполняем строки

if (i % 2 == 0){

s1 += "*";

s2 += " ";

}

else {

s2 += "*";

s1 += " ";

}

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

if (i % 2 == 0){//выводим s1, если строка имеет четный номер

System.out.println(s1);

}

else System.out.println(s2);//выводим s2, если строка имеет нечетный номер

}

Решение

Для того, чтобы вывести изображение как на рисунке достаточно заметить, что выводятся строки только двух видов и то поочерёдно. Первый вид — первым символом строки является $\ast$ и затем чередуется $\ast$ и пробел. Второй вид — первым символом строки является пробелом и затем чередуется $\ast$ и пробел. Мы заполняем две строки, по одной каждого вида. Нам остается только выводить строку необходимого нам вида, сделаем это в цикле.

Ссылки

Условие задачи на e-olymp

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

e-olymp 3873. Счастливый номер

09/09/2020 by Валентин Цушко

Условие

Подавляющее большинство людей стараются найти закономерности, которые приносят удачу! Зуб акулы в ухе папуаса — к удачной рыбной ловле. Черная кошка, которая передумала перебегать вам дорогу — к отмене контрольной. Любимая игрушка у компьютера — к удаче в командном чемпионате по программированию.

Для большинства студентов несомненным является тот факт, что номер трамвайного билетика приносит удачу. А уж если такой билетик достался перед экзаменом, пятерка обеспечена! Главное тут — четко понимать, что такое счастливый билет. И почему, спрашивается, многие считают, что только номер автобусного или троллейбусного билета может приносить удачу своему владельцу?! Чем хуже, скажем, номер паспорта или номер кассового чека в гастрономе? Главное, чтобы номер был счастливым!

Витька всегда считал, что удачу приносят такие номера, в записи которых цифры идут в неубывающем порядке. Например, счастливыми являются номера $11111$ или $12345$. Даже номер $00000$ — тоже счастливый!

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

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

Входной файл содержит единственное целое число $N$, $(1 \leq N \leq 64)$, $N$ — длина числа, для которой нужно вычислить количество счастливых номеров.

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

Вывести одно число — количество счастливых номеров.

Тесты

№	Входные данные	Выходные данные
1	2	55
2	4	715
3	3	220

Программный код

public class Main
{
    public static long factorial(int n){
        long a = 1;
        for (int i = (n + 9); i > n; i--) a = a * i;  // мы сократили, чтобы не пришлось делить огромные числа
        return a;
    }
	public static void main(String[] args) {
		

        java.util.Scanner in = new java.util.Scanner(System.in);
        
        int n;
        n = in.nextInt();
        long fact = 1;
        for (int i = 2; i <= 9; i++) fact = fact * i;
        System.out.print(factorial(n) / fact);
	}
}

public class Main

{

public static long factorial(int n){

long a = 1;

for (int i = (n + 9); i > n; i--) a = a * i; // мы сократили, чтобы не пришлось делить огромные числа

return a;

}

public static void main(String[] args) {

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

int n;

n = in.nextInt();

long fact = 1;

for (int i = 2; i <= 9; i++) fact = fact * i;

System.out.print(factorial(n) / fact);

}

Решение

Для того, чтобы решить эту задачу, я начертил таблички (рис. 1.1) для всех вариантов $2$ значного числа и $1$ значного (рис. 1.2). Для $3$ значного аналогично, только рядов будет $3$. Из комбинаторики мы помним формулу: $C_n^m=\frac{n!}{m!(n-m)!}$, из которой мы получим: $(n + 9)! \over {9! \times n!}$. Потому-что из картинки мы видим что при 1 значном числе количество вариантов равно $10$. В коде я сразу сокращал на $n!$, чтобы не получались огромные числа.

рис 1.1

рис 1.2

Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

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 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 338. Моя любимая, несократимая…

28/12/2018 by Андрей Святозар Чернецкий

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

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

Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).

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

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

Тесты

Входные данные	Выходные данные
1	0
10000	30397485
5	9
80	1965
37	431
5168	8119803
9973	30237929

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

import java.util.Scanner;
 
public class Main {
	public static int eulerf(int n) {
		int result = n;
		for (int i = 2; i * i <= n; ++i) {
    	    if (n % i == 0) {
    	        while (n % i == 0) n /= i; 
    	        result -= result / i; 
    	    } 
    	}
    	if (n > 1) result -= result / n; 
    	return result; 
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		n = sc.nextInt();
		int sum = 0;
    	for (int i = 2; i <= n; ++i) {
        	sum += eulerf(i);
    	}
    	System.out.print(sum);
	}
}

import java.util.Scanner;

public class Main {

public static int eulerf(int n) {

int result = n;

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

if (n % i == 0) {

while (n % i == 0) n /= i;

result -= result / i;

}

if (n > 1) result -= result / n;

return result;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n;

n = sc.nextInt();

int sum = 0;

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

sum += eulerf(i);

}

System.out.print(sum);

}

Решение

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

описание функции Эйлера на Wikipedia

e-olymp 1327. Ладьи на шахматной доске

27/12/2018 by Ivan Myasoedov

Ладьи на шахматной доске

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером $n × n$ можно расставить $n$ ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее $1000$.

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

Выведите ответ, найденный Гариком.

Тесты

#	ВХОДНЫЕ ДАННЫE:	ВЫХОДНЫЕ ДАННЫЕ:
1	2	2
2	10	3628800
3	3	6
4	1	1
5	4	24

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

import java.util.Scanner;
import java.math.BigInteger;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
    	Scanner in = new Scanner(System.in);
    	int a = in.nextInt();
    	BigInteger [] f = new BigInteger[30000];
    	f[0] = BigInteger.valueOf(1);
    	for(int i = 1; i <= a; i++)
    	{
    	  f[i]=f[i-1].multiply(BigInteger.valueOf(i));
    	}
	    System.out.print(f[a]);
	}
}

import java.util.Scanner;

import java.math.BigInteger;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int a = in.nextInt();

BigInteger [] f = new BigInteger[30000];

f[0] = BigInteger.valueOf(1);

for(int i = 1; i <= a; i++)

{

f[i]=f[i-1].multiply(BigInteger.valueOf(i));

}

System.out.print(f[a]);

}

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

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

e-olymp 47. Паркет из треугольников

27/12/2018 by Артем Чернобровкин

Задача

Прямоугольную комнату размерами [latex] m [/latex] на [latex] n [/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex] a [/latex] на паркетину [latex] b [/latex].

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

Во входном файле в первой сроке через пробел заданы значения [latex]m[/latex], [latex]n[/latex] [latex]\left ( 1\leqslant n,m\leqslant 100 \right )[/latex], а во второй — [latex] a [/latex] и [latex] b [/latex].

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

Искомое количество шагов

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
3	5 4 15 22	3
5	3 2 6 12	2

Код 1

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


class Main
{
	public static void swap(int A, int B) {
		int C = A;
		A = B;
		B = C;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		int vertSize;
		int horSize;
    	int firstNumber;
    	int lastNumber;
    	Scanner in = new Scanner(System.in);
    	horSize = in.nextInt();
		vertSize = in.nextInt();
		firstNumber = in.nextInt();
		lastNumber= in.nextInt();
    	if (firstNumber > lastNumber){
    		int C = firstNumber;
			firstNumber = lastNumber;
			lastNumber = C;
    	} 
    //вычисление координат
    	int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    	int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    	int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    	int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    	int[] Search= new int[2 * horSize];
    	Search[firstNumberx - 1] = 0;
    	int step = 1;
    	for (int i = firstNumberx - 2; i >= 0; i--){
        	Search[i] = step++;
    	}
    	step = 1;
    	for (int i = firstNumberx; i < 2 * horSize; i++){
        	Search[i] = step++;
    	}
    	//сравнение по у
    	for (int j = firstNumbery; j < lastNumbery; j++) {
        	for (int i = 1; i < 2 * horSize; i += 2) {
            	Search[i - 1] = Search[i] + 1;
            	Search[i] += 2;
            //определение значения на предпоследнем элементе
            	if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                	Search[i - 2] = Search[i];
            	}
        	}
    	}
    System.out.println(Search[lastNumberx - 1]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void swap(int A, int B) {

int C = A;

A = B;

B = C;

}

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

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

Scanner in = new Scanner(System.in);

horSize = in.nextInt();

vertSize = in.nextInt();

firstNumber = in.nextInt();

lastNumber= in.nextInt();

if (firstNumber > lastNumber){

int C = firstNumber;

firstNumber = lastNumber;

lastNumber = C;

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int[] Search= new int[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

for (int i = firstNumberx; i < 2 * horSize; i++){

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

for (int i = 1; i < 2 * horSize; i += 2) {

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определение значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

System.out.println(Search[lastNumberx - 1]);

}

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Следующим шагом будет определение позиции [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Положим, что [latex]x[/latex] — это позиция в строке, а [latex]y[/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем массив, переменные в котором будет иметь тип [latex]int[/latex] , а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex]int[/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции [latex]Search[firstNumberx — 1][/latex] стояло количество шагов, совершенных в ходе решения.

Код 2

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long m, n, a, b;
		Scanner in = new Scanner(System.in);
		m = in.nextLong();
		n = in.nextLong();
		a = in.nextLong();
		b = in.nextLong();
    	long dm = ((a + 1)/2 - 1) %m - ((b + 1)/2 - 1) % m;
    	long dn = (a - 1)/(2 * m) - (b - 1)/(2 * m);
    	long o = dm * dn < 0? Math.min(Math.abs(dm), Math.abs(dn)) : 0;
    	long k = dm > 0? 1: -1;
    	a += 2*k*o*(m - 1);
    	System.out.print( ((a + b) % 2 == 0? 0: Math.max(a, b) % 2 == 0? 1: -1) + 2*(Math.abs(dm) + Math.abs(dn) - o));

	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long m, n, a, b;

Scanner in = new Scanner(System.in);

m = in.nextLong();

n = in.nextLong();

a = in.nextLong();

b = in.nextLong();

long dm = ((a + 1)/2 - 1) %m - ((b + 1)/2 - 1) % m;

long dn = (a - 1)/(2 * m) - (b - 1)/(2 * m);

long o = dm * dn < 0? Math.min(Math.abs(dm), Math.abs(dn)) : 0;

long k = dm > 0? 1: -1;

a += 2*k*o*(m - 1);

System.out.print( ((a + b) % 2 == 0? 0: Math.max(a, b) % 2 == 0? 1: -1) + 2*(Math.abs(dm) + Math.abs(dn) - o));

}

Ссылки

Задача на e-olymp

Код_1 задачи на ideone

Код_2 задачи на ideone

e-olymp 1489. Шоколад

27/12/2018 by Илья Черноморец

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленькихшоколадных долек — прямоугольников $2 \cdot 1$.

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

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные	Выходные данные
2 3 1 1 2 3 3 2	Yes
5 6 1 2 2 3 3 4 1 5 6 7 7 4 8 5 6 9 10 10 8 11 11 9 12 13 14 14 15 15 12 13	No
4 7 1 1 2 5 8 11 6 2 14 4 7 3 9 5 3 7 10 6 13 2 3 4 3 8 12 5 7 7	Yes

Код решения

import java.io.InputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        new Resolver(System.in, System.out).solve();
    }

    public static class Resolver {

        private Scanner scanner;
        private PrintWriter writer;

        public Resolver(InputStream is, OutputStream os) {
            this.scanner = new Scanner(is);
            this.writer = new PrintWriter(os);
        }

        public void solve() {
            int rowCount = scanner.nextInt();
            int columnCount = scanner.nextInt();
            int[][] chocolate = new int[rowCount][columnCount];
            for (int i = 0; i < rowCount; i++) {
                for (int j = 0; j < columnCount; j++) chocolate[i][j] = scanner.nextInt();
            }
            check(chocolate, rowCount, columnCount);
            writer.flush(); writer.close();
        }

        private void check(int[][] chocolate, int rowCount, int columnCount) {
            if (BreakRow(chocolate, rowCount, columnCount) || BreakColumn(chocolate, rowCount, columnCount)) writer.println("Yes");
            else writer.println("No");
        }
        private boolean BreakRow(int[][] chocolate, int rowCount, int columnCount) {
            for (int i = 0; i < rowCount - 1; i++) {
                boolean okRow = true;
                for (int j = 0; j < columnCount; j++) {
                    if (chocolate[i][j] == chocolate[i + 1][j]) { okRow = false; break; }
                }
                if (okRow) return true;
            }
            return false;
        }
        private boolean BreakColumn(int[][] chocolate, int rowCount, int columnCount) {
            for (int i = 0; i < columnCount - 1; i++) {
                boolean okColumn = true;
                for (int j = 0; j < rowCount; j++) {
                    if (chocolate[j][i] == chocolate[j][i + 1]) { okColumn = false; break; }
                }
                if (okColumn) return true;
            }
            return false;
        }
    }
}

import java.io.InputStream;

import java.io.OutputStream;

import java.io.PrintWriter;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

new Resolver(System.in, System.out).solve();

}

public static class Resolver {

private Scanner scanner;

private PrintWriter writer;

public Resolver(InputStream is, OutputStream os) {

this.scanner = new Scanner(is);

this.writer = new PrintWriter(os);

}

public void solve() {

int rowCount = scanner.nextInt();

int columnCount = scanner.nextInt();

int[][] chocolate = new int[rowCount][columnCount];

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

for (int j = 0; j < columnCount; j++) chocolate[i][j] = scanner.nextInt();

}

check(chocolate, rowCount, columnCount);

writer.flush(); writer.close();

}

private void check(int[][] chocolate, int rowCount, int columnCount) {

if (BreakRow(chocolate, rowCount, columnCount) || BreakColumn(chocolate, rowCount, columnCount)) writer.println("Yes");

else writer.println("No");

}

private boolean BreakRow(int[][] chocolate, int rowCount, int columnCount) {

for (int i = 0; i < rowCount - 1; i++) {

boolean okRow = true;

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

if (chocolate[i][j] == chocolate[i + 1][j]) { okRow = false; break; }

}

if (okRow) return true;

}

return false;

}

private boolean BreakColumn(int[][] chocolate, int rowCount, int columnCount) {

for (int i = 0; i < columnCount - 1; i++) {

boolean okColumn = true;

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

if (chocolate[j][i] == chocolate[j][i + 1]) { okColumn = false; break; }

}

if (okColumn) return true;

}

return false;

}

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true и false в обратном случае.Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа boolean. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

Ссылка на E-olymp
Ссылка на решение

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-olimp 2864. Табулирование функции

26/12/2018 by Антон Джашимов

Задача

Напишите программу, которая выводит на экран таблицу значений функции $y=3\sin (x)$ на промежутке от $a$ до $b$ включительно с шагом $h.$

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

В одной строке через пробел заданы три вещественных числа $a$, $b$ и $h.$

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

В каждой строке выведите по два числа $x$ и $y$ соответственно, по возрастанию $x$ с тремя десятичными знаками.

Тесты

Входные данные	Выходные данные
1 2 0.5	1.000 2.524 1.500 2.992 2.000 2.728
0 0 1	0.000 0.000
20 10 5	10.000 -1.632 15.000 1.951 20.000 2.739
-3 -1 1	-3.000 -0.423 -2.000 -2.728 -1.000 -2.524

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

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

class Main {
    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        double a, b, h;
        a = in.nextDouble();
        b = in.nextDouble();
        h = in.nextDouble();
        for (double x = a; x <= b; x += h) {
            System.out.printf("%.3f %.3f\n", x, 3 * Math.sin(x));
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

Scanner in = new Scanner(System.in);

double a, b, h;

a = in.nextDouble();

b = in.nextDouble();

h = in.nextDouble();

for (double x = a; x <= b; x += h) {

System.out.printf("%.3f %.3f\n", x, 3 * Math.sin(x));

}

Решение

C помощью цикла от $a$ до $b$ с шагом $h$ выведем на экран таблицу значений функции на заданном промежутке. Для вычисления синусов воспользуемся методом sin() из класса Math.

Ссылки

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