Флаги

@ThendVJ1 · Регистрация: 03.11.2022

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

(Время: 2 сек. Память: 128 Мб Сложность: 58%)
У Васи есть ткань прямоугольной формы, которая имеет клетчатую структуру и состоит из N×M цветных частей, разбитых на N строк и M столбцов.

Как известно, Вася интересуется флагами стран и он заметил, что если вырезать из этой ткани прямоугольник, состоящий из трёх цветных полос, то он будет напоминать флаг какой-нибудь страны. Вася думает, что прямоугольник похож на флаг, если он состоит из трёх одноцветных полос одинаковой высоты, находящихся друг под другом. При этом цвет средней полосы не должен совпадать с цветом верхней и нижней полос.

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

Помогите Васе вычислить количество различных флагов, которые могут у него получиться.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1 ≤ N, M ≤ 2000) – количество строк и столбцов в материи.

Каждая из последующих N строк входных данных описывает очередную строку материи и состоит из M строчных английских букв от «a» до «z», где одинаковым цветам соответствуют одинаковые буквы, а разным цветам – разные буквы.

Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – количество флагов, которые могут получиться у Васи.
INPUT.TXT
4 3
aaa
bbb
ccb
ddd
OUTPUT.TXT
6
У меня есть код,но он крашится на 2 тесте.Можете помочь исправить программу:

PHP
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
n,m=map(int,input().split())
a=[' '.join(input()).split() for _ in range(n)]
u=[1]
p=[]
w=[0]*n
c=0
r=0
for j in range(m):
    if j!=0:
        u.reverse()
        u.append(j-1)
        u.reverse()
        p=u
        u=[1]
        c=0
    for i in range(1,n):
        if a[i][j]==a[i-1][j]:
            u.append(u[i-1]+1)
        else:
            if c==0:
                c=i
            u.append(1)
    for i in range(c,n):
        h=u[i]
        if i+h<n and u[i-h]>=h and u[i+h]==h:
            r+=1
            if p!=[] and p[i]==h and a[i-h][j]==a[i-h][p[0]] and a[i+h][j]==a[i+h][p[0]]:
                f=w[i]
                r+=f
                w[i]=0
                w[i]+=f+1
            else:
                r+=w[i]
                w[i]=0
r+=sum(w)
print(r)

P.S.Я знаю,что во 2 тесте N=10 и M=10

@Red white socks · 26.12.2022, 08:49

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

У меня есть код,но он крашится на 2 тесте

Что вы вкладываете в понятие крашится?
Начать следует с разбора примера. Почему получается 6 флагов?
Я насчитал 12:
6 флагов 3х1, 4 флага 3х2 и 2 флага 3х3.

@ThendVJ1 · 26.12.2022, 12:20 **[ТС]**

Red white socks,извините.Я и вправду не правильно изъяснился.Программа не крашится она выдаёт неверный ответ.
в ответе 6 и вот пояснение к примеру и к самой задаче:

@ThendVJ1 · 26.12.2022, 12:34 **[ТС]**

Red white socks, там в условии говорится, что средний слой флага должен отличаться от верхнего и нижнего слоёв.
Я считаю,что я как раз самый оптимальный способ выбрал.Ведь как и положено в динамике(а эта задача вроде на динамику),я разбил задачу на подзадачи и есть моменты, где я использую сохранение ответов в массив.Кстати вот доработанный код,но он всё равно не проходит второй тест:

Python
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
n,m=map(int,input().split())
a=[' '.join(input()).split() for _ in range(n)]
u=[1]
p=[]
g=0
w=[0]*n
c=0
r=0
for j in range(m):
    if j!=0:
        p=u
        g=j-1
        u=[1]
        c=0
    for i in range(1,n):
        if a[i][j]==a[i-1][j]:
            u.append(u[i-1]+1)
        else:
            if c==0:
                c=i
            u.append(1)
    for i in range(c,n):
        h=u[i]
        if i+h<n and u[i-h]>=h and u[i+h]==h:
            r+=1
            if p!=[] and p[i]==h and a[i-h][j]==a[i-h][g] and a[i+h][j]==a[i+h][g]:
                f=w[i]
                r+=f
                w[i]=0
                w[i]+=f+1
            elif p!=[] and (p[i]!=h or a[i-h][j]!=a[i-h][g] or a[i+h]!=a[i+h][g]):
                r+=w[i]
                w[i]=0
        else:
             r+=w[i]
             w[i]=0
r+=sum(w)
print(r)

