Найти количество N-значных чисел, состоящих из цифр 1 и 2, не содержащих три подряд идущих одинаковых цифры

@Fixer_84 · Регистрация: 30.04.2016

Студворк — интернет-сервис помощи студентам

Здравствуйте! Вот еще одна задача с E-olymp (№ 12). К сожалению, только 67% (один - неправильный ответ, остальные не прошли по времени). Мне пока, хотя бы, выяснить где неправильный ответ

Для решения использовал проверенные функции. А вот моя (IfThree (string s)) - возможно, далеко не идеальна. Прошу Вашей помощи.

Числа

Дикари, живущие на острове невезения умеют считать только до двух. Поэтому у них есть только две цифры — цифра 1 и цифра 2. Кроме того, дикари очень суеверные люди. Числа, в которых стоят подряд три одинаковые цифры, они считают несчастливыми и не используют. Например, число 1221212 можно использовать, так как в нем нет трех подряд идущих одинаковых цифр. А число 12121112 — нельзя. В нем есть три подряд идущие цифры (в этом примере это единицы).

Ваша задача заключается в том, чтобы выяснить, сколько существует N-значных чисел, состоящих только из цифр 1 и 2 таких, что в них нет трех подряд идущих одинаковых цифр .

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

Единственная строка входного файла содержит натуральное число N, 1 ≤ N ≤ 30.

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

Выведите в выходной файл количество N-значных чисел, состоящих из только из цифр 1 и 2, и не содержащих трех подряд идущих одинаковых цифр. Вывод числа должен осуществляться с переводом строки.

Мое решение (для N <= 20 - работает, дальше зависает):

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
#include <iostream>
#include <string>
 
using namespace std;
 
long long k = 0;
 
bool IfThree(string s)
{
    for (int i = 0; i < s.length() - 2; i++)
    {
        if ((s[i] == s[i+1]) && (s[i+1] == s[i+2]))
        {
            return false;
            break;
        }
    }
    return true;
}
 
void F(string str, string s, long long N)
{
    if (s.length() == N)
    {
        if (IfThree(s))
            k++;
        return;
    }
    for (int i = 0; i < str.length(); i++)
    {
        F(str, s + str[i], N);
    }
}
 
void Perm(string str, long long N)
{
    F(str, "", N);
}
 
int main()
{
    long long N;
    cin >> N;
    if (N == 1) k = 1; else Perm("12", N);
    cout << k << endl;
    system("pause");
    return 0;
}

Добавлено через 11 минут
Где неправильный ответ - нашел. При N = 1, k = 2. Как можно оптимизировать это решение?

Добавлено через 27 минут
Все, кажется, сводится к тому, чтобы быстро проверить, содержит ли одна из комбинаций три подряд идущие 2 или 1. Я сделал это с помощью функции IsThree(). Можно как-то ее оптимизировать?

Добавлено через 17 минут
Сделал так, но лучше не стало. По-прежнему 9 тестов из 30 не проходят по времени. Кажется дело в основном алгоритме:

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
#include <iostream>
#include <string>
 
using namespace std;
 
int k = 0;
 
void F(string str, string s, int N)
{
    if (s.length() == N)
    {
        if ((s.find("111") == string::npos) && (s.find("222") == string::npos))
            k++;
        return;
    }
    for (int i = 0; i < str.length(); i++)
    {
        F(str, s + str[i], N);
    }
}
 
void Perm(string str, int N)
{
    F(str, "", N);
}
 
int main()
{
    int N;
    cin >> N;
    if (N == 1) k = 2; else Perm("12", N);
    cout << k << endl;
    system("pause");
    return 0;
}

Добавлено через 2 минуты
Может, наоборот, посчитать те, которые содержат 111 или 222 и вычесть их из общего количеcтва? Но будет ли так быстрее...

Добавлено через 8 минут
Может как-то применить алгоритм для двузначного числа...(0100101 - использовать вместо 1 и 2?) Как там поведут себя биты...Ума не приложу.

@Ромаха · 08.05.2017, 23:18

Снова неправильный подход. Нужно дп.

@Kudryashov_R_D · 09.05.2017, 00:00

Fixer_84, может регулярные выражения сработают?

@Fixer_84 · 09.05.2017, 00:04 **[ТС]**

Kudryashov_R_D, здравствуйте! Может быть, не пробовал. Тут эта функция на каждом шаге проверяет. Будет ли это быстрее. Попробую.

