Задача

Подсчитайте количество способов, которыми можно получить сумму $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

Задача

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

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

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

Входной файл содержит в единственной строке натуральные числа $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
Код решения

java@Cat

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

Tag Archives: перестановки

e-olymp 9036. Комбинация игральных костей

Задача

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

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

Тесты

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

Решение

Ссылки

e-olymp 4475. Часы

Задача

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

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

Тесты

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

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

Примечание

Ссылки