Я уверен в моём коде где-то прячется один единственный изъян,который мешает пройти программе.
И я знаю,что в моём изначальном вопросе ошибка,т.к. я код на питоне вставил в PHP

@Red white socks · 26.12.2022, 12:40

ThendVJ1, это я ступил, третью строчку как ccc прочитал вместо ссb) Теперь понятно.
Сейчас не могу ваш код посмотреть, только вечером. Но следующий алгоритм выглядит перспективным: находим вертикальную триминошку и пытаемся продолжить ее вправо.

@ThendVJ1 · 26.12.2022, 17:02 **[ТС]**

Red white socks, я тоже ступил,т.к. мой прошлый код рассматривал только равенство a[i+h] и a[i-h],т.е. к примеру:
6 2
ba
aa←
bb
bb
cc
cc←
и считал это за флаг.а теперь мой новый код рассматривает равенство a[i][j] и a[i][j-1](в моём случае,чтобы программа не крашилась это g) и равенство u[i+h] и p[i+h], u[i-h] и p[i-h].
Но к сожалению неверный ответ на тесте 4.Можете в этом убедиться сами,сдав мой код в проверяющую систему:

Добавлено через 7 минут
Можете в этом убедиться сами,сдав мой код в проверяющую систему acmp.Задача так и называется Флаги под номером 1853.Если в поисковике не находит,то зайдите на acmp в раздел "курсы",в разделе "курсы" перейдите в раздел "Региональные олимпиады", а после в раздел "Муниципальный этап", и там найдёте Муниципальный этап 2022/2023 9-11 классы.

Добавлено через 12 минут
вот кстати мой новый код:

Python
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
n,m=map(int,input().split())
a=[' '.join(input()).split() for _ in range(n)]
u=[1]
p=[]
g=0
w=[0]*n
c=0
r=0
for j in range(m):
    if j!=0:
        p=u
        g=j-1
        u=[1]
        c=0
    for i in range(1,n):
        if a[i][j]==a[i-1][j]:
            u.append(u[i-1]+1)
        else:
            if c==0:
                c=i
            u.append(1)
    for i in range(c,n):
        h=u[i]
        if i+h<n and u[i-h]>=h and u[i+h]==h:
            r+=1
            if p!=[] and p[i]==h and a[i-h][j]==a[i-h][g] and a[i+h][j]==a[i+h][g] and a[i][g]==a[i][j] and u[i+h]==p[i+h] and u[i-h]==p[i-h]:
                f=w[i]
                r+=f
                w[i]=0
                w[i]+=f+1
            elif p!=[] and (p[i]!=h or a[i-h][j]!=a[i-h][g] or a[i+h][j]!=a[i+h][g] or a[i][g]!=a[i][j] or u[i+h]!=p[i+h] or u[i-h]!=p[i-h]):
                r+=w[i]
                w[i]=0
        else:
             r+=w[i]
             w[i]=0
r+=sum(w)
print(r)

Добавлено через 4 минуты
Red white socks, Забейте на мой прошлый ответ.Я всё нашёл,но теперь Memory limit на 24 тесте.Я думаю там отсилу тестов 30,так что прорыв! Теперь нужна помощь с оптимизацией.
Вот самая лучшая моя прога на эту задачу,которая прошла 24 теста:

Python
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
n,m=map(int,input().split())
a=[' '.join(input()).split() for _ in range(n)]
u=[1]
p=[]
g=0
w=[0]*n
c=0
r=0
for j in range(m):
    if j!=0:
        p=u
        g=j-1
        u=[1]
        c=0
    for i in range(1,n):
        if a[i][j]==a[i-1][j]:
            u.append(u[i-1]+1)
        else:
            if c==0:
                c=i
            u.append(1)
    for i in range(c,n):
        h=u[i]
        if i+h<n and u[i-h]>=h and u[i+h]==h:
            r+=1
            if p!=[] and p[i]==h and a[i-h][j]==a[i-h][g] and a[i+h][j]==a[i+h][g] and a[i][g]==a[i][j] and p[i+h]==h and p[i-h]>=h:
                f=w[i]
                r+=f
                w[i]=0
                w[i]+=f+1
            elif p!=[] and (p[i]!=h or a[i-h][j]!=a[i-h][g] or a[i+h][j]!=a[i+h][g] or a[i][g]!=a[i][j] or h!=p[i+h] or p[i-h]<h):
                r+=w[i]
                w[i]=0
        else:
             r+=w[i]
             w[i]=0
r+=sum(w)
print(r)

И немного неловко вышло по поводу моего утверждения:"Я уверен в моём коде где-то прячется один единственный изъян,который мешает пройти программе".

