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 8950. Шаблон 5

08/11/2022 by Наталья Фатеева

Условие

По заданному нечетному натуральному числу [latex] n [/latex] вывести изображение размером [latex] n × n [/latex], образованное символами звездочка и пробел как показано в примере.

*				*
*	*		*	*
*	*	*	*	*
*	*		*	*
*				*

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

Одно нечетное натуральное число [latex] n (n>1)[/latex] .

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

Вывести изображение [latex] n × n [/latex].

Тесты

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

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

*		*
*	*	*
*		*

*				*
*	*		*	*
*	*	*	*	*
*	*		*	*
*				*

*						*
*	*				*	*
*	*	*		*	*	*
*	*	*	*	*	*	*
*	*	*		*	*	*
*	*				*	*
*						*

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

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

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		
		Scanner l= new Scanner(System.in);
		int n= l.nextInt();
    	// Создаем  матрицу для хранения всех ответов
	        int [][]x = new int [n][n];
    	        int m=(n-1)/2;
    	      for(int i=0;i<n;i++){
    		    for(int j=0;j<n;j++){
        		x[i][j]=1;
		        }
    		    for(int j=i+1;j<n-i-1;j++){
        		x[i][j]=0;
    		    }
    	          }
 
    	      for( int i=0;i<m;i++){
    		    for (int j=0;j<n;j++){
        		if(x[i][j]==0) {
        			x[n-i-1][j]=0;
    			}
    		     }
    	          }
		       for(int i=0;i<n;i++){
    		     for(int j=0;j<n;j++){
    			    if(x[i][j]!=0){
        			System.out.print("*");
        		    }
        		    else System.out.print(" ");
    		      }
    		     System.out.println(" ");
		      }
      }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

public class Main

{

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

{

Scanner l= new Scanner(System.in);

int n= l.nextInt();

// Создаем матрицу для хранения всех ответов

int [][]x = new int [n][n];

int m=(n-1)/2;

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

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

x[i][j]=1;

}

for(int j=i+1;j<n-i-1;j++){

x[i][j]=0;

}

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

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

if(x[i][j]==0) {

x[n-i-1][j]=0;

}

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

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

if(x[i][j]!=0){

System.out.print("*");

}

else System.out.print(" ");

}

System.out.println(" ");

}

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

Считываем значение [latex]n[/latex]. Создаём двумерный массив [latex] n * n [/latex] все элементы которого равны единице. Далее в цикле заполняем пространство между [latex] * [/latex] нулями. Так как позиции [latex] (i,0)[/latex] и [latex] (i,n) [/latex] всегда [latex] * [/latex], ко второму счётчику [latex] j [/latex] прибавляем единицу . На середине [latex] m = ( n — 1 ) / 2 [/latex] цикл прекращает заполнение нулями, потому в следующем цикле верхняя часть отображается в нижнюю. После чего происходит вывод двумерного массива заменяя [latex] 0=« » [/latex] и [latex] 1=«*» [/latex].

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

e-olymp 8669. Все делители

03/12/2020 by Катя Романцова

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

Найдите все делители натурального числа $n$.

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

Одно натуральное число $ n ( n \leqslant 10^9 ) $.

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

Выведите в возрастающем порядке все делители числа $n$.

Тесты

№	Входные данные	Выходные данные
1	10	1 2 5 10
2	36	1 2 3 4 6 9 12 18 36
3	455	1 5 7 13 35 65 91 455
4	38965	1 5 7793 38965
5	999999	1 3 7 9 11 13 21 27 33 37 39 63 77 91 99 111 117 143 189 231 259 273 297 333 351 407 429 481 693 777 819 999 1001 1221 1287 1443 2079 2331 2457 2849 3003 3367 3663 3861 4329 5291 6993 8547 9009 10101 10989 12987 15873 25641 27027 30303 37037 47619 76923 90909 111111 142857 333333 999999
6	1000000000	1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3906250 4000000 5000000 6250000 7812500 8000000 10000000 12500000 15625000 20000000 25000000 31250000 40000000 50000000 62500000 100000000 125000000 200000000 250000000 500000000 1000000000

Код

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

class Main 
{ 
	public static void main (String[] args) throws java.lang.Exception
	{
		 Scanner sc = new Scanner(System.in); 
		 int n = sc.nextInt(); 
		 double sqrt_n = Math.sqrt (n);
	 	 for (int i = 1; i < sqrt_n; i++) { 
	 	 	 if (n % i == 0) System.out.print(i + " "); 
	 	 } 
	 	 for (int i = (int)sqrt_n; i >= 1; i--) { 
	 	 	 if (n % i == 0) System.out.print(n/i + " ");
	 	 }
	 }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

double sqrt_n = Math.sqrt (n);

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

if (n % i == 0) System.out.print(i + " ");

}

