Поиск чисел

@0xFFF · Регистрация: 20.10.2020

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

Здравствуйте, прошу помощи с задачей.

На вход дается число n, необходимо найти все n-разрядные числа, которые удовлетворяют следующему условию: среди соседних пар цифр числа нет пар, где одна цифра четная, а другая кратна трем.

Например, число 1234 не подойдет, потому что есть пара 23, где одна цифра кратная трем, а другая четная, а вот например число 567 подойдет.

Собственно, сам вопрос, сейчас я решаю задачу полным перебором всех пар чисел для каждого числа, но по условию задачи n <= 22, а перебор всех пар 22-значного числа занимает слишком много времени (ограничение три секунды). Возможно есть какое-то более оптимальное решение?

Пример
Ввод:
3
Вывод:
446

@vantfiles · 11.03.2021, 09:01

Сообщение от 0xFFF

необходимо найти все n-разрядные числа

Может быть нужно найти их количество?

Добавлено через 3 минуты

Сообщение от 0xFFF

число 1234 не подойдет

1134 тоже не подойдет? То есть порядок следования четных и кратных трем неважен?

Добавлено через 10 минут
Да, есть способ.

Нужно найти количество всех "неподходящих" двузначных чисел XX.

тогда их количество будет равно XX + XX*10 + XX*100 ...

Добавлено через 17 минут
И даже цикл крутить не надо, если вынести XX за скобку, получится репьюнит, а для его получения есть формула:

https://ru.wikipedia.org/wiki/Репьюниты

@0xFFF · 11.03.2021, 09:05 **[ТС]**

vantfiles,
Да, нужно найти их количество, немного неточно указал. Порядок кратных трем и четных неважен, то есть не подойдёт как 34, так и 43.
А насчёт вашего предложения, я тоже об этом думал, но нам же нужно тогда отдельно обрабатывать крайние левые разряды числа, потому что число например 108 нам не подойдёт, ведь ноль кратен трем, а 080 учитыватьсься не будет, поскольку нужны числа без ведущих нулей.
Как, например, применить этот способ для числа из примера n = 3?

@vantfiles · 11.03.2021, 09:23

Двузначные тоже не надо циклом искать, их количество равно 2 * ( 5 * 3 ) - 1
Минус один, потому что 66 попадает в обе группы

Добавлено через 2 минуты

Сообщение от 0xFFF

n = 3

2 * ( 5 * 3 ) - 1 = 29

29 + 29 * 10 = 319

Итого 1000 - 319 = 691

Добавлено через 2 минуты
Не, запутался не так, считать придется...

Добавлено через 5 минут
Нам не подходят:

20
23
26
...

Вобщем их надо подсчитать, а 00, 02, 04 ... не учитывать, поскольку их лидирующий ноль не учитывается.

@0xFFF · 11.03.2021, 09:34 **[ТС]**

А почему они не учитываются? Да у них ведущий ноль, но число 104 также не подойдёт, так и 109

@vantfiles · 11.03.2021, 09:50

20 23 26 29
30 32 34 36 38
40 43 46 49
60 62 63 64 66 68 69
80 83 86 89
90 92 94 96 98

Ничего не пропустил?

Добавлено через 7 минут
Да, алгоритм посложнее получается...

@Shamil1 · 11.03.2021, 10:08

Новая цифра зависит только от предыдущей.
Мы считаем количество двухзначных чисел (включая 01 и т.п.), начинающихся с цифр 0-9. Затем, используя эту информацию, считаем количество трехзначных чисел (включая 01 и т.п.), начинающихся с цифр 0-9.

Добавлено через 9 минут
В первом варианте мы создаём матрицу 10xN. Заполняем первый столбец "1". Для каждой ячейки второго столбца суммируем все разрешённые цифры первого столбца.

Матрицу можно заменить на два массива - "предыдущий" и "текущий".

@vantfiles · 11.03.2021, 11:08

Из-за чисел 00 02 04 06 08 нужно учитывать лидирующие числа тоже:

xxx00 -- 999 чисел
xx00x -- 990 чисел
x00xx -- 900 чисел

Ну и для остальных этот подсчет придется делать тоже

Добавлено через 11 минут

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

начинающихся с цифр 0-9.

30 участвует в подсчете, а 030 уже нет

Добавлено через 46 минут

Сообщение от 0xFFF

Пример
Ввод:
3
Вывод:
446

0xFFF, Вы не могли бы подсказать, какие числа получаются для 2, 3, 4 и 5 ?

@LegionK · 11.03.2021, 15:24

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
#define ll unsigned long long
 
int main()
{
    ll n;
    cin >> n;
 
    vector<vector<ll>>dp(n,vector<ll>(10));
 
    for(ll i = 1;i<=9;++i)dp[0][i] += 1;
 
    for(ll i = 1;i<n;++i){
 
        for(ll j = 0;j<=9;++j){
 
            for(ll a = 0;a<=9;++a){
 
                ll ok = 1;
                if(a % 2 == 0 && j % 3 == 0)ok = 0;
                if(a % 3 == 0 && j % 2 == 0)ok = 0;
 
                if(ok)dp[i][j] += dp[i-1][a];
 
            }
 
        }
 
    }
 
    ll sum = 0;
 
    for(ll i = 0;i<=9;++i)sum += dp.back()[i];
 
    cout << sum;
 
 
 
    return 0;
}

@Shamil1 · 11.03.2021, 15:46

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

30 участвует в подсчете, а 030 уже нет

040 участвует в подсчёте, так как является валидным аффиксом для n-значного числа.

Строка 1:
Содержит 1 для всех цифр, так как есть ровно 1 способ получить такой аффикс.

Строка 2:
Для 0 содержит 7. Это сумма чисел в строке 1, кроме ячеек для цифр 3, 6, 9. То есть, имеем 7 валидных аффиксов длины 2, начинающихся с цифры 0.
Для 1 содержит 10 (10 валидных аффиксов).
И так далее.

Добавлено через 19 минут
з.ы. Я не понял, 0 кратен трём или нет?

@vantfiles · 11.03.2021, 16:02

LegionK, для двойки выдается 61 - а это не так, несложно подсчитать руками.

Сообщение от 0xFFF

поскольку нужны числа без ведущих нулей.

@Shamil1 · 11.03.2021, 16:04

Экспериментальным путём вычислил, что ноль кратен трём.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Main()
{
    Console.WriteLine(Solve(3));
}
 
int Solve(int n)
{
    int[] a = Enumerable.Repeat(1, 10).ToArray();
 
    for (int i = 1; i < n; i++)
    {
        a = Enumerable.Range(0, 10).Select(j => a.Where((x, k) => IsValid(k, j)).Sum()).ToArray();
 
        Console.WriteLine($"i = {i}: [{string.Join(",", a)}]");
    }
 
    return a.Skip(1).Sum();
}

Вывод:

Code
1
2
3
i = 1: [3,10,6,5,6,10,3,10,6,5]
i = 2: [30,64,48,40,48,64,30,64,48,40]
446

@Shamil1 · 11.03.2021, 16:13

Без отладочной печати в консоль получается примерно так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
void Main()
{
    Console.WriteLine(Solve(3));
}
 
int Solve(int n) =>
    Enumerable.Range(0, n-1).Aggregate(Enumerable.Repeat(1, 10).ToArray(), 
        (acc,i) => Enumerable.Range(0, 10).Select(j => acc.Where((x, k) => IsValid(k, j)).Sum()).ToArray())
        .Skip(1).Sum();
 
bool IsValid(int x, int y) => 
    !(x % 2 == 0 && y % 3 == 0 || x % 3 == 0 && y % 2 == 0);

@vantfiles · 11.03.2021, 16:23

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

Экспериментальным путём вычислил, что ноль кратен трём.

Ноль кратен любому натуральному числу.

@Shamil1 · 11.03.2021, 17:05

Сообщение от 0xFFF

по условию задачи n <= 22

Нужно использовать long, чтобы избежать переполнения.

C#
1
2
3
4
5
6
7
8
9
10
11
long Solve2(int n)
{
    long[] a = Enumerable.Repeat(1L, 10).ToArray();
 
    for (int i = 1; i < n; i++)
    {
        a = Enumerable.Range(0, 10).Select(j => a.Where((x, k) => IsValid(k, j)).Sum()).ToArray();
    }
 
    return a.Skip(1).Sum();
}

@LegionK · 11.03.2021, 17:05

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

для двойки выдается 61 - а это не так, несложно подсчитать руками.

