1482 / 946 / 811
Регистрация: 30.04.2016
Сообщений: 3,306
1

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

08.05.2017, 23:05. Показов 4089. Ответов 15
Метки нет (Все метки)

Здравствуйте! Вот еще одна задача с 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?) Как там поведут себя биты...Ума не приложу.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.05.2017, 23:05
Ответы с готовыми решениями:

Найти максимальное количество одинаковых чисел, идущих подряд
Дан массив A(n). Найти максимальное количество одинаковых чисел, идущих подряд.

Дан текст, содержащий цифры. Найти наибольшее количество идущих подряд цифр
дан текст содержащий цифры.найти наибольшее количество идущих подряд цифр

Найти, сколько шестизначных чисел в четверичной системе не содержат двух одинаковых цифр, идущих подряд?
Собственно, вот такая задача... Нужно очень срочно, заранее спасибо за любую помощь!

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

15
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
08.05.2017, 23:18 2
Снова неправильный подход. Нужно дп.
0
21 / 21 / 10
Регистрация: 11.09.2015
Сообщений: 103
09.05.2017, 00:00 3
Fixer_84, может регулярные выражения сработают?
0
1482 / 946 / 811
Регистрация: 30.04.2016
Сообщений: 3,306
09.05.2017, 00:04  [ТС] 4
Kudryashov_R_D, здравствуйте! Может быть, не пробовал. Тут эта функция на каждом шаге проверяет. Будет ли это быстрее. Попробую.

Добавлено через 2 минуты
Ромаха, здравствуйте! Да, я думал, что размещения с повторениями сработают. Раньше меня эта рекурсия выручала. В этот раз все сложнее. Вы правы, скорее всего, придется менять алгоритм. Может как-то попробовать через двузначные числа...Там вместо 1 и 2 будет 0 и 1. Но с ними тоже не работал. Не знаю.
0
21 / 21 / 10
Регистрация: 11.09.2015
Сообщений: 103
09.05.2017, 00:24 5
Или попробуй сравнивать substr (s, i+1, 2) == "11" или substr (s, i+1, 2) == "22", если s[i] = '1' или '2'
0
1482 / 946 / 811
Регистрация: 30.04.2016
Сообщений: 3,306
09.05.2017, 00:43  [ТС] 6
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.
0
21 / 21 / 10
Регистрация: 11.09.2015
Сообщений: 103
09.05.2017, 02:49 7
А может делать проверку только одного очередного 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 минут
Нет, этот код выдаёт лишние числа
0
4642 / 2155 / 272
Регистрация: 01.03.2013
Сообщений: 5,738
Записей в блоге: 22
09.05.2017, 03:11 8
А мы без ДП и прочих ужасов, с наивным однострочником:
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';}
Получили следующие результаты:
Код
Лимит времени 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
И при этом со свистом влезаем в ограничения как по времени, так и по памяти. Что я делаю не так?
1
21 / 21 / 10
Регистрация: 11.09.2015
Сообщений: 103
09.05.2017, 03:47 9
А вот так работает
Кликните здесь для просмотра всего текста

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 минут
Но это не задача с олимпиады!
1
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
09.05.2017, 13:38 10
Цитата Сообщение от _Ivana Посмотреть сообщение
с наивным однострочником:
Лол.
Пишешь код в одну строку, называешь однострочником, ликуешь. - неплохой план

Это и есть дп(ну как дп). Только без запоминания. А эт уже не очень
0
4642 / 2155 / 272
Регистрация: 01.03.2013
Сообщений: 5,738
Записей в блоге: 22
09.05.2017, 14:54 11
Ну для обоснованного ликования надо чтобы кот при этом влезал в эту одну строчку экрана.

А ДП это будет когда (если) мемоизацию прикрутить. И в данном случае это более чем тривиально (банальный массив 30*2). Но и без него для n=30 неплохо получилось, особенно на фоне остального ужаса, написанного в теме - который и есть лол (в сравнении с).
0
1482 / 946 / 811
Регистрация: 30.04.2016
Сообщений: 3,306
09.05.2017, 15:33  [ТС] 12
Спасибо всем! А вообще, не имея решения _Ivana, я бы дальше действовал так: У меня программа считает для N <= 20. И я получаю вот такую последовательность: 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892... Ее, возможно, можно расшифровать и сделать несложное решение. Вот этим сейчас и займусь
0
4642 / 2155 / 272
Регистрация: 01.03.2013
Сообщений: 5,738
Записей в блоге: 22
09.05.2017, 15:38 13
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Ее, возможно, можно расшифровать и сделать несложное решение.
О, на фоне общего буйства лола в теме всплывают признаки здравомыслия... https://oeis.org/search?q=2%2C... 1%81%D0%BA
0
1482 / 946 / 811
Регистрация: 30.04.2016
Сообщений: 3,306
09.05.2017, 16:01  [ТС] 14
Получается, что каждый последующий равен сумме двух предыдущих. Вот и все

Добавлено через 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;
}
0
21 / 21 / 10
Регистрация: 11.09.2015
Сообщений: 103
09.05.2017, 17:18 15
Если решать "в лоб", то количество 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
4642 / 2155 / 272
Регистрация: 01.03.2013
Сообщений: 5,738
Записей в блоге: 22
09.05.2017, 18:04 16
Цитата Сообщение от 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);
    }
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.05.2017, 18:04

Сколько среди 5-значных чисел таких, в которых подряд не менее 4 одинаковых цифр?
доброго здоровья всем знатокам! посоветуйте правильное решение задачи: с формулой! Есть какое...

Сколько существует 6-значных чисел, у которых нет одинаковых цифр, а 2 и 4 цифры - нечётные?
1) Сколько существует 6-значных чисел, у которых нет одинаковых цифр, а 2 и 4 цифры - нечётные?

Подсчитать количество одинаковых чисел массива, идущих подряд
program qwe; const n=20; var arr: array of integer; i:integer; count:byte; begin ...

Сколько шестизначных чисел в четверичной системе не содержат двух одинаковых цифр, идущих подряд
Найти, сколько шестизначных чисел в четверичной системе не содержат двух одинаковых цифр, идущих...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.