for (int i = (int)sqrt_n; i >= 1; i--) {

if (n % i == 0) System.out.print(n/i + " ");

}

Решение

Можно заметить, что делитель и частное взаимодополняют друг друга. Мы найдем делители, потом частные этого выражения. Так как частные также являются делителями. Значит последовательность делителей в порядке возрастания можно разделить на две части. Создадим два цикла для нахождения этих двух частей:

в первом цикле проверяем каждое натуральное число от $1$ до $\sqrt n$. Выводим числа, если они являются делителями;
во втором цикле делим заданное число $n$ на все делители и выводим.

Ссылки

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

Код на Ideone

Засчитанный код на E-olymp

e-olimp 8536. Заповнення смуги $3 \times n$

02/12/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

import java.util.Scanner;

class Main {
	public static void main (String[] args) {
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	    int[] F = new int[51];
	    F[0] = 0;
	    F[1] = 1;
	    F[2] = 1;
	    F[3] = 2;
	    F[4] = 3;
	    for(int i = 5; i <= n; i++) {
	       F[i] = F[i-2] + F[i-3] + F[i-4];
	    }
	    System.out.println(F[n]);
	}
}

import java.util.Scanner;

class Main {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] F = new int[51];

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

System.out.println(F[n]);

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

import java.util.Scanner;

public class Main {
	public static int[] F = new int[51];
	public static int numberOfWays(int n){
		F[0] = 0;
		F[1] = 1;
		F[2] = 1;
		F[3] = 2;
		F[4] = 3;
	    if(F[n] > 0) {
    		return F[n];
		} else {
    		F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
		}
		return F[n];
	}
	public static void main (String[] args){
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	    System.out.println(numberOfWays(n));
	}
}

import java.util.Scanner;

public class Main {

public static int[] F = new int[51];

public static int numberOfWays(int n){

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

if(F[n] > 0) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

public static void main (String[] args){

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

System.out.println(numberOfWays(n));

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

e-olymp 798. Платформы

02/12/2020 by Анна Цивинская

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

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

Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

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

В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

Тесты

№	Ввод	Вывод
1	4 1 2 3 30	29 4 1 2 3 4
2	2 7 23	16 2 1 2
3	5 0 1 0 1 0	0 3 1 3 5

Код

import java.util.Scanner;

class Main{
	public static void main (String[] args) {
		final int MAX = 100001;
		Scanner sc = new Scanner(System.in);
        int amount_of_pltf = sc.nextInt();
        int[] energy, platforms,  list_of_pltf;
        int[] heights = new int[MAX];
        for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();
        
        energy = new int[MAX];
        platforms = new int[MAX];
        energy[1] = 0;
    	energy[2] = Math.abs(heights[2] - heights[1]);
    	platforms[1] = -1;
    	platforms[2] = 1;
    	
    	//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
	    for (int j = 3; j <= amount_of_pltf; j++){
	        if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){
	            energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);
	            platforms[j] = j - 1;
	        } else {
	            energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);
	            platforms[j] = j - 2;
	        }
	    }
	    
	    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
	    int final_amount = 0;
	    list_of_pltf = new int[MAX];
	    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
	    
    	System.out.println(energy[amount_of_pltf] + "\n" + final_amount);
	    for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");
	}
}

import java.util.Scanner;

class Main{

public static void main (String[] args) {

final int MAX = 100001;

Scanner sc = new Scanner(System.in);

int amount_of_pltf = sc.nextInt();

int[] energy, platforms, list_of_pltf;

int[] heights = new int[MAX];

for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();

energy = new int[MAX];

platforms = new int[MAX];

energy[1] = 0;

energy[2] = Math.abs(heights[2] - heights[1]);

platforms[1] = -1;

platforms[2] = 1;

//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)

for (int j = 3; j <= amount_of_pltf; j++){

if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){

energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);

platforms[j] = j - 1;

} else {

energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);

platforms[j] = j - 2;

}

//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.

int final_amount = 0;

list_of_pltf = new int[MAX];

for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;

System.out.println(energy[amount_of_pltf] + "\n" + final_amount);

for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");

}

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

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

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки

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 8538. Калькулятор

27/11/2020 by Александр Розин

Условие

Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.

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

Одно число $n$ $\left(10\leq n\leq 10^9\right)$.

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

Выведите наименьшее количество операций.

Тесты

