Форум программистов, компьютерный форум CyberForum.ru

Определить, сколько существует различных раскрасок полоски из N клеток - C++

Восстановить пароль Регистрация
 
Brat_OK
0 / 0 / 0
Регистрация: 01.09.2013
Сообщений: 20
25.03.2014, 16:56     Определить, сколько существует различных раскрасок полоски из N клеток #1
Решаю задачу условие на картинке, написал код идею вроде понял, не могу понять почему проходит лишь на частичный балл, помогите разобраться,

Мой код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
 
using namespace std;
 
long long MOD = 1e9+7;
 
 
long long fact (int n)
{
 
    long long res = 1;
 
    for (int i = 2; i <= n; i++)
        res = (res*i) % MOD;
 
    return res;
}
 
int main()
{
   int n,a,b,c,sum;
 
 
    cin >> n >> a >> b >> c;
 
    sum = a + b + c;
 
 
    if (sum == 0 || sum > n)
        {
            cout << 0;
            return 0;
        }
 
    cout << fact(sum);
 
 
}
Миниатюры
Определить, сколько существует различных раскрасок полоски из N клеток  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.03.2014, 16:56     Определить, сколько существует различных раскрасок полоски из N клеток
Посмотрите здесь:

Дано слово. определить сколько различных букв в нем C++
C++ из листа клетчатой бумаги N*N клеток вырезали М клеток . на сколько кусков распадается оставшаяся часть листа?
C++ Задано слово. Определить, сколько в нем различных символов.
C++ Определить сколько различных символов в каждом слове введенного с клавиатуры текста
C++ Определить, сколько различных букв имеется в предложении
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Man2201
 Аватар для Man2201
75 / 75 / 4
Регистрация: 25.04.2010
Сообщений: 296
25.03.2014, 17:02     Определить, сколько существует различных раскрасок полоски из N клеток #2
Для случая когда входные данные 3 2 1 0 правильный ответ - 3, Ваша программа выдаст 6. У Вас не совсем правильная формула.
Brat_OK
0 / 0 / 0
Регистрация: 01.09.2013
Сообщений: 20
25.03.2014, 17:09  [ТС]     Определить, сколько существует различных раскрасок полоски из N клеток #3
Так правильно? А нет, так тоже не правильно получается)
Тогда как же считать?
Изображения
 
Man2201
 Аватар для Man2201
75 / 75 / 4
Регистрация: 25.04.2010
Сообщений: 296
25.03.2014, 17:46     Определить, сколько существует различных раскрасок полоски из N клеток #4
Минуту, сейчас напишу

Добавлено через 9 минут
Сначала разместим красные, их минимум А, вариантов размещения
N!/(A! * (N-A)!)
аналогично зеленые
(N-A)!/(B! *(N-A-B)!)
и синие
(N-A-B)!/(C!*(N-A-B-C)!)
остальные (N-A-B-C) раскрашиваем в любой цвет. Таких вариантов 3^(N-A-B-C).
Тогда конечная формула:
(N!/(A!*B!*C!*(N-A-B-C)!))* 3^(N-A-B-C).
Кажется так, хотя могу ошибаться. В случаях когда N = A+B+C точно правильная. В остальных еще надо допроверить, хотя по логике все так.
Надо доопределить факториал, что 0! = 1 и факториал от отрицательного числа равен 0

Добавлено через 11 минут
Нет, для случая N != A+B+C не подходит, включаются повторения. Сейчас додумаю
Brat_OK
0 / 0 / 0
Регистрация: 01.09.2013
Сообщений: 20
25.03.2014, 17:47  [ТС]     Определить, сколько существует различных раскрасок полоски из N клеток #5
Переписал код, при тесте 3 0 0 0 выдает 27, то ли я накосячил где-то то ли в фомуле что то не так...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
 
using namespace std;
 
long long MOD = 1e9+7;
 
 
long long fact (int n)
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
 
    long long res = 1;
 
    for (int i = 2; i <= n; i++)
        res = (res*i) % MOD;
 
    return res;
}
 
int main()
{
   int n,a,b,c,sum, m;
 
 
    cin >> n >> a >> b >> c;
 
 
    cout << (fact(n)/(fact(a)*fact(b)*fact(c)*fact(n-a-b-c))) * pow(3,n-a-b-c);
 
}
Man2201
 Аватар для Man2201
75 / 75 / 4
Регистрация: 25.04.2010
Сообщений: 296
25.03.2014, 17:55     Определить, сколько существует различных раскрасок полоски из N клеток #6
Как раз тут все правильно, 27 вариантов раскраски
Brat_OK
0 / 0 / 0
Регистрация: 01.09.2013
Сообщений: 20
25.03.2014, 17:58  [ТС]     Определить, сколько существует различных раскрасок полоски из N клеток #7
Написал код вроде работает, можете привести для него контр тест на котором он может лечь?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
 
using namespace std;
 
long long MOD = 1e9+7;
 
 
long long fact (int n)
{
 
    long long res = 1;
 
    for (int i = 2; i <= n; i++)
        res = (res*i) % MOD;
 
    return res;
}
 
int main()
{
   int n,a,b,c,sum, m;
 
 
    cin >> n >> a >> b >> c;
 
    if (n < a+b+c || a+b+c == 0)
        {
            cout << 0;
            return 0;
       }
 
 
    if (a > 0 && b > 0 && c > 0)
    {
     m = min(c,min(a,b));
     sum = m * 3;
    }
    else if (a > 0 && b > 0 && c == 0)
    {
        m = min(a,b);
        sum = m*2;
    }
    else if (a > 0 && c > 0 && b == 0)
    {
        m = min(a,c);
        sum = m*2;
    }
    else if (b > 0 && c > 0 && a == 0)
    {
        m = min(b,c);
        sum = m*2;
    }
    else
        {
            cout << 1;
            return 0;
        }
 
 
    int r= 0;
 
    if (a >= m)
        r += a-m;
    if (b >= m)
        r += b-m;
    if (c >= m)
        r += c-m;
 
    cout << fact(sum)+r;
 
 
}
Добавлено через 2 минуты
При тесте 3 0 0 0, ответ 27?
Откуда там краска, там же нет клеток с краской?
Или я чего то не понял?
Man2201
 Аватар для Man2201
75 / 75 / 4
Регистрация: 25.04.2010
Сообщений: 296
25.03.2014, 18:06     Определить, сколько существует различных раскрасок полоски из N клеток #8
Вы немного не поняли условие задачи
В случае 3 0 0 0 не говорится что клеток нету, говорится что нету минимального количества цветов, то есть любая раскраска подходит, а всего 27 раскрасок

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream.h>
int fact(int n)
{
    if(n==0) return(1);
    if(n<0) return(0);
    int f = 1;
    for(int i=2;i<=n;i++)
        f = f*i;
    return(f);
    }
int main()
{
    int N,A,B,C;
    cin>>N>>A>>B>>C;
    int result = 0;
    for(int i = A;i <=N; i++)
       for(int j = B; j<=N; j++)
          for( int k = C; k<=N; k++)
              if(i+j+k == N)
                 result = result+fact(N)/fact(i)/fact(j)/fact(k);
    cout<<result<<endl;
    system("pause");
    }
Добавлено через 1 минуту
этот код работает правильно, только немного по принципу полного перебора. если такой сойдет - остановимся, если надо через комбинаторику вывести формулу - будем дальше думать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2014, 21:25     Определить, сколько существует различных раскрасок полоски из N клеток
Еще ссылки по теме:

Определить сколько различных символов в каждом слове C++
Определить, сколько различных букв в слове C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Brat_OK
0 / 0 / 0
Регистрация: 01.09.2013
Сообщений: 20
25.03.2014, 21:25  [ТС]     Определить, сколько существует различных раскрасок полоски из N клеток #9
Данный способ, не совсем корректен, задача проходит лишь частичный балл...

Добавлено через 7 минут
Добавил вычисление по модулю все ок, но на больших тестах идет завал по времени, так что видимо нужна формула...Обычный перебор не подходит
Yandex
Объявления
25.03.2014, 21:25     Определить, сколько существует различных раскрасок полоски из N клеток
Ответ Создать тему
Опции темы

Текущее время: 08:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru