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

10/12/2019 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

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

Первый способ (выполняется быстрее, но использует больше памяти)

#include <iostream>
using namespace std;

int main() {
    int n;
    int ans;
    cin >> n; //считываем сумму, для которой будем считать количество перестановок
    long long a[n+1]; //создаем массив
    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];
    }
    
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int ans;

cin >> n; //считываем сумму, для которой будем считать количество перестановок

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

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

}

cout << ans;

return 0;

}

Второй способ (использует меньше памяти, но выполняется дольше)

#include <iostream>
using namespace std;

int main() {
    int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6
    int n, quantity, counter = 6;
    cin >> n; //считываем сумму
    if (n > 6)
    {
        while (counter < n)
        {
            counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов
            quantity = 0;
            for (int j = 1; j < 7; j++) //подсчет количества способов для k-ой суммы
                quantity = (quantity + a[6-j]) % 1000000007;
                
            for (int i = 0; i < 5; i++)  
                a[i] = a[i+1];
            a[5] = quantity;
        }
        cout << a[5];
    }
    else cout << a[n-1];
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6

int n, quantity, counter = 6;

cin >> n; //считываем сумму

if (n > 6)

{

while (counter < n)

{

counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов

quantity = 0;

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

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

for (int i = 0; i < 5; i++)

a[i] = a[i+1];

a[5] = quantity;

}

cout << a[5];

}

else cout << a[n-1];

return 0;

}

Решение

Создадим массив на $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

Related Images:

e-olymp 203. Кубики-2

02/01/2018 by Данила Савчак

Задача

После Нового года Витэк решил стать банкиром и поэтому стал играться только кубиками с цифрами, ведь будущая профессия требовала умения четко и быстро оперировать с цифрами и числами. И опять ему нравились такие расположения кубиков, на которых последовательность изображенных на них цифр читалась в обеих направлениях одинаково.
Каждое утро, придя в детсад Витэк сразу смотрел на разложенные на полу кубики, и если последовательность не читалась в обеих направлениях одинаково, доставал какое-то количество новых кубиков и размещал их правее, чтобы получить такое размещение кубиков, которое соответствовало его требованию.
Какое наименьшее количество кубиков нужно доставить для этого Витэку?

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

В первой строке – количество разложенных перед Витэком кубиков [latex]N[/latex] [latex](1 ≤ N ≤ 100)[/latex], в следующей строке последовательность из [latex]N[/latex] цифр на кубиках через пробел.

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

Наименьшее количество кубиков, которое нужно правее доставить Витэку.

Тесты

#	Входные данные	Выходные данные
1	3 1 2 3	2
2	5 1 2 3 4 4	3
3	2 1 2	1
4	2 1 1	0

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

#include <iostream>
using namespace std;

int main() {
    int n, h=0, k=0;
    cin >> n;
    int A[n];
    for ( int i = 0; i < n; i++ ) {
        cin >> A[i];
    }
    for ( int i = 0; i < n; i++ ) {
        if ( A[n-1] == A[i] ) {
            int t = 1;
            for ( int j = i + 1; j < n - 1; j++ ) {
                if ( A[j] != A[ n - 1 - t ] ) {
                    k++;
                }
                t++;
            }
            if ( k == 0 ) {
                h = i;
                break;
            }
            else k = 0;
        }
    }
    cout << h;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, h=0, k=0;

cin >> n;

int A[n];

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

cin >> A[i];

}

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

if ( A[n-1] == A[i] ) {

int t = 1;

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

if ( A[j] != A[ n - 1 - t ] ) {

k++;

}

t++;

}

if ( k == 0 ) {

h = i;

break;

}

else k = 0;

}

cout << h;

return 0;

}

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

Читаем поток данных переводя каждое прочитанное число в элемент массива. Для каждого элемента массива проверяем его равенство с последний и если да, то через два цикла(начиная с начала и с конца) проверяем равенство остальных элементов массива по двое и если да, то увеличиваем переменную, от которой будет зависеть ответ, если она в конце будет равна [latex]0[/latex], то выведем число равное номеру элемента массива равного последнему.

Ссылки

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

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

Related Images:

e-olymp 2807. Кубики — 3

31/12/2017 by Валерия Ларикова

Задача

Дома у Витека было [latex]2[/latex] одинаковых набора кубиков из английских букв, но во время очередной уборки один из кубиков затерялся. Помогите Витеку определить, какой же из кубиков отсутствует в одном из наборов.

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

В первой строке задано количество найденных Витеком кубиков [latex]n (1 ≤ n ≤ 10^5)[/latex], а во второй строке [latex]n[/latex] символов, изображённых на каждом из кубиков.

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex] «Ok»[/latex], если Витек ошибся и ни один из кубиков не потерялся.

Тесты

#	Входные данные	Выходные данные
1	5 abcac	b
2	8 ryirhiyh	Ok
3	3 AVA	V
4	6 DjkjDk	Ok
5	7 LnCsCnL	s

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

#include <iostream>
#include <string>//данная библиотека содержит методы и переменные для работы со строками
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n % 2 == 0) cout << "Ok";
    else {
        int x[200];
        for ( int i = 65; i <= 122; i++)
            x[i] = 0;
        char c;
        while ((c = cin.get()) != EOF)
            x[c]++;
        for (int i = 'A'; i <= 'z'; i++)
            if (x[i] % 2 != 0) 
                c = i;
        cout << c;
    }
    return 0;
}

#include <iostream>

#include <string>//данная библиотека содержит методы и переменные для работы со строками

using namespace std;

int main() {

int n;

cin >> n;

if (n % 2 == 0) cout << "Ok";

else {

int x[200];

for ( int i = 65; i <= 122; i++)

x[i] = 0;

char c;

while ((c = cin.get()) != EOF)

x[c]++;

for (int i = 'A'; i <= 'z'; i++)

if (x[i] % 2 != 0)

c = i;

cout << c;

}

return 0;

}

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

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Если условие выполняется, то выводим на экран сообщение с текстом [latex] «Ok»[/latex]. Если нет, то рассматриваем второй случай. Создаем массив, в котором будем хранить количество кубиков для каждой буквы. Обнуляем ячейки массива, в которых будут храниться данные. Далее мы будем считывать символы в соответствии с их числовыми кодами. После прочтения входного потока, найдем элемент массива с нечетным числом вхождений и выведем его на экран.