Добавлено через 2 минуты
Ромаха, здравствуйте! Да, я думал, что размещения с повторениями сработают. Раньше меня эта рекурсия выручала. В этот раз все сложнее. Вы правы, скорее всего, придется менять алгоритм. Может как-то попробовать через двузначные числа...Там вместо 1 и 2 будет 0 и 1. Но с ними тоже не работал. Не знаю.

@Kudryashov_R_D · 09.05.2017, 00:24

Или попробуй сравнивать substr (s, i+1, 2) == "11" или substr (s, i+1, 2) == "22", если s[i] = '1' или '2'

@Fixer_84 · 09.05.2017, 00:43 **[ТС]**

Kudryashov_R_D, Сделал так. ничего не изменилось:

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
#include <iostream>
#include <string>
 
using namespace std;
 
bool IfThree(string s)
{
for (int i = 0; s[i]; i++)
{
if ((s.substr(i, 3) == "111") || (s.substr(i, 3) == "222")) 
{
return false;
break;
}
}
return true;
}
 
int k = 0;
 
void F(string str, string s, int N)
{
    if (s.length() == N)
    {
        if (IfThree(s))
            k++;
        return;
    }
    for (int i = 0; i < str.length(); i++)
    {
        F(str, s + str[i], N);
    }
}
 
void Perm(string str, int N)
{
    F(str, "", N);
}
 
int main()
{
    int N;
    cin >> N;
    if (N == 1) k = 2; else Perm("12", N);
    cout << k << endl;
    system("pause");
    return 0;
}

А это вы о чем выше, не понимаю...Я перебираю все комбинации и ищу без трех 111 или 222.

@Kudryashov_R_D · 09.05.2017, 02:49

А может делать проверку только одного очередного i-го символа и в зависимости от его значения передавать проверку следующего i+1 одной из функций, "знающих" о двух предшествующих символах: Prev11 (i), Prev22(i), Prev12(i), Prev21(i).

Добавлено через 36 минут
Вместо 4 функций можно использовать switch (ij), где ij = 11, 22, 12 или 21.

Добавлено через 1 час 16 минут
Например

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
void main () {
  const int N = 5;
  string str =
  "12121" "21212" "12" "2211" "11212" "12";
  cout << str.data() << "\n";
  unsigned i = 0; unsigned j = 0; int ij = -1;
  while (j < str.size()) {
    if (ij < 0) {
      if (j + N >= str.size())
        break;
      ij = (str[j] == '1' ? 10 : 20)
         + (str[j+1] == '1' ? 1 : 2);
      i = j;
      j += 2;
    }
    switch (ij) {
    case 11:
      if (str[j] == '1')
        i = j - 1;
      else if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1; 
      }
      break;
    case 22:
      if (str[j] == '2')
        i = j - 1;
      else if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1;
      }
      break;
    case 12:
      if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1; 
      } else
        ij = str[j] == '1' ? 21 : 22;
      break;
    case 21:
      if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1; 
      } else
        ij = str[j] == '1' ? 11 : 12;
      break;
    }
    ++j;
  }
}

Добавлено через 11 минут
Нет, этот код выдаёт лишние числа

@_Ivana · 09.05.2017, 03:11

А мы без ДП и прочих ужасов, с наивным однострочником:

C++
1
2
3
4
5
#include <iostream>
 
int f(int n, int k) { return k>2 ? 0 : n==0 ? 1 : f(n-1, k+1) + f(n-1, 1); }
 
int main() {int n; std::cin >> n; std::cout << f(n, 0) << '\n';}

Получили следующие результаты:

Code
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
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
 
