#!/usr/bin/python3 # načtení vstupu T, N = list(map(int, input().strip().split(' '))) vstup = [] for _ in range(T): s = input().strip() vstup.append(s) # zjisti, který znak je dominantní pro každý sloupec dominantni = [None] * N for i in range(N): pocet = [0] * 26 # kolikrát jsme ve sloupci potkali příslušný znak for j in range(T): idx = ord(vstup[j][i]) - ord('A') pocet[idx] += 1 if pocet[idx] > T // 2: dominantni[i] = vstup[j][i] break # zkusíme každý možný začátek (i) a zkusíme, jak daleko se dokážeme dostat (j) # 'uvazujeme' bude obsahovat testy, které zatím obsahují jen dominantní odpovědi # (tj. ze začátku všechny prvky a postupně odstraňujeme nevyhovující) # ze tří cyklů v sobě je dobře vidět složitost O(TN^2), ale pozor, že používáme # pro větší čitelnost funkci remove, která iteruje do prvního výskytu daného # prvku (a ve skutečnosti tak toto řešení pracuje v O(T^2*N^2)) # (určitě byste snadno cyklus přepsali, aby šel přes indexy a používal funkci pop) mx, a, b, c = 0, 0, 0, 0 for i in range(N): uvazujeme = [l for l in range(T)] #ve starších verzích Pythonu by fungovalo čistě range(T), ale Python 3 vrací tzv. range object, my chceme list for j in range(i, N): for k in list(uvazujeme): if vstup[k][j] != dominantni[j]: uvazujeme.remove(k) if len(uvazujeme) <= T // 2: break delka = j - i + 1 if mx < delka: mx, a, b, c = delka, i, j, len(uvazujeme) print(a, b, c)