Ну во первых я предлагаю больше конструктива внести. Я уже сожалею что ответил в этот балаган.

Во вторых я уверен, что ответ 61. Можно в самом деле, как вы сказали, посчитать руками :

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

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
#define ll unsigned long long
 
int main()
{
    int cnt = 0;
 
    for(int i = 1;i<=9;++i){
 
        for(int j = 0;j<=9;++j){
 
            int ok = 1;
 
            if(i % 2 == 0 && j % 3 == 0)ok = 0;
            if(i % 3 == 0 && j % 2 == 0)ok = 0;
 
            if(ok)++cnt;
 
        }
    }
 
    cout << cnt;
 
 
 
 
    return 0;
}

И ответ будет именно, что 61.

А предвидя сообщение, что i - первая цифра, может начинаться с 0, предлагаю посмотреть на ответ для 3 :

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

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 <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
#define ll unsigned long long
 
int main()
{
    int cnt = 0;
 
    for(int i = 1;i<=9;++i){
 
        for(int j = 0;j<=9;++j){
 
            for(int a = 0;a<=9;++a){
 
                int ok = 1;
 
                if(i % 2 == 0 && j % 3 == 0)ok = 0;
                if(i % 3 == 0 && j % 2 == 0)ok = 0;
 
                if(a % 2 == 0 && j % 3 == 0)ok = 0;
                if(a % 3 == 0 && j % 2 == 0)ok = 0;
 
                if(ok)++cnt;
 
            }
        }
 
    }
    cout << cnt;
 
 
 
 
    return 0;
}

И вы не поверите, он тоже выдает корректный ответ. Который уже можно проверить по примеру из сообщения темы. А вот поставив i = 0, этот код, увы, насчитает 30 лишних чисел.

В целом, больше отвечать не хочется. Все, всем удачи, всем здоровья.

@vantfiles · 11.03.2021, 17:39

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

для двойки выдается 61 - а это не так, несложно подсчитать руками.

Все так, заблуждался. Я зачем-то считал общее количество чисел с нуля, а не в диапазонах 10-99, 100-999, 1000-9999 и так далее.

@Shamil1 · 11.03.2021, 17:44

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

Во вторых я уверен, что ответ 61.

Да. Для n = 2 ответ 61.
Этот ответ получается суммированием массива [3,10,6,5,6,10,3,10,6,5] кроме нулевого элемента (так как число не может начинаться с 0).
Нулевой элемент нам понадобится для вычисления следующей строки, так как аффикс числа может начинаться с 0.

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

код, увы, насчитает 30 лишних чисел

Да. [30,64,48,40,48,64,30,64,48,40] - у нас есть 30 аффиксов длины 3, начинающихся с 0.

@Shamil1 · 11.03.2021, 17:49

Кстати, вместо массива длиной 10 можно использовать массив длиной 4, так как у нас всего 4 вида цифр: делятся на 2 и 3, делятся только на 2, только на 3, ни на 2 ни на 3.

@Mikhaylo · 11.03.2021, 20:40

Если взять результат, полученный для (n-1), и построить из него все числа для n путем добавления допустимых цифр 0-9 в конце, то можно сделать следующие наблюдения:

Обозначим некоторые группы цифр буквами:
А = 1, 5, 7
Б = 2, 4, 8, 0
В = 3, 9

Цифры А при добавлении совместимы со всеми цифрами А, Б, В, 6.
Цифры Б совместимы с цифрами А, Б.
Цифры В совместимы с цифрами А, В.
Цифра 6 совместима с цифрами А.

Заведем четыре счетчика, которые будут считать, сколько чисел для данного n имеют последнюю цифру А, Б, В, 6.

Для n=1:

S1(А) = 3
S1(Б) = 3
S1(В) = 2
S1(6) = 1

Для n=2:
S2(А) = S1(А) + 3 * [S1(А) + S1(Б) + S1(В) + S1(6)] = 30
S2(Б) = S1(Б) + 4 * [S1(А) + S1(Б)] = 27
S2(В) = S1(В) + 2 * [S1(А) + S1(В)] = 12
S2(6) = S1(6) + S1(А) = 4

И так далее.

Добавлено через 1 минуту
Но еще проблема переполнения счетчиков вроде как не решена, так как общее количество чисел порядка 1E+26.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

Поиск чисел

Решение

Решение