# 1 Засчитано  2,27 ms 1 640 KiB
# 2 Засчитано  1,89 ms 1 552 KiB
# 3 Засчитано  1,84 ms 1 652 KiB
# 4 Засчитано  1,69 ms 1 756 KiB
# 5 Засчитано  1,77 ms 1 628 KiB
# 6 Засчитано  1,82 ms 1 668 KiB
# 7 Засчитано  1,77 ms 1 796 KiB
# 8 Засчитано  1,73 ms 1 788 KiB
# 9 Засчитано  1,70 ms 1 644 KiB
# 10 Засчитано 1,76 ms 1 744 KiB
# 11 Засчитано 1,71 ms 1 672 KiB
# 12 Засчитано 1,72 ms 1 736 KiB
# 13 Засчитано 1,71 ms 1 572 KiB
# 14 Засчитано 1,71 ms 1 576 KiB
# 15 Засчитано 1,72 ms 1 744 KiB
# 16 Засчитано 1,79 ms 1 584 KiB
# 17 Засчитано 1,81 ms 1 660 KiB
# 18 Засчитано 1,77 ms 1 672 KiB
# 19 Засчитано 1,89 ms 1 744 KiB
# 20 Засчитано 1,84 ms 1 728 KiB
# 21 Засчитано 1,98 ms 1 664 KiB
# 22 Засчитано 2,10 ms 1 564 KiB
# 23 Засчитано 2,35 ms 1 664 KiB
# 24 Засчитано 2,69 ms 1 660 KiB
# 25 Засчитано 3,41 ms 1 796 KiB
# 26 Засчитано 4,25 ms 1 580 KiB
# 27 Засчитано 6,49 ms 1 636 KiB
# 28 Засчитано 7,86 ms 1 644 KiB
# 29 Засчитано 11,82 ms    1 740 KiB
# 30 Засчитано 17,86 ms    1 664 KiB
30 (100 %)  3,22 ms / 17,86 ms  1 672 KiB / 1 796 KiB

И при этом со свистом влезаем в ограничения как по времени, так и по памяти. Что я делаю не так?

@Kudryashov_R_D · 09.05.2017, 03:47

А вот так работает

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
void main () {
  const int N = 5;
  string str =
   "12121" "21212" "12" "221" "1" "11212" "12";
  cout << str.data() << "\n";
  unsigned i = 0; unsigned j = 0; int ij = -1;
  while (j < str.size()) {
    if (ij < 0) {
      if (j + N >= str.size())
        break;
      ij = (str[j] == '1' ? 10 : 20)
         + (str[j+1] == '1' ? 1 : 2);
      i = j;
      j += 2;
    }
    switch (ij) {
    case 11:
      if (str[j] == '1')
        i = j - 1;
      else if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1; 
      } else
        ij = 12;
      break;
    case 22:
      if (str[j] == '2')
        i = j - 1;
      else if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1;
      } else
        ij = 21;
      break;
    case 12:
      if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1; 
      } else
        ij = str[j] == '1' ? 21 : 22;
      break;
    case 21:
      if (j-i+1 == N) {
        cout << str.substr (i, N) << "\n";
        ij = -1; 
      } else
        ij = str[j] == '1' ? 11 : 12;
      break;
    }
    ++j;
  }
}

Добавлено через 20 минут
Но это не задача с олимпиады!

@Ромаха · 09.05.2017, 13:38

Сообщение от _Ivana

с наивным однострочником:

Лол.
Пишешь код в одну строку, называешь однострочником, ликуешь. - неплохой план

Это и есть дп(ну как дп). Только без запоминания. А эт уже не очень

@_Ivana · 09.05.2017, 14:54

Ну для обоснованного ликования надо чтобы кот при этом влезал в эту одну строчку экрана.

А ДП это будет когда (если) мемоизацию прикрутить. И в данном случае это более чем тривиально (банальный массив 30*2). Но и без него для n=30 неплохо получилось, особенно на фоне остального ужаса, написанного в теме - который и есть лол (в сравнении с).

@Fixer_84 · 09.05.2017, 15:33 **[ТС]**

Спасибо всем! А вообще, не имея решения _Ivana, я бы дальше действовал так: У меня программа считает для N <= 20. И я получаю вот такую последовательность: 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892... Ее, возможно, можно расшифровать и сделать несложное решение. Вот этим сейчас и займусь

@_Ivana · 09.05.2017, 15:38

Сообщение от Fixer_84

Ее, возможно, можно расшифровать и сделать несложное решение.

О, на фоне общего буйства лола в теме всплывают признаки здравомыслия...

https://oeis.org/search?q=2%2C... 1%81%D0%BA

@Fixer_84 · 09.05.2017, 16:01 **[ТС]**

Получается, что каждый последующий равен сумме двух предыдущих. Вот и все

Добавлено через 17 минут
Вот грубое и на скорую руку решение с использованием массивов (M = 30, можно больше). Довольно быстро работает!

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
#include <iostream>
 
using namespace std;
 
int main()
{
    const int M = 30;
    int A[M];
    int N;
    cin >> N;
    A[0] = 2;
    A[1] = 4;
    if (N == 1)
        cout << A[0] << endl;
    else if (N == 2)
        cout << A[1] << endl;
    else
    {
        for (int i = 2; i < M; i++)
        {
            A[i] = A[i-1] + A[i-2];
            if (i == N - 1)
            {
                cout << A[i] << endl;
                break;
            }
        }
    }
    system("pause");
    return 0;
}