№	Входные данные	Выходные данные
1	1447	16
2	18	3
3	111	6

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

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);
		int n = in.nextInt();
		int k = 0;
		while(n > 0) {
			k += n%3 + 1;
			n /= 3;
		}
		System.out.print(k - 2);
	}
}

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);

int n = in.nextInt();

int k = 0;

while(n > 0) {

k += n%3 + 1;

n /= 3;

}

System.out.print(k - 2);

}

Решение

Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$. n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $13$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.

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

04/10/2020 by Эвелина Алексютенко

Задача

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

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

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

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

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

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

Тесты

Входные данные	Выходные данные
2	2
10	3628800
500	122013682599111006870123878542304692625357434280319284219241 358838584537315388199760549644750220328186301361647714820358 416337872207817720048078520515932928547790757193933060377296 085908627042917454788242491272634430567017327076946106280231 045264421887878946575477714986349436778103764427403382736539 747138647787849543848959553753799042324106127132698432774571 554630997720278101456108118837370953101635632443298702956389 662891165897476957208792692887128178007026517450776841071962 439039432253642260523494585012991857150124870696156814162535 905669342381300885624924689156412677565448188650659384795177 536089400574523894033579847636394490531306232374906644504882 466507594673586207463792518420045936969298102226397195259719 094521782333175693458150855233282076282002340262690789834245 171200620771464097945611612762914595123722991334016955236385 094288559201872743379517301458635757082835578015873543276888 868012039988238470215146760544540766353598417443048012893831 389688163948746965881750450692636533817505547812864000000000 000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000
999	402387260077093773543702433923003985719374864210714632543799 910429938512398629020592044208486969404800479988610197196058 631666872994808558901323829669944590997424504087073759918823 627727188732519779505950995276120874975462497043601418278094 646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347 553428646576611667797396668820291207379143853719588249808126 867838374559731746136085379534524221586593201928090878297308 431392844403281231558611036976801357304216168747609675871348 312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092 761244896359928705114964975419909342221566832572080821333186 116811553615836546984046708975602900950537616475847728421889 679646244945160765353408198901385442487984959953319101723355 556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545 257223865541461062892187960223838971476088506276862967146674 697562911234082439208160153780889893964518263243671616762179 168909779911903754031274622289988005195444414282012187361745 992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933 061690897968482590125458327168226458066526769958652682272807 075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301 435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720 559654228749774011413346962715422845862377387538230483865688 976461927383814900140767310446640259899490222221765904339901 886018566526485061799702356193897017860040811889729918311021 171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926 649875337218940694281434118520158014123344828015051399694290 153483077644569099073152433278288269864602789864321139083506 217095002597389863554277196742822248757586765752344220207573 630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457 156805941872748998094254742173582401063677404595741785160829 230135358081840096996372524230560855903700624271243416909004 153690105933983835777939410970027753472000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

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

import java.math.BigInteger;
import java.util.Scanner;

class Main
{
	public static void main (String[] args) 
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		BigInteger factorial = BigInteger.valueOf(1); 
		/* присваиваем результату 1, приводя к типу BigInteger;
		1 - нейтральный элемент относительно умножения */
		if(n == 0) {
			System.out.println(1);
		}
		else {
			for(int i = 1; i <=n; i++) {
				factorial = factorial.multiply(BigInteger.valueOf(i)); 
				// приводим i к типу BigInteger
			}
			System.out.println(factorial);
		}
	}
}

import java.math.BigInteger;

import java.util.Scanner;

class Main

{

public static void main (String[] args)

{

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

BigInteger factorial = BigInteger.valueOf(1);

/* присваиваем результату 1, приводя к типу BigInteger;

1 - нейтральный элемент относительно умножения */

if(n == 0) {

System.out.println(1);

}

else {

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

factorial = factorial.multiply(BigInteger.valueOf(i));

// приводим i к типу BigInteger

}

System.out.println(factorial);

}

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

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

Детали реализации

Для реализации алгоритма я использовала класс java.math.BigInteger, подробнее о нем можно почитать здесь.
Также для ввода данных я использовала класс java.util.Scanner, подробнее о нем можно почитать тут и вот тут.

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

e-olymp 1704. Умная черепашка

30/09/2020 by Виктория Крачилова

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

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

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

Тесты

№	Ввод	Вывод
1	4 5	10
2	3 14	105
3	11 17	5311735
4	20 21	68923264410
5	30 30	30067266499541040

Код программы (циклы)

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int m = i.nextInt();
	    if (m > n){
	    	int t = n;
	    	n = m;
	    	m = t;
	    }
	    long den = 1, ways = 1; // den - знаменатель, ways - количество способов.
	    for (int j = 0; j < m - 1; j++) {
	        ways *= n + j;
	        if (ways % den == 0) {
	            ways /= den;
	            den++;
	        }
	    }
	    System.out.println(ways);
	}
}

