#include #include #define MAXN 100 struct trojice { int x[3]; // x[0] = R-G, x[1] = G-B, x[2] = pozice ve vstupu }; int n = 0; // délka vstupu struct trojice soucty[MAXN+1]; // prefixové součty reprezentované trojicemi // (hodnoty jsou posunuté o MAXN, aby nebyly nikdy záporné) // Načteme vstup a vytvoříme posloupnost trojic void read_in(void) { soucty[0] = (struct trojice) { { MAXN, MAXN, 0 } }; int c; while ((c = getchar()) != '\n') { n++; soucty[n] = soucty[n-1]; if (c == 'r') soucty[n].x[0]++; else if (c == 'g') soucty[n].x[0]--, soucty[n].x[1]++; else soucty[n].x[1]--; soucty[n].x[2] = n; } } // Přihrádkové třídění void sort(void) { struct trojice aux[MAXN]; // pomocné pole, kde budou bydlet přihrádky int len[2*MAXN+1]; // délky přihrádek int pos[2*MAXN+1]; // aktuální pozice v přihrádkách for (int s=2; s>=0; s--) // podle které složky právě třídíme { for (int p=0; p<2*MAXN+1; p++) // spočítáme, kolik místa potřebujeme na kterou přihrádku len[p] = 0; for (int i=0; i<=n; i++) len[soucty[i].x[s]]++; pos[0] = 0; // rozdělíme pomocné pole na přihrádky for (int p=1; p<2*MAXN+1; p++) pos[p] = pos[p-1] + len[p-1]; for (int i=0; i<=n; i++) // rozhazujeme do přihrádek aux[pos[soucty[i].x[s]]++] = soucty[i]; memcpy(soucty, aux, (n+1) * sizeof(struct trojice)); // přesuneme zpět } } // Nalezneme nejvzdálenější výskyt dvou stejných prefixových součtů void usek(void) { int max = 0, maxz = 0; int j = 0; while (j <= n) { int i = j; while (j <= n && soucty[i].x[0] == soucty[j].x[0] && soucty[i].x[1] == soucty[j].x[1]) j++; // Od i do j-1 leží v poli soucty úsek stejných prefixových součtů // Spočítáme vzdálenost mezi prvním a posledním výskytem ve vstupu int l = soucty[j-1].x[2] - soucty[i].x[2]; if (l > max) max = l, maxz = soucty[i].x[2]; } printf("Nejdelší bílý úsek má délku %d a začíná na pozici %d\n", max, maxz); } int main(void) { read_in(); sort(); usek(); return 0; }