Добавлено через 6 минут
Я думаю стоит как-то заменить массив w на что-нибудь менее жирное.К примеру переменную или переменные.Но как?
Или бред с переменной f. На что-то более умное заменить.
Но я убрал последнее никчёмное условие:
else:
r+=w[i]
w[i]=0
Или мороки по поводу переменной c. Или условие j!=0.
Крч я чувствую,что мы на подходе решения задачи.Столко идей,но как их реализовать?

Добавлено через 3 часа 23 минуты
Ксати,а память будет меньше,если я постепенно буду сравнивать j и j-1 столбцы.Т.е. берём 0 столбик и 1 столбик сравниваем их,после очищаем эти массивы и опять заполняем,в одном массиве будет 1,а в другом 2

@Red white socks · 26.12.2022, 17:25

ThendVJ1, я все равно не вижу ничего сложного в задаче.
Основа - определение флагов в столбце n x 1. Результат заносим в словарь, ключи - кортеж из начальной и конечной строки, значение - длина текущего флага, в начале 1.
Далее - определяем множество кортежей начальной и конечной позиции флагов в следующем столбце и сверяем словарь.
Если ключ содержится в множестве, то увеличиваем значение на 1, иначе - ключ удаляем, а счетчик увеличиваем на k(k+1)/2, если значение в словаре было равно k.

Добавлено через 2 минуты
В кортеж(ключ) еще надо добавить и цвета флага.

@ThendVJ1 · 26.12.2022, 17:54 **[ТС]**

Red white socks, вот я про то же,что задача не трудная,но по памяти не проходит.Я вас и прошу помочь моему коду с памятью,ведь ему что-то плохо

@eaa · 26.12.2022, 18:32

ThendVJ1, выбери pypy.
у меня с доп матрицей NхM. прошло нормально.

Добавлено через 2 минуты
11 строка p=u это что?
убери append'ы, зачем тебе динамически создавать списки. можно сразу указать размер.

@ThendVJ1 · 26.12.2022, 19:30 **[ТС]**

