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-olimp 1658. Факториал

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

Задача

Вычислите факториал числа.

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

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

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

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные	Выходные данные
3	6
0	1
20	2432902008176640000

Решение №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 factorial = 1;
    	for(int k = 1; k <= n; k++) {
        	factorial *= k;
    	}
    	System.out.print(factorial);
	}
}

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 factorial = 1;

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

factorial *= k;

}

System.out.print(factorial);

}

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.

Решение №2

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

public class Main{

public static long factorial(int a){

if (a == 0)

return 1;

else

return a*factorial(a - 1);

}

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

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

int a;

int n = i.nextInt();

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

}

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

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

e-olymp 123. Количество нулей у факториала

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

Задача

Найти количество нулей в конце записи факториала числа $n$.

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

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

Количество нулей в конце записи $n!$

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	0
2	7	1
3	12	2
4	100	24
5	306	75
6	5000	1249

Код

class Main{
	public static void main (String[] args){
		java.util.Scanner in = new java.util.Scanner(System.in); 
		long n = in.nextInt(), m = 5, s = 0;
		while(n >= m){
			s = s + (n / m); 
			m = m * 5;
		}
		System.out.println(s);
	}
}

class Main{

public static void main (String[] args){

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

long n = in.nextInt(), m = 5, s = 0;

while(n >= m){

s = s + (n / m);

m = m * 5;

}

System.out.println(s);

}

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

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

Код на Ideone

Засчитанное решение на e-olymp

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 271. Факториал!

27/12/2018 by Георгий Мартынюк

Задача

Найти значение факториала целого числа [latex]n[/latex]

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

Одно целое число [latex]n(0\leq n\leq 3000)[/latex].

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

Выведите факториал числа [latex]n[/latex].

Тесты

Входные данные	Выходные данные
3	6
5	120
1	1

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

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

public class factorial {
  public static BigInteger factorial(int num){
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= num; i++)
      fact = fact.multiply(BigInteger.valueOf(i));
     return fact;
}
 
  public static void main(String[] args) throws java.lang.Exception{
  Scanner input = new Scanner(System.in); 
  int x;
  x = input.nextInt(); 
  System.out.println(factorial(x));
  }
}

import java.util.Scanner;

import java.math.BigInteger;

public class factorial {

public static BigInteger factorial(int num){

BigInteger fact = BigInteger.valueOf(1);

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

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

return fact;

}

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

Scanner input = new Scanner(System.in);

int x;

x = input.nextInt();

System.out.println(factorial(x));

}

Решение

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.
Для решения данной задачи создаем класс [latex]factorial[/latex] для вычисления факториала. А потом используем метод [latex]factorial[/latex] в классе [latex]main[/latex].

Ссылки

e-olymp
Ideone

e-olymp 97. Числа Белла

23/12/2018 by Томас Пасенченко

Задача

Число Белла $B_n$ равно количеству разбиений множества из $n$ элементов на произвольное количество непересекающихся непустых подмножеств. Например, $B_3 = 5$, так как существует $5$ возможных разбиений множества $\lbrace a, b, c\rbrace$: $\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace$. Дополнительно считаем, что $B_0 = 1$.
Рассмотрим определитель $D_n$:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа $p$ найти наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

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

Каждая строка ввода содержит два целых числа $n$ и $p$ ($0\leq\; n,\;p \;\leq\; 10000$). Известно, что $p$ – простое.

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

Для каждой пары входных значений $n$ и $p$ в отдельной строке выведите наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

Тесты

Входные данные	Выходные данные
1 5 3 2 4 2 4 3 10000 3	0 2 5 2 24962375
18 2 465 1009 9998 9221 548 11	134 0 778 14412
1093 1093 1103 1723 3931 617 4868 6113 9534 71	1 0 10635 0 639989
617 17 42 11 0 5	11295 63 0

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

import java.util.Scanner;
public class Main {
 	public static void main (String[] args) {
   		Scanner scanner = new Scanner(System.in);
   		int n, p;
   		while(scanner.hasNextInt()) {
   			n = scanner.nextInt();
   			p = scanner.nextInt();
   			int k = 0;
   			for (int i = 1; i  0) {
   					fact /= p;
   					k += fact;
   				}
   			}
   			System.out.println(k);
   		}
   	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n, p;

while(scanner.hasNextInt()) {

n = scanner.nextInt();

p = scanner.nextInt();

int k = 0;

for (int i = 1; i 0) {

fact /= p;

k += fact;

}

System.out.println(k);

}

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i!$$
Воспользуемся этим свойством для решения данной задачи. Найдём степень числа $p$
в разложении на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число $k$.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Число Белла на wikipedia

e-olymp 513. Проблема Николая

05/11/2018 by Даниель Савчак

Задача

Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex].

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

Вывести искомое количество способов.

Тесты

Входные данные	Выходные данные
[latex]500[/latex] [latex]2001[/latex]	[latex]0[/latex]
[latex]4[/latex] [latex]5[/latex]	[latex]4[/latex]
[latex]4[/latex] [latex]7[/latex]	[latex]3[/latex]
[latex]15[/latex] [latex]213[/latex]	[latex]147[/latex]
[latex]10[/latex] [latex]3[/latex]	[latex]0[/latex]

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n, m, k = 1;
    	n = in.nextInt();
    	m = in.nextInt();
    	if ( n >= m) 
    	{
        	System.out.print(0);
    	}
    	else 
    	{
    		for ( int i = 2; i <= n; i++ ) 
    		{
            	k = ( k * i ) % m;
        	}
        	System.out.print(k); 
    	}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n, m, k = 1;

n = in.nextInt();

m = in.nextInt();

if ( n >= m)

{

System.out.print(0);

}

else

{

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

{

k = ( k * i ) % m;

}

System.out.print(k);

}

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

Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.

Ссылки

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

Код решения на ideone.com.

А136з

23/11/2016 by Коваль Максим

Задача Вычислить: Реализовать формулу, x+=[знак который зависит от четности/нечетности определяется отдельно для каждого элемента массива]*[соответствующий элемент массива]/[факториал текущего номера элемента массива].

Тест

n	последовательность	sum(wolframalpha)
2	0 0	0
2	5 8	-1
3	5 8 12	-3
4	1 2 3 24	1
5	0 0 0 2 3	0, 058333

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

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception{
                Scanner in = new Scanner(System.in);
                int n = in.nextInt();
                int[] a = new int[n];
                for (int i=0; i<n; i++){
                     a[i] = in.nextInt();
                }
                double sum=0;
                int f=1;
                for (int i=1; i<=n; i++){
                     f*=i;
                     double sign = (i%2==0) ? 1 : -1;
                     sum+=(sign*a[i-1])/f;
                }
                System.out.println(sum);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[] a = new int[n];

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

a[i] = in.nextInt();

}

double sum=0;

int f=1;

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

f*=i;

double sign = (i%2==0) ? 1 : -1;

sum+=(sign*a[i-1])/f;

}

System.out.println(sum);

}

Решение:
В этой задаче главное правильно расставить знаки, так как это повлияет на результат.Поэтому мы заводим переменную $sign$ , которая будет следить за знаком. Далее проверяем чётность, если элемент делиться на 2 без остатка, то он получает знак $+$

Ссылка на Ideone

http://ideone.com/ZB6a2C

А137е

06/07/2016 by Ирина Литвиненко

Даны натуральные [latex]n[/latex], действительные [latex]a_1,\ldots, a_n[/latex].

Вывести: [latex]a_1+1!, a_2 +2!,\ldots, a_n+n![/latex].

Тесты:

n	a1	a2	a3	a4
4	1	2	3	4	Output	2	4	9	28
4	0.1	0.2	0.3	0.4	Output	1.1	2.2	6.3	24.4

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

class Main {
	
	public static void main (String[] args) throws java.lang.Exception {
		
		int n;
		double a, fact = 1.0;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); //читаем n
		
		for(int k = 1; k <= n; k++) {
			
			a = scanner.nextDouble(); //читаем из потока k-ый элемент 
			fact *= k; //увеличиваем фаториал
			System.out.print( (a+fact) + " "); //выводим сумму цифры из потока и факториала
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

int n;

double a, fact = 1.0;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt(); //читаем n

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

a = scanner.nextDouble(); //читаем из потока k-ый элемент

fact *= k; //увеличиваем фаториал

System.out.print( (a+fact) + " "); //выводим сумму цифры из потока и факториала

}

www.ideone.com

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл for, от [latex]1[/latex] до [latex]n[/latex]. Дальше в теле цикла описываем чтение элементов, увеличение факториала и вывод суммы цифр из потока и факториала.