@0xFFF 0 / 0 / 0 Регистрация: 20.10.2020 Сообщений: 5

	Поиск чисел 11.03.2021, 00:41. Показов 4192. Ответов 31 Метки алгоритмы, олимпиадное программирование (Все метки) Здравствуйте, прошу помощи с задачей. На вход дается число n, необходимо найти все n-разрядные числа, которые удовлетворяют следующему условию: среди соседних пар цифр числа нет пар, где одна цифра четная, а другая кратна трем. Например, число 1234 не подойдет, потому что есть пара 23, где одна цифра кратная трем, а другая четная, а вот например число 567 подойдет. Собственно, сам вопрос, сейчас я решаю задачу полным перебором всех пар чисел для каждого числа, но по условию задачи n <= 22, а перебор всех пар 22-значного числа занимает слишком много времени (ограничение три секунды). Возможно есть какое-то более оптимальное решение? Пример Ввод: 3 Вывод: 446 0

@0xFFF 0 / 0 / 0 Регистрация: 20.10.2020 Сообщений: 5
	11.03.2021, 09:05 [ТС]
	vantfiles, Да, нужно найти их количество, немного неточно указал. Порядок кратных трем и четных неважен, то есть не подойдёт как 34, так и 43. А насчёт вашего предложения, я тоже об этом думал, но нам же нужно тогда отдельно обрабатывать крайние левые разряды числа, потому что число например 108 нам не подойдёт, ведь ноль кратен трем, а 080 учитыватьсься не будет, поскольку нужны числа без ведущих нулей. Как, например, применить этот способ для числа из примера n = 3? 0

@0xFFF 0 / 0 / 0 Регистрация: 20.10.2020 Сообщений: 5
	11.03.2021, 09:34 [ТС]
	А почему они не учитываются? Да у них ведущий ноль, но число 104 также не подойдёт, так и 109 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	11.03.2021, 09:50
	20 23 26 29 30 32 34 36 38 40 43 46 49 60 62 63 64 66 68 69 80 83 86 89 90 92 94 96 98 Ничего не пропустил? Добавлено через 7 минут Да, алгоритм посложнее получается... 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	11.03.2021, 10:08
	Новая цифра зависит только от предыдущей. Мы считаем количество двухзначных чисел (включая 01 и т.п.), начинающихся с цифр 0-9. Затем, используя эту информацию, считаем количество трехзначных чисел (включая 01 и т.п.), начинающихся с цифр 0-9. Добавлено через 9 минут В первом варианте мы создаём матрицу 10xN. Заполняем первый столбец "1". Для каждой ячейки второго столбца суммируем все разрешённые цифры первого столбца. Матрицу можно заменить на два массива - "предыдущий" и "текущий". 1

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	11.03.2021, 17:49
	Кстати, вместо массива длиной 10 можно использовать массив длиной 4, так как у нас всего 4 вида цифр: делятся на 2 и 3, делятся только на 2, только на 3, ни на 2 ни на 3. 0

@Mikhaylo 698 / 572 / 75 Регистрация: 20.09.2014 Сообщений: 3,700
	11.03.2021, 20:40
	Если взять результат, полученный для (n-1), и построить из него все числа для n путем добавления допустимых цифр 0-9 в конце, то можно сделать следующие наблюдения: Обозначим некоторые группы цифр буквами: А = 1, 5, 7 Б = 2, 4, 8, 0 В = 3, 9 Цифры А при добавлении совместимы со всеми цифрами А, Б, В, 6. Цифры Б совместимы с цифрами А, Б. Цифры В совместимы с цифрами А, В. Цифра 6 совместима с цифрами А. Заведем четыре счетчика, которые будут считать, сколько чисел для данного n имеют последнюю цифру А, Б, В, 6. Для n=1: S1(А) = 3 S1(Б) = 3 S1(В) = 2 S1(6) = 1 Для n=2: S2(А) = S1(А) + 3 * [S1(А) + S1(Б) + S1(В) + S1(6)] = 30 S2(Б) = S1(Б) + 4 * [S1(А) + S1(Б)] = 27 S2(В) = S1(В) + 2 * [S1(А) + S1(В)] = 12 S2(6) = S1(6) + S1(А) = 4 И так далее. Добавлено через 1 минуту Но еще проблема переполнения счетчиков вроде как не решена, так как общее количество чисел порядка 1E+26. 1