@Kudryashov_R_D · 09.05.2017, 17:18

Если решать "в лоб", то количество N-разрядных чисел из 0/1, не содержащих подряд 3-х нулей или единиц - Q(N), равно разности всех N-разрядных чисел 2^N минус удвоенное количество групп из 0 или 1 от 3 до N в группе, соседствующие либо с границей числа, либо с 1 или 0 (например, 3-х групп 0000,0001,1000 для N=4 и т.д.). Для N=3,4,5 искомое Q(N) легко вычислить на бумаге. И вариант N=6 тоже не труден. Если положиться на Q(N) = Q(N-1)+Q(N-2), то счёт элементарен. Хотя эта индукция не доказана.
Но откуда _Ivana взяла свою рекуррентную формулу - вот что мучает такого профана, как я!
Ссылка на oeis.org/search?q= ... не много мне дала.

@_Ivana · 09.05.2017, 18:04

Сообщение от Kudryashov_R_D

Но откуда _Ivana взяла свою рекуррентную формулу - вот что мучает такого профана, как я!

А вы стесняетесь прямо спросить?

Эта формула родилась в результате оптимизации исходной рекурсивной функции, которую я написал прямо по условию задачи - вот она (напишу в более традиционном виде, если последовательные тернарные операторы смущают некоторых участников):

C++
1
2
3
4
5
6
7
int g(int n, int d, int k) {
    if (k>2) return 0;
    else if (n==0) return 1;
    else {
        return g(n-1, 1, d==1 ? k+1 : 1) + g(n-1, 2, d==2 ? k+1 : 1);
    }
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	08.05.2017, 23:18
	Снова неправильный подход. Нужно дп. 0

@Kudryashov_R_D 21 / 21 / 10 Регистрация: 11.09.2015 Сообщений: 103
	09.05.2017, 00:00
	Fixer_84, может регулярные выражения сработают? 0

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337
	09.05.2017, 00:04 [ТС]
	Kudryashov_R_D, здравствуйте! Может быть, не пробовал. Тут эта функция на каждом шаге проверяет. Будет ли это быстрее. Попробую. Добавлено через 2 минуты Ромаха, здравствуйте! Да, я думал, что размещения с повторениями сработают. Раньше меня эта рекурсия выручала. В этот раз все сложнее. Вы правы, скорее всего, придется менять алгоритм. Может как-то попробовать через двузначные числа...Там вместо 1 и 2 будет 0 и 1. Но с ними тоже не работал. Не знаю. 0

@Kudryashov_R_D 21 / 21 / 10 Регистрация: 11.09.2015 Сообщений: 103
	09.05.2017, 00:24
	Или попробуй сравнивать substr (s, i+1, 2) == "11" или substr (s, i+1, 2) == "22", если s[i] = '1' или '2' 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	09.05.2017, 14:54
	Ну для обоснованного ликования надо чтобы кот при этом влезал в эту одну строчку экрана. А ДП это будет когда (если) мемоизацию прикрутить. И в данном случае это более чем тривиально (банальный массив 30*2). Но и без него для n=30 неплохо получилось, особенно на фоне остального ужаса, написанного в теме - который и есть лол (в сравнении с). 0

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337
	09.05.2017, 15:33 [ТС]
	Спасибо всем! А вообще, не имея решения _Ivana, я бы дальше действовал так: У меня программа считает для N <= 20. И я получаю вот такую последовательность: 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892... Ее, возможно, можно расшифровать и сделать несложное решение. Вот этим сейчас и займусь 0

@Kudryashov_R_D 21 / 21 / 10 Регистрация: 11.09.2015 Сообщений: 103
	09.05.2017, 17:18
	Если решать "в лоб", то количество N-разрядных чисел из 0/1, не содержащих подряд 3-х нулей или единиц - Q(N), равно разности всех N-разрядных чисел 2^N минус удвоенное количество групп из 0 или 1 от 3 до N в группе, соседствующие либо с границей числа, либо с 1 или 0 (например, 3-х групп 0000,0001,1000 для N=4 и т.д.). Для N=3,4,5 искомое Q(N) легко вычислить на бумаге. И вариант N=6 тоже не труден. Если положиться на Q(N) = Q(N-1)+Q(N-2), то счёт элементарен. Хотя эта индукция не доказана. Но откуда _Ivana взяла свою рекуррентную формулу - вот что мучает такого профана, как я! Ссылка на oeis.org/search?q= ... не много мне дала. 0