class Main

{

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

{

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

int n = i.nextInt();

int m = i.nextInt();

if (m > n){

int t = n;

n = m;

m = t;

}

long den = 1, ways = 1; // den - знаменатель, ways - количество способов.

for (int j = 0; j < m - 1; j++) {

ways *= n + j;

if (ways % den == 0) {

ways /= den;

den++;

}

System.out.println(ways);

}

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$. Для того, чтобы избежать больших чисел, делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

Ссылки (циклы)

Код программы (динамическое программирование)

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    // Создаем треугольную матрицу для хранения всех ответов
	    long [][]x = new long [30][];
	    for (int i = 0; i < 30; ++i) x[i] = new long[i+1];
	    // Находим все ответы
	    x[0][0] = 1;
	    for (int i = 1; i < 30; ++i) {
	        x[i][0] = 1;
	        for (int j = 1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];
	        x[i][i] = 2 * x[i][i-1];        
	    }
	    // Проходим все тесты
	    java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int m = i.nextInt();
	    System.out.println(x[Math.max(n,m)-1][Math.min(n,m)-1]);
	}
}

class Main

{

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

{

// Создаем треугольную матрицу для хранения всех ответов

long [][]x = new long [30][];

for (int i = 0; i < 30; ++i) x[i] = new long[i+1];

// Находим все ответы

x[0][0] = 1;

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

x[i][0] = 1;

for (int j = 1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];

x[i][i] = 2 * x[i][i-1];

}

// Проходим все тесты

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

int n = i.nextInt();

int m = i.nextInt();

System.out.println(x[Math.max(n,m)-1][Math.min(n,m)-1]);

}

Решение

Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.

Ссылки (динамическое программирование)

e-olimp 7848. Переставить соседние

20/09/2020 by Елизавета Савицкая

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

Тесты

Входные данные	Выходные данные
7 3 5 -7 7 5 -9 -4	5 3 7 -7 -9 5 -4
8 -9 81 27 -38 2 6 -56 -21	81 -9 -38 27 6 2 -21 -56
2 25 -76	-76 25
3 55 44 33	44 55 33
1 99	99

Код

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int arr[] = new int[n];
		for(int k = 0; k < n; k++){
        	arr[k] = i.nextInt();
		} 
    	for(int k = 1; k < n; k+=2){
        	int q = arr[k];
        	arr[k] = arr[k-1];
        	arr[k-1] = q;
		}
		for(int k = 0; k < n; k++){
    		System.out.print(arr[k] + " ");
		}
	}
}

class Main{

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

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

int n = i.nextInt();

int arr[] = new int[n];

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

arr[k] = i.nextInt();

}

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

int q = arr[k];

arr[k] = arr[k-1];

arr[k-1] = q;

}

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

System.out.print(arr[k] + " ");

}

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olimp 8234. Сходинки

20/09/2020 by Елизавета Савицкая

Задача

Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

Вхідні дані

Одне число $n$ — номер сходинки $(n \leqslant 60)$.

Вихідні дані

Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

Тести

Вхідні дані	Вихідні дані
0	1
5	13
15	5768
32	181997601
60	4680045560037375

Код № 1

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		long array[] = new long[61];
		array[0] = 1;
    	array[1] = 1;
    	array[2] = 2;
    	for(int k = 3; k <= n; k++) {
        	array[k] = array[k-1] + array[k-2] + array[k-3];
		}
		System.out.print(array[n]);
	}
}

class Main{

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

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

int n = i.nextInt();

long array[] = new long[61];

array[0] = 1;

array[1] = 1;

array[2] = 2;

for(int k = 3; k <= n; k++) {

array[k] = array[k-1] + array[k-2] + array[k-3];

}

System.out.print(array[n]);

}

Рішення

Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

Код № 2

public class Main{
	public static long array[] = new long[61];
    public static long num_of_ways(int n){
		if(array[n] == 0) {
			array[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);
        	return array[n];
    	}
		else {
        	return array[n];
    	}
	}
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		array[0] = 1;
    	array[1] = 1;
    	array[2] = 2;
		System.out.print(num_of_ways(n));
	}
}

public class Main{

public static long array[] = new long[61];

public static long num_of_ways(int n){

if(array[n] == 0) {

array[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);

return array[n];

}

else {

return array[n];

}

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

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

int n = i.nextInt();

array[0] = 1;

array[1] = 1;

array[2] = 2;

System.out.print(num_of_ways(n));

}

Посилання

Умова задачі на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone