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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
06.07.2014, 13:33     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #1
Задание:
В День флага России владелец магазина решил украсить свою витрину полосками ткани белого, синего и красного цветов. Он хочет, чтобы выполнялись следующие условия:
  1. Полоски одного цвета не должны располагаться рядом друг с другом.
  2. Синяя полоска может быть расположена только между белой и красной или между красной и белой.

Определите количество способов выполнить желание владельца магазина.

Исходные данные:
N — количество полосок, 1 ≤ N ≤ 45.
Результат:
M — количество способов украсить витрину.
http://acm.timus.ru/problem.aspx?space=1&num=1225

Я подумала, что у нас есть 2 изначальных варианта (б - белый, к - красный): бкбкбк... и кбкбкб... И уже в эти варианты мы вставляем синий между белым и красным - сначала один синий во всю цепочку, потом 2 синих и т.д., т.е. у нас есть сочетания по 1, по 2 и т.д. из n-2. Но это абсолютно неправильно - даже первый тест не проходит. Почему?

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
#include <iostream>
using std::cin;
using std::cout;
 
#define I unsigned __int64
 
I C(int n, int k)
{
    I res = 1;
    for (int i = 1; i <= k; i++)
        res *= n - k + i;
    for (int i = 1; i <= k; i++)
        res /= i; // делим отдельно, чтобы точно не должно было возникнуть дробных чисел
    return res;
}
 
int main()
{
    int n;
    cin >> n;
    I res = 0;
    for (int i = 0; i <= n-2; i++)
        res += C(n-2, i);
    cout << 2*res; // два варианта цепочки
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2014, 13:33     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
Посмотрите здесь:

C++ Определить количество отрицательных элементов, расположенных вы-ше главной диагонали матрицы.
C++ Для вещественных массивов a и b определить максимальное количество подряд расположенных элементов
C++ Определить количество четных элементов, расположенных на главной и побочной диагоналях матрицы
Определить количество отрицательных элементов, расположенных выше главной диагонали матрицы C++
Из двухмерного массива сформировать одномерный по определенной схеме C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 15:18     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #2
Не проверял на правильность весь алгоритм, но при N=1 выводит 0, хотя должно по идее быть 3.
Я бы вообще сделал эту задачу методом динамического программирования и не мучился б)
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
06.07.2014, 15:49  [ТС]     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #3
Dani, при 1 должно быть 2, но ясно что что-то неправильно. Поставила проверку конкретно на 1 и 2, теперь первые 3 теста проходит.
Динамическое еще не освоила, спасибо что напомнил, давно хотела
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 15:53     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #4
Керра, ах, да. Синий - между красным и белым. Тогда - точно, 2. Сейчас попробую описать, как и понимаю ваше (дальше на ты, хорошо? ) решение: ты перебираешь количество синих полос - их количество может быть от 0 и до n-2, потому что... почему? Если у нас всего N полосок, получается одна белая и красная и n-2 синие. И тут получится так, что много синих полосок будут стоять на соседних местах.
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
06.07.2014, 15:58  [ТС]     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #5
Dani, поняла, действительно затупила, ща подумаю

Добавлено через 1 минуту
получается, что до n/2. но опять неправильно.

текущий вариант:
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
#include <iostream>
using std::cin;
using std::cout;
 
#define I unsigned __int64
 
I C(int n, int k)
{
    I res = 1;
    for (int i = 1; i <= k; i++)
        res *= n - k + i;
    for (int i = 1; i <= k; i++)
        res /= i;
    return res;
}
 
int main()
{
    int n;
    cin >> n;
    I res = 0;
    if (n == 1 || n == 2)
        res = 1;
    else
        for (int i = 0; i <= n/2; i++)
            res += C(n-2, i);
    cout << 2*res;
    return 0;
}
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 15:59     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #6
Керра, я уже писал: лучше сделать методом ДП и не мучиться
fio
 Аватар для fio
10 / 10 / 3
Регистрация: 16.06.2014
Сообщений: 45
06.07.2014, 16:00     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #7
Я обещаю, что Флаги невозможно сдать, вычисляя С.
Нужно понять совсем базовое динамическое программирование.
Иначе просто не влезет в ограничения.
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
06.07.2014, 16:01  [ТС]     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #8
но должно же быть точное математическое решение
хотя ДП все равно надо будет осваивать, это да, надо ее в любом случае и так тоже решить

Добавлено через 49 секунд
fio, ок, мерси
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 16:02     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #9
Возможно, если составить решение динамическим программированием, можно получить реккурентное уравнение, решить его и получить одну формулу.
gng
605 / 451 / 122
Регистрация: 08.09.2013
Сообщений: 1,152
06.07.2014, 17:06     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #10
45 полос - это предел для метода тупого перебора, на моем старом нетбуке (селерон 900) считает почти минуту.
C
1
2
3
4
5
6
7
8
9
unsigned long C (int n, int blue) {
  if (n < 2)  return 1;
  return blue ? C (n-1, 0) : C (n-1,0) + C (n-1, 1);
}
main() {
  int n;
  scanf ("%d", &n);
  printf ("%lu\n", 2 * C (n-1, 0));
}
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.07.2014, 18:06     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #11
Под спойлером - ряд, являющийся ответом и формула, как его получить
Кликните здесь для просмотра всего текста
http://oeis.org/A006355
Сначала рассмотрим частные случаи. Для флагов длинны 1 решение очевидно

Попробуем полчить флаги длинны N. Для этого сначала к каждому флагу добавим R/W (это разрешено правилами) - первый синтезированный флаг. Второй флаг может быть получен добавлением B в предпоследнюю позицию (может быть запрещено, поскольку две B рядом недопустимы).

Получим следующий реультат (см вложение):

Как видим, у нас образуются мертвые ветки. Попробуем определить количество живых веток.

Видно, что каждая ветка на предыдущем шаге дает две ветки, из которых отмирают те, у которых предпоследняя буква B. Количество таких букв определяется на шаге N - 3 (текущий шаг N). Получаем общую формулу:

f(1) = 2
f(2) = 2
f(3) = 4
f(n) = f(n - 1) * 2 - f(n - 3)

P.S. Подходит также формула f(n) = f(n - 1) + f(n - 2), но мне уже лень доказывать
Миниатюры
Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме  
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.07.2014, 18:13     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #12
Решения
Кликните здесь для просмотра всего текста
Код #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
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<std::size_t> ans;
 
    ans.push_back(2);
    ans.push_back(2);
    ans.push_back(4);
 
    std::size_t n;
    std::cin >> n;
 
    --n;
 
    for(std::size_t i = 2; i <= n; ++i)
    {
        ans.push_back(ans.at(i) * 2 - ans.at(i - 2));
    }
 
    std::cout << ans.at(n) << std::endl;
 
    return 0;
}
Код #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
int main()
{
    std::size_t prev = 2;
    std::size_t curr = 2;
 
    std::size_t n;
    std::cin >> n;
 
    for(std::size_t i = 2; i < n; ++i)
    {
        std::size_t tmp = curr;
        curr += prev;
        prev = tmp;
    }
 
    std::cout << curr << std::endl;
 
    return 0;
}
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
06.07.2014, 20:12     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #13
Керра, вот ток что сдал комбинаторикой!

C++ (Qt)
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#pragma comment(linker, "/STACK:167177216")
 
#include <stdio.h>
#include <stack>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <memory.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <time.h>
#include <cassert>
#include <cstring>
//#include <unordered_set>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
 
const int INF = 1e9;
const ld eps = 1e-9;
const li MOD = (li)(4e6 + 37);
const li INF64 = (li)(INF) * (li)(INF);
 
const int ddx[] = {-1, 1, 1, -1};
const int ddy[] = {1, 1, -1, -1};
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dxh[] = {-1, -1, -1, 1, 1, 1, 1, -1};
const int dyh[] = {1, -1, -1, -1, -1, 1, 1, 1};
const string dirs[] = {"RIGHT", "UP", "LEFT", "DOWN"};
 
bool in(int i, int j, int n, int m)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}
 
li c[111][111];
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen("errors.txt", "w", stderr);
    //ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
 
    if(n == 1)
    {
        cout << 2 << endl;
        return 0;
    }
 
    for(int i = 1; i <= 100; i++)
    {
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
 
    li ans = 0;
    for(int r = 1; r <= n; r++)
        for(int w = 1; w <= n; w++)
        {
            if(abs(r - w) > 1)
                continue;
            int left = n - r - w;
            if(left < 0)
                continue;
            
            li cur = c[r + w - 1][left];
            if(r == w)
                cur *= 2LL;
            ans += cur;
        }
 
    cout << ans << endl;
    return 0;
}
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
06.07.2014, 20:18     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #14
SlavaSSU, первая половина файла - просто А так вообще это тоже динамика получилась...
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
06.07.2014, 20:19     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #15
Somebody, где ты там динамику увидел? делал так же, как и хотел ТС. поставил сначала красные и белые полоски, и потом вставлял синие всеми возможными способами
gray_fox
06.07.2014, 20:21
  #16

Не по теме:

Цитата Сообщение от SlavaSSU Посмотреть сообщение
C++
1
2
3
4
5
6
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define x first
#define y second
Не надо так...

Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
06.07.2014, 20:23     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #17
Цитата Сообщение от SlavaSSU Посмотреть сообщение
C++
1
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
Ну, я вижу, считается C, но это по сути тоже динамика.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
06.07.2014, 20:26     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #18
Somebody, и че? само решение не динамикой! если в задаче не на динамику будет подзадача(например, найти максимум в массие, и я этот максимум в массиве буду искать динамикой), то ты же не скажешь, что ты динамикой сдал. а так да, С-шки удобно так считать динамикой(треугольник паскаля, если кто не згал)
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 20:38     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #19
Цитата Сообщение от SlavaSSU Посмотреть сообщение
где ты там динамику увидел?
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
Для посчета c[i][j] используются меньшие подзадачи (уже посчитанные значения) c[i-1][j-1] и c[i-1][j]
Цитата Сообщение от gray_fox Посмотреть сообщение
Не надо так...
Это у SlavaSSU такой заранее написанный заголовок для участия в контестах. Такие замены, например, pb вместо push_back, помогают сэкономить время во время турнира и быстрее сдать задачу.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2014, 20:42     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
Еще ссылки по теме:

Определить количество четных элементов, расположенных на главной и побочной диагоналях C++
C++ Определить количество различных комбинаций монет, которые могут сложиться в определенную сумму
Запуск программ по определенной схеме с использованием Fiber и Thread C++

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

Или воспользуйтесь поиском по форуму:
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
06.07.2014, 20:42     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #20
Dani, Dani, да знаю, выше ответил что подсчет Сшек динамикой не в счет! Само решение типа комбинаторное! А ты участвуешь в контестах? У тебя какие ники на codeforces и topcoder? Чето кажется ты крутой да там?
Yandex
Объявления
06.07.2014, 20:42     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
Ответ Создать тему
Опции темы

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