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 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 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-olymp 9036. Комбинация игральных костей

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

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	3	4
3	5	16
4	6	32
5	8	123

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
public class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
	    int ans = 0;
	    Scanner myObj = new Scanner(System.in);
	    n = myObj.nextInt(); //считываем сумму, для которой будем считать количество перестановок
	    int a[] = new int[n+1]; //создаем массив
	    Arrays.fill(a, 0);
	    if (n == 1) ans = 1;
	    if (n == 2) ans = 2;
	    if (n == 3) ans = 4;
	    if (n == 4) ans = 8;
	    if (n == 5) ans = 16;
	    if (n == 6) ans = 32;
	    // частные случаи
	    
	    if (n > 6)
	    {
	        a[1] = 1; 
	        a[2] = 2; 
	        a[3] = 4; 
	        a[4] = 8;
	        a[5] = 16; 
	        a[6] = 32; 
	        for (int i = 7; i < n + 1; i++)
	        {
	            a[i]=0;
	            for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы
	                a[i] = ( a[i] + a[i-j] ) % 1000000007;
	        }
	        ans = a[n];
	    }
	    
	    System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

public class Ideone

{

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

{

int n;

int ans = 0;

Scanner myObj = new Scanner(System.in);

n = myObj.nextInt(); //считываем сумму, для которой будем считать количество перестановок

int a[] = new int[n+1]; //создаем массив

Arrays.fill(a, 0);

if (n == 1) ans = 1;

if (n == 2) ans = 2;

if (n == 3) ans = 4;

if (n == 4) ans = 8;

if (n == 5) ans = 16;

if (n == 6) ans = 32;

// частные случаи

if (n > 6)

{

a[1] = 1;

a[2] = 2;

a[3] = 4;

a[4] = 8;

a[5] = 16;

a[6] = 32;

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

{

a[i]=0;

for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы

a[i] = ( a[i] + a[i-j] ) % 1000000007;

}

ans = a[n];

}

System.out.println(ans);

}

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$ . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается $a_{5}$ и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на $a_{7}$ и уменьшится на $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

Условие задачи на 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 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 4475. Часы

09/12/2018 by Алиса Ворохта

Задача

Жители планеты Олимпия любят летать в гости на другие планеты. Ученые планеты разработали часы, которые могут налаживаться для отсчета времени на любой планете. Эти часы состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

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

Входной файл содержит в единственной строке натуральные числа $S, M, H, K$ (количество секунд в минуте, минут в часе, часов в сутках и общее количество шариков соответственно), причем:

$S, M, H ≤ 60$;
$S+M+H-2≤K≤1000$

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

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

Тесты

Входные данные	Выходные данные
$5$ $12$ $12$ $30$	$380$
$7$ $10$ $40$ $70$	$5610$
$60$ $60$ $60$ $500$	$4560840$
$60$ $30$ $5$ $1000$	$4970$

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

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

class Main
{
	public static double gcd(double a, double b){
		double temp;
    	while(b > 0){
        	a = a - b*Math.floor(a/b);
        	temp = a;
			a = b;
	    	b = temp;
    	}
    	return a;
    }
    public static double lcm(double a, double b){
    	return a*(b/gcd(a,b));
    }
	public static void main (String[] args) throws java.lang.Exception
	{
    	int S, M, H, K;
		Scanner in = new Scanner(System.in);
		S = in.nextInt();
		M = in.nextInt();
		H = in.nextInt();
		K = in.nextInt();
		Deque clock = new ArrayDeque(); 
		for(int i = 1; i <= K; i++)
    		clock.addLast(i);
    	Stack s = new Stack();
    	Stack m = new Stack();
    	Stack h = new Stack();
    	while(h.size() != H){
    		s.push(clock.getFirst());  //первый шарик очереди падает
    		clock.removeFirst();       //на секундную чашу
    		if(s.size() == S){         //при переполнении чаши  
				m.push(s.peek());      //последний упавший шарик
    			s.pop();               //переходит на минутную чашу
    			while(!s.empty()){     //остальные шарики  
					clock.addLast((Integer)s.peek());   //переходят в конец очереди
					s.pop();           //в обратном порядке     
				}
				if(m.size() == M){     //аналогично при переполнении          
					h.push(m.peek());  //минутной чаши      
					m.pop();
					while(!m.empty()){
						clock.addLast((Integer)m.peek());
						m.pop();
					}
				}
			}
		}
		while(!h.empty()){
			clock.addLast((Integer)h.peek());
			h.pop();
		}
		/*суточная перестановка
		1  2  3  4  5  6  ... K
		a1 a2 a3 a4 a5 a6 ... ak*/
		int[] permutation = new int[K + 1];
		for(int i = 1; i <= K; i++){
			permutation[i] = clock.getFirst();
			clock.removeFirst();
		}
		//разложение перестановки в композицию непересекающихся циклов
		boolean[] used = new boolean[K+1]; 
		double permutationOrder = 1;    //метки на посещенных элементах
		for(int i = 1; i <= K; i++){    //порядок перестановки
		if(!used[i]){    //если элемент не принадлежит ни одному из обследованных циклов
				double cycleLength = 1;  //найти длину его цикла
				for(int x = i; permutation[x] != i; x = permutation[x]){
					used[x] = true;
					cycleLength++;
				}
				/*и воспользоваться тем, что порядок перестановки -
				произведение длин циклов из его разложения*/
				permutationOrder = lcm(permutationOrder, cycleLength);
			}
    	}
    	System.out.print(Math.round(permutationOrder));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static double gcd(double a, double b){

double temp;

while(b > 0){

a = a - b*Math.floor(a/b);

temp = a;

a = b;

b = temp;

}

return a;

}

public static double lcm(double a, double b){

return a*(b/gcd(a,b));

}

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

{

int S, M, H, K;

Scanner in = new Scanner(System.in);

S = in.nextInt();

M = in.nextInt();

H = in.nextInt();

K = in.nextInt();

Deque clock = new ArrayDeque();

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

clock.addLast(i);

Stack s = new Stack();

Stack m = new Stack();

Stack h = new Stack();

while(h.size() != H){

s.push(clock.getFirst()); //первый шарик очереди падает

clock.removeFirst(); //на секундную чашу

if(s.size() == S){ //при переполнении чаши

m.push(s.peek()); //последний упавший шарик

s.pop(); //переходит на минутную чашу

while(!s.empty()){ //остальные шарики

clock.addLast((Integer)s.peek()); //переходят в конец очереди

s.pop(); //в обратном порядке

}

if(m.size() == M){ //аналогично при переполнении

h.push(m.peek()); //минутной чаши

m.pop();

while(!m.empty()){

clock.addLast((Integer)m.peek());

m.pop();

}

while(!h.empty()){

clock.addLast((Integer)h.peek());

h.pop();

}

/*суточная перестановка

1 2 3 4 5 6 ... K

a1 a2 a3 a4 a5 a6 ... ak*/

int[] permutation = new int[K + 1];

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

permutation[i] = clock.getFirst();

clock.removeFirst();

}

//разложение перестановки в композицию непересекающихся циклов

boolean[] used = new boolean[K+1];

double permutationOrder = 1; //метки на посещенных элементах

for(int i = 1; i <= K; i++){ //порядок перестановки

if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов

double cycleLength = 1; //найти длину его цикла

for(int x = i; permutation[x] != i; x = permutation[x]){

used[x] = true;

cycleLength++;

}

/*и воспользоваться тем, что порядок перестановки -

произведение длин циклов из его разложения*/

permutationOrder = lcm(permutationOrder, cycleLength);

}

System.out.print(Math.round(permutationOrder));

}

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

Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
$\begin{pmatrix}
1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\
1& 5& 8& 2& 4& 3& 7& 7& 6& 10
\end{pmatrix}$
Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Примечание

Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.

Ссылки

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