Поиск чисел

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

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

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

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

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

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

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

@Shamil1 · 11.03.2021, 21:49

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

Б = 2, 4, 8, 0

0 в одной группе с цифрой 6.

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

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

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

64 бита как раз хватает на заявленные в задаче n <= 22

@vantfiles · 11.03.2021, 22:53

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

64 бита как раз хватает на заявленные в задаче n <= 22

Не-а, максимум на 64 битах это 18446744073709551615

@Mikhaylo · 11.03.2021, 23:12

Пайтону насрать

Python
1
2
3
4
5
6
7
8
9
10
11
12
SA = [3]
SB = [3]
SC = [2]
S6 = [1]
S = [9]
for i in range(1,23):
    SA.append(SA[i-1] + 3 * (SA[i-1] + SB[i-1] + SC[i-1] + S6[i-1]))
    SB.append(SB[i-1] + 4 * (SA[i-1] + SB[i-1]))
    SC.append(SC[i-1] + 2 * (SA[i-1] + SC[i-1]))
    S6.append(S6[i-1] + SA[i-1])
    S.append(SA[i] + SB[i] + SC[i] + S6[i]) 
print(S)

Ответ: [9, 73, 634, 5491, 47677, 414232, 3600133, 31293277, 272024842, 2364704119, 20556523057, 178699975504, 1553460368209, 13504429104577, 117395767067962, 1020536904292075, 8871662656888501, 77122542293717128, 670436516072733613, 5828193821246293429, 50665264318645533706, 440439884075939627791, 3828802517377148001289]

Добавлено через 5 минут
Специально подводят к переполнению регистра, последние четыре суммы
5.82E+19
5.07E+20
4.40E+21
3.82E+22

@Shamil1 · 12.03.2021, 09:01

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

Не-а, максимум на 64 битах это 18446744073709551615

9223372036854775807 // int64 (половина максимума)
7816215383979529216 // ответ для n=22

@vantfiles · 12.03.2021, 09:20

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