eaa, p=u-это типо я беру сначала прохожусь по 0 столбцу,после в p заполняю 0 столбец,а в u 1 столбец и сравниваю их.После сравнения p и u меняю их(в p значение u,а в u значение нового столбца

Добавлено через 1 минуту
eaa, ксати сколько всего тестов,не можешь подсказать?

@eaa · 26.12.2022, 19:47

ThendVJ1, 25 тестов.
да же попробовал 2 доп.матрицы использовать по NxM, тоже нормально заходит.

Добавлено через 14 минут
ThendVJ1, вроде в твоей программе ничего не нарушил, проверяй:

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

Python
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
n, m = map(int, input().split())
a = [' ' + input() for _ in range(n)]
u = [1] * (n + 1)
p = []
g = 0
w = [0] * n
c = 0
r = 0
for j in range(m):
    if j != 0:
        p = u[:]
        g = j - 1
        u = [1] * (n + 1)
        c = 0
    for i in range(1, n):
        if a[i][j] == a[i - 1][j]:
            u[i] = u[i - 1] + 1
        else:
            if c == 0:
                c = i
            u[i] = 1
    for i in range(c, n):
        h = u[i]
        if i + h < n and u[i - h] >= h and u[i + h] == h:
            r += 1
            if p != [] and p[i] == h and a[i - h][j] == a[i - h][g] and a[i + h][j] == a[i + h][g] and a[i][g] == a[i][
                j] and p[i + h] == h and p[i - h] >= h:
                f = w[i]
                r += f
                w[i] = 0
                w[i] += f + 1
            elif p != [] and (
                    p[i] != h or a[i - h][j] != a[i - h][g] or a[i + h][j] != a[i + h][g] or a[i][g] != a[i][j] or h !=
                    p[i + h] or p[i - h] < h):
                r += w[i]
                w[i] = 0
        else:
            r += w[i]
            w[i] = 0
r += sum(w)
print(r)

@ThendVJ1 · 26.12.2022, 21:53 **[ТС]**

eaa, не работает(.Я максимум дошёл до этого:

Python
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
n,m=map(int,input().split())
a=[' '.join(input()).split() for _ in range(n)]
u=[1]*n
p=[]
g=0
w=[0]*n
c=0
r=0
for j in range(m):
    if j!=0:
        p=u
        g=j-1
        u=[1]*n
        c=0
    for i in range(1,n):
        if a[i][j]==a[i-1][j]:
            u[i]=u[i-1]+1
        else:
            if c==0:
                c=i
    for i in range(c,n):
        h=u[i]
        if i+h<n and u[i-h]>=h and u[i+h]==h:
            if p!=[] and p[i]==h and a[i-h][j]==a[i-h][g] and a[i+h][j]==a[i+h][g] and a[i][g]==a[i][j] and p[i+h]==h and p[i-h]>=h:
                w[i]+=1
            else:
                w[i]=1
        else:
            w[i]=0
        r+=w[i]
print(r)

Но программа обрабатывать 24 тест за 1,359 с и 128МБ памяти,что является рекордом среди моих программ,т.к. прошлые программы были медленее и памяти требовали 129МБ

Добавлено через 3 минуты
Можешь сказать,что является лишним в моей программе, из-за чего переполняется память?Будет ли разумней вместо forов всю программу запихать в рекурсию и потом когда рекурсия дойдёт до i==n-1,вывести ответ и выйти из программы(к примеру sys.exit()),чтобы рекурсия не пошла обратна

@eaa · 26.12.2022, 22:02

ThendVJ1, я же выше подправил код, смотри.

Добавлено через 1 минуту
2-ую строчку исправь

Добавлено через 6 минут
Там join и split не нужны

@ThendVJ1 · 26.12.2022, 22:03 **[ТС]**

eaa,Большая благодарность вам! У меня прошла программа за 0,796 с и 11МБ.У меня в прошлой программе как я понял переполнение была из-за двумерного массива в строке 2?

@eaa · 26.12.2022, 22:06

ThendVJ1, да, похоже на то. Ты хранил как двумерный список строк.
А сейчас у тебя одномерный список строк.

@ThendVJ1 · 26.12.2022, 22:11 **[ТС]**

eaa, я эту задачу решал около 3 дней.Большущее спасибо!Я как понял мои догадки про сравнения j столбика и j-1 оказались верны,но большая моя ошибка была в том,что я просто думал,что печатая input().split() я не перехожу на масивы,а работаю также со строками,ведь input() же.

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

Добавлено через 1 минуту
или можете для глупенького меня объяснить почему печатая input().split() я перехожу на массивы,но вы говорите,что это всё ещё строки

@eaa · 26.12.2022, 22:11

ThendVJ1, там один символ. Но памяти сожрёт больше.
К строке же можно тоже по индексу обратиться.

@ThendVJ1 · 26.12.2022, 22:13 **[ТС]**

и если не секрет, то за сколько времени ваша программа решает эту задачу? Я видел ваше последнее решение этой задачи зашло за 1,3,но я как понял это решение с 2 доп. матрицами N*M

@eaa · 26.12.2022, 22:19

ThendVJ1, у меня не было цели оптимизировать, в 1 секунду укладывается.
Завтра потестирую.

@ThendVJ1 · 26.12.2022, 22:30 **[ТС]**

eaa, и ксати можно узнать вобщем по поводу acmp.Верно ли я поступаю,что уделяю именно этому сайту много времени.Может есть что-нибудь лучше,что прокачает мои олимпиадные навыки быстрее.Я даже не против за это заплатить деньги.Я конечно понимаю,что самый эффективный способ заключается как раз таки в самостоятельном решение задач(что я почти смог сделать.Если вы посмотрите полностью эту тему,то убедитесь,что единственный мною упущенный шаг к решению этой задачи,является ваш совет).Но это долго.Ведь тратить 3 дня на задачу 58% сложности это слишком,тем более на регионе мне надо такие задачи уметь решать за час от силы.

Добавлено через 6 минут
Ладно ответите,когда сможете.Не буду вас отвлекать.Ещё раз спасибо!

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@ThendVJ1 117 / 1 / 0 Регистрация: 03.11.2022 Сообщений: 18
	26.12.2022, 12:20 [ТС]
	Red white socks,извините.Я и вправду не правильно изъяснился.Программа не крашится она выдаёт неверный ответ. в ответе 6 и вот пояснение к примеру и к самой задаче: Миниатюры 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	26.12.2022, 12:40
	ThendVJ1, это я ступил, третью строчку как ccc прочитал вместо ссb) Теперь понятно. Сейчас не могу ваш код посмотреть, только вечером. Но следующий алгоритм выглядит перспективным: находим вертикальную триминошку и пытаемся продолжить ее вправо. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	26.12.2022, 17:25
	ThendVJ1, я все равно не вижу ничего сложного в задаче. Основа - определение флагов в столбце n x 1. Результат заносим в словарь, ключи - кортеж из начальной и конечной строки, значение - длина текущего флага, в начале 1. Далее - определяем множество кортежей начальной и конечной позиции флагов в следующем столбце и сверяем словарь. Если ключ содержится в множестве, то увеличиваем значение на 1, иначе - ключ удаляем, а счетчик увеличиваем на k(k+1)/2, если значение в словаре было равно k. Добавлено через 2 минуты В кортеж(ключ) еще надо добавить и цвета флага. 0

@ThendVJ1 117 / 1 / 0 Регистрация: 03.11.2022 Сообщений: 18
	26.12.2022, 17:54 [ТС]
	Red white socks, вот я про то же,что задача не трудная,но по памяти не проходит.Я вас и прошу помочь моему коду с памятью,ведь ему что-то плохо 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	26.12.2022, 18:32
	ThendVJ1, выбери pypy. у меня с доп матрицей NхM. прошло нормально. Добавлено через 2 минуты 11 строка p=u это что? убери append'ы, зачем тебе динамически создавать списки. можно сразу указать размер. 0

@ThendVJ1 117 / 1 / 0 Регистрация: 03.11.2022 Сообщений: 18
	26.12.2022, 19:30 [ТС]
	eaa, p=u-это типо я беру сначала прохожусь по 0 столбцу,после в p заполняю 0 столбец,а в u 1 столбец и сравниваю их.После сравнения p и u меняю их(в p значение u,а в u значение нового столбца Добавлено через 1 минуту eaa, ксати сколько всего тестов,не можешь подсказать? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	26.12.2022, 22:02
	Сообщение было отмечено ThendVJ1 как решение Решение ThendVJ1, я же выше подправил код, смотри. Добавлено через 1 минуту 2-ую строчку исправь Добавлено через 6 минут Там join и split не нужны 1

@ThendVJ1 117 / 1 / 0 Регистрация: 03.11.2022 Сообщений: 18
	26.12.2022, 22:03 [ТС]
	eaa,Большая благодарность вам! У меня прошла программа за 0,796 с и 11МБ.У меня в прошлой программе как я понял переполнение была из-за двумерного массива в строке 2? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	26.12.2022, 22:06
	ThendVJ1, да, похоже на то. Ты хранил как двумерный список строк. А сейчас у тебя одномерный список строк. 0

@ThendVJ1 117 / 1 / 0 Регистрация: 03.11.2022 Сообщений: 18
	26.12.2022, 22:11 [ТС]
	eaa, я эту задачу решал около 3 дней.Большущее спасибо!Я как понял мои догадки про сравнения j столбика и j-1 оказались верны,но большая моя ошибка была в том,что я просто думал,что печатая input().split() я не перехожу на масивы,а работаю также со строками,ведь input() же. Добавлено через 2 минуты eaa, а да,я реально до сейчашнего времени думал,что двумерный список строк значительнее меньше занимает памяти и времени,чем двумерный список массивов. Добавлено через 1 минуту или можете для глупенького меня объяснить почему печатая input().split() я перехожу на массивы,но вы говорите,что это всё ещё строки 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	26.12.2022, 22:11
	ThendVJ1, там один символ. Но памяти сожрёт больше. К строке же можно тоже по индексу обратиться. 1

@ThendVJ1 117 / 1 / 0 Регистрация: 03.11.2022 Сообщений: 18
	26.12.2022, 22:13 [ТС]
	и если не секрет, то за сколько времени ваша программа решает эту задачу? Я видел ваше последнее решение этой задачи зашло за 1,3,но я как понял это решение с 2 доп. матрицами N*M 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	26.12.2022, 22:19
	ThendVJ1, у меня не было цели оптимизировать, в 1 секунду укладывается. Завтра потестирую. 0

@ThendVJ1 117 / 1 / 0 Регистрация: 03.11.2022 Сообщений: 18
	26.12.2022, 22:30 [ТС]
	eaa, и ксати можно узнать вобщем по поводу acmp.Верно ли я поступаю,что уделяю именно этому сайту много времени.Может есть что-нибудь лучше,что прокачает мои олимпиадные навыки быстрее.Я даже не против за это заплатить деньги.Я конечно понимаю,что самый эффективный способ заключается как раз таки в самостоятельном решение задач(что я почти смог сделать.Если вы посмотрите полностью эту тему,то убедитесь,что единственный мною упущенный шаг к решению этой задачи,является ваш совет).Но это долго.Ведь тратить 3 дня на задачу 58% сложности это слишком,тем более на регионе мне надо такие задачи уметь решать за час от силы. Добавлено через 6 минут Ладно ответите,когда сможете.Не буду вас отвлекать.Ещё раз спасибо! 0

Флаги

Решение