Поиск чисел

@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 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .	Цена ошибки DevAlt 23.08.2026 Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .
Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. zorxor 22.08.2026 Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .	Жизня: рисунок укладки багажа, сделанный клодом anaschu 21.08.2026 Сделал 15 снимков, он по снимкам сделал схему.	Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .

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

	Поиск чисел 11.03.2021, 00:41. Показов 4444. Ответов 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

Поиск чисел

Решение