Ответ: [9, 73, 634, 5491, 47677,

А это, вообще, что?

@Shamil1 · 12.03.2021, 14:30

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

А это, вообще, что?

Это неправильно посчитанные ответы для n=1,2,...

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

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

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

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Main()
{
    Console.WriteLine(Solve(3));
}
 
long Solve(int n)
{
    (long c0, long c1, long c2, long c3) = (1,1,1,1);
    
    for (int i = 1; i < n; i++)
    {
        (c0, c1, c2, c3) = (2 * c0, 3 * c1, 3 * c2, 2 * c3);
        (c0, c1, c2, c3) = (c1, c0 + c1 + c2 + c3, c2 + c1, c3 + c1);       
    }
    
    return c0 + 3 * c1 + 3 * c2 + 2 * c3;
}

Вместо массива на 4 элемента я использую кортеж из 4-х целых чисел.

К группе с0 относятся 0, 6 (делятся на 2 и 3).
К группе с1 относятся 1, 5, 7 (не делятся ни на 2, ни на 3).
К группе с2 относятся 2, 4, 8 (делятся только на 2).
К группе с3 относятся 3, 9 (делятся только на 3).

Изначально в кортеже количество аффиксов длиной 1, начинающихся с любой из цифр соответсвующей группы.
В строке 12 умножаем на количество цифр в группе, чтобы получить суммарное количество аффиксов, начинающихся с цифр соответсвующей группы.
В строке 13 вычисляем количество аффиксов длиной i+1, начинающихся с любой из цифр соответсвующей группы. Для этого складываем количества допустимых (после цифр данной группы) аффиксов длинной i.
В строке 16 из двух цифр группы с0 учитываем только одну (шестёрку), так как число не может начинаться с нуля.

@Mikhaylo · 12.03.2021, 21:48

Почему 0 делится на 3-то?

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

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

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

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

Добавлено через 2 часа 3 минуты
https://ru.m.wikipedia.org/wik... 1%82%D1%8C

Хотя свойство делимости определено на всём множестве целых чисел, обычно рассматривается лишь делимость натуральных чисел.

@Shamil1 · 13.03.2021, 13:35

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

Почему 0 делится на 3-то?

У меня были сомнения на этот счет, поэтому я проверил экспериментальным путем.

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

Так что все правильно у меня.

Правильно у автора задачи (его задача - он определяет). То есть, для n=3 должно получаться 446.

@vantfiles · 13.03.2021, 13:41

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

Почему 0 делится на 3-то?

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

У меня были сомнения на этот счет, поэтому я проверил экспериментальным путем.

А ведь Mikhaylo прав - ноль делится на 3, но он не кратен трем.

@Shamil1 · 13.03.2021, 15:53

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

з.ы. Я не понял, 0 кратен трём или нет?

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

А ведь Mikhaylo прав - ноль делится на 3, но он не кратен трем.

Зависит от определения.
Если какой-нибудь термин в условии задачи допускает двоякое толкование, то следует уточнить у автора задачи (или организатора конкурса). Если такой возможности нет, то следует ориентироваться на пример ввода-вывода.

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

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

Прав или неправ Михаил - зависит от его целей. Если его цель - придраться к условию задачи, то, возможно, он прав. Если его цель - решить задачу, то он сразу должен был проверить свое решение на приведенном примере ввода-вывода.

@Mikhaylo · 13.03.2021, 18:54

Извините, я обнаружил аж три ошибки в моем решении (с моей трактовкой):
1. Я забыл учесть для n=1 число "0".
2. Зачем-то я прибавлял к текущим счетчикам предыдущие значения (подсчет был нарастающим итогом).
3. Досчитал до n=23, а не до 22.

Python
1
2
3
4
5
6
7
8
9
10
11
12
SA = [3] # 1, 5, 7
SB = [3] # 2, 4, 8, 0
SC = [2] # 3, 9
S6 = [1] # 6
S = [10]
for i in range(1,22):
    SA.append(3 * (SA[i-1] + SB[i-1] + SC[i-1] + S6[i-1]))
    SB.append(4 * (SA[i-1] + SB[i-1]))
    SC.append(2 * (SA[i-1] + SC[i-1]))
    S6.append(SA[i-1])
    S.append(SA[i] + SB[i] + SC[i] + S6[i]) 
print(S)

Ответ: [10, 64, 497, 3799, 29234, 224773, 1729157, 13301896, 102332429, 787252339, 6056429042, 46592883169, 358445183369, 2757566270848, 21214323724697, 163204613662591, 1255554805365074, 9659150174035789, 74309127535060637, 571670005847935864, 4397933422975378229, 33833887025243036923]
Последнее значение переполняет unsigned int64: 3.38E+19

Вариант с авторской трактовкой:

Python
1
2
3
4
5
6
7
8
9
10
11
12
SA = [3] # 1, 5, 7
SB = [3] # 2, 4, 8
SC = [2] # 3, 9
SD = [1] # 6, 0
S = [10]
for i in range(1,22):
    SA.append(3 * (SA[i-1] + SB[i-1] + SC[i-1] + SD[i-1]))
    SB.append(3 * (SA[i-1] + SB[i-1]))
    SC.append(2 * (SA[i-1] + SC[i-1]))
    SD.append(2 * SA[i-1])
    S.append(SA[i] + SB[i] + SC[i] + SD[i]) 
print(S)

Ответ: [10, 61, 446, 3172, 22772, 162964, 1167512, 8361232, 59887376, 428925136, 3072092384, 22003149376, 157592734016, 1128722742592, 8084226096512, 57901470916864, 414706414115072, 2970242479021312, 21273701367635456, 152368156016567296, 1091303040047657984, 7816215383979529216]

Последнее значение: 7.81E+18

@0xFFF · 15.03.2021, 10:49 **[ТС]**

Уважаемые программисты! Всем большое спасибо за ответы, честно говоря, не ожидал такого большого отклика.

По поводу задачи: похоже единственным действительно быстрым способом будет способ предложенный ув. Mikhaylo, Shamil1. Реализация LegionK использует то же наблюдение -- зависимость новой цифры от предыдущей.

Еще насчет кратности нуля трем, во время проведения соревнований, эта информация уточнялась, и по условию этой задачи ноль кратен трем, а также ноль является четным, то есть если n = 3, то число 100 нам бы не подошло.

Не по теме:

После подведения итогов был предоставлен авторский разбор, в котором автор сам допустил небольшую ошибку, которая не позволяет правильно решить задачу

Новые блоги и статьи Все статьи Все блоги /
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .

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

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

@0xFFF 0 / 0 / 0 Регистрация: 20.10.2020 Сообщений: 5
	15.03.2021, 10:49 [ТС]
	Уважаемые программисты! Всем большое спасибо за ответы, честно говоря, не ожидал такого большого отклика. По поводу задачи: похоже единственным действительно быстрым способом будет способ предложенный ув. Mikhaylo, Shamil1. Реализация LegionK использует то же наблюдение -- зависимость новой цифры от предыдущей. Еще насчет кратности нуля трем, во время проведения соревнований, эта информация уточнялась, и по условию этой задачи ноль кратен трем, а также ноль является четным, то есть если n = 3, то число 100 нам бы не подошло. Не по теме: После подведения итогов был предоставлен авторский разбор, в котором автор сам допустил небольшую ошибку, которая не позволяет правильно решить задачу 0

Поиск чисел

Решение