3. Zanedbané zastávky (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

Kocúrkovo je to pravé mesto pre ľudí, ktorí sa vedia stratiť aj vo vlastnom byte. Je to totiž len jedna veľmi dlhá ulica. A keďže je taká dlhá, už roky tu jazdí mestská hromadná doprava.

Miestne autobusy jazdia po Kocúrkove tak, ako by ste od dlhej, rovnej ulice čakali. Pozdĺž ulice je postavených \(n\) autobusových zastávok. Každá autobusová linka má dve konečné zastávky, medzi ktorými jej autobusy jazdia hore-dolu, pričom stoja aj na každej zastávke po ceste. Kocúrkovo je však Kocúrkovo a tak sa môže stať, že niektoré linky začínajú aj končia na rovnakej zastávke (a teda ich autobusy iba stoja na tejto zastávke).

Kocúrkovské zastávky začali pod náporom neúprosného času hrdzavieť a chátrať. Preto si starosta Kocúrkova povedal, že ich dá všetky zrekonštruovať. A keď už sa prerábajú, tak by to malo byť vidno. Nech na to ľudia do volieb nezabudnú.

Rekonštrukcia jednej zastávky trvá jeden deň. Je možné rekonštruovať aj viac zastávok naraz. Starosta by teda mohol všetky zastávky nechať zrekonštruovať v ten istý deň, ale pre jeho volebné preferencie to nemusí byť tá najlepšia možnosť. Ľudia si totiž rekonštrukciu budú pamätať lepšie, ak bude prebiehať dlhšie.

Starostovi hrá do karát to, že Kocúrkovo je známe svojimi klebetníkni. Stačí, aby sa na trase autobusovej linky prerábala jediná zastávka a v autobuse vrava neutíchne až do večera. Ak sa teda v nejaký deň na trase každej linky prerába aspoň jedna zastávka, v celej Kocúrkovskej hromadnej doprave sa rozpráva iba o rekonštrukcii.

Úloha

Máte zadaný počet zastávok v Kocúrkove, počet liniek MHD a konečné zastávky, medzi ktorými tieto linky premávajú.

Starosta chce naplánovať rekonštrukciu zastávok tak, aby sa čo najdlhšie v autobusoch hovorilo iba o nej. Chce teda, aby od začiatku rekonštrukcie čo najdlhšie platilo, že na trase každej linky sa prerába aspoň jedna zastávka. Povedané ešte inak, starosta chce, aby sa čo najneskôr stalo, že na trase niektorej linky sa nebude prerábať žiadna zastávka.

A tu prichádzate na rad vy. Nájdite pre starostu Kocúrkova takýto plán a povedzte mu, koľko dní bude pri každej linke MHD aspoň jedna zastávka v rekonštrukcii. Pre každú zastávku teda naplánujte, v ktorý deň sa má prerábať.

Formát vstupu

V prvom riadku vstupu sú dve medzerou oddelené celé čísla \(n\) a \(m\) - počet zastávok a počet autobusových liniek. Platí \(1 \leq n \leq 1\, 000\, 000\) a \(1 \leq m \leq 100\, 000\).

Nasleduje \(m\) riadkov, v každom z nich sú dve medzerou oddelené čísla \(z_i\) a \(k_i\) - poradové čísla konečných zastávok \(i\)-tej linky, od začiatku mesta. Platí \(1 \leq z_i \leq k_i \leq n\).

Formát výstupu

Na prvý riadok výstupu vypíšte jedno číslo - po koľko dní od začiatku vieme rekonštruovať aspoň jednu zastávku na trase každej linky.

Na druhý riadok vypíšte \(n\) medzerou oddelených čísel - čísla dní, kedy sa majú rekonštruovať jednotlivé zastávky (v poradí od začiatku mesta po koniec). Rekonštrukcia sa začína nultým (\(0\)) dňom. Ak existuje viac optimálnych riešení, vypíšte ľubovoľné z nich.

Príklady

Input:

Output:

2
1 0 2 1 0

Na trase prvej linky sa zastávky rekonštruujú v deň \(1\), \(0\) a \(2\), takže ľudia si budú rekonštrukciu všímať \(3\) dni. Podobne druhá linka. Pri tretej sa rekonštruuje v dni \(0\) a \(1\). Všetci si teda budú starostovu rekonštrukciu všímať aspoň \(2\) dni.

Aj v tejto sérií sa tretia úloha dala vyriešiť prekvapivo jednoduchým algoritmom so zaujímavou myšlienkou.

Je zjavné, že niekedy nám nastane deň, kedy pri niektorej linke nebude prerábaná ani jedna zastávka. Keďže každý deň prerobíme aspoň jednu zastávku, po \(n\) dňoch budú určite všetky hotové.

Podobne sa môžeme pozrieť na nejakú konkrétnu linku s \(i\) zastávkami. Podobnú úvahu ako pre celé Kocúrkovo vieme spraviť aj pre túto linku. Na trase tejto linky najneskôr v \(i\)-ty deň nebude prerábaná ani jedna zastávka. Označme si \(k\) počet zastávok na najkratšej linke. Na tejto linke sa najneskôr \(k\) ty deň nebude prerábať zastávka, tým pádom odpoveď na úlohu bude najviac \(k\).

Teraz si ukážeme že plán rekonštrukcie dá naozaj spraviť tak, že prvá linka bez prerábanej zastávky sa zjaví až v \(k\)-ty deň.

Úvaha

Pre lepšiu čitateľnosť si očíslujeme zastávky \(0\) až \(n-1\) namiesto \(1\) až \(n\).

Predstavme si, že od prvých dvoch Kocúrkovských zastávok jazdia linky dĺžky \(k\). Prvá linka jazdí medzi zastávkami \(0\) a \(k-1\). Keďže máme \(k\) dní, \(k\) zastávok a chceme každý deň rekonštruovať aspoň jednu zastávku, tak môžeme napríklad rekonštruovať \(i\)-tu zastávku v deň číslo \(i\).

Teraz sa pozrime na druhú linku, ktorá jazdí medzi zastávkami \(1\) až \(k\). Rekonštrukciu zastávok \(1\) až \(k-1\) už máme naplánovanú z prvej linky, a chýba v nej len deň číslo \(0\). Nemáme teda inú možnosť, ako rekonštruovať zastávku \(k\) v deň \(0\).

Podobne, ak by sme mali linku aj medzi zastávkami \(2\) a \(k+1\), tak zastávka \(k+1\) by musela byť rekonštruovaná v ten istý deň ako zastávka \(1\), čiže v deň \(1\). V tomto vzore vieme ľahko pokračovať aj ďalej, vo všeobecnosti sa zastávka \(i\) bude rekonštruovať v deň \(i \bmod k\), čo znamená zvyšok po delení \(i\) číslom \(k\).

Takýto plán nám zaručí, že ľubovoľných \(k\) po sebe idúcich zastávok bude rekonštruovaných v každom dni od \(0\) až po \(k-1\) v nejakom poradí. Tým pádom ľubovoľná linka dĺžky aspoň \(k\) bude mať počas každého z prvých \(k\) dní rekonštruovanú aspoň jednu zastávku.

Implementácia

Zo vstupu potrebujeme okrem počtu zastávok \(n\) a počtu liniek \(m\) len dĺžku najkratšej linky \(k\). Počet dní na výstupe potom bude práve \(k\). Plán rekonštrukcie vyrobíme jednoducho. Zastávku číslo \(i\) budeme prerábať v dni \(i \bmod k\).

Časová zložitosť takéhoto riešenia je \(O(m)\) na načítanie vstupu a \(O(n)\) na vypísanie odpovede, dokopy \(O(n + m)\).

Pamäťová zložitosť je \(O(1)\). Vo vzorovom kóde kóde v C++ si môžeme všimnúť, že na výpočet najkratšej dĺžky linky a vypísanie plánu rekonštrukcie nepotrebujeme žiadne polia ¹.

#include <iostream>
#include <algorithm> // tu je definovane min 

using namespace std;

int main() {

    int n, m;
    cin >> n >> m;

    // prve ohranicenie riesenia
    int k = n;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        // ak mame kratsiu linku nez doteraz tak zapiseme jej dlzku
        k = min(k, b-a+1);
    }

    cout << k << endl;

    for (int i=0; i<n; i++) {
        if (i != 0) {
            cout << " ";
        }
        cout << i % k;
    }
    cout << endl;
}

n, m = [int(x) for x in input().split()]

# nacitame konecne zastavky, ulozime ich ako dvojice v liste
konecne_zastavky = [input().split() for _ in range(m)]

# tieto dvojice postupne odcitame od seba
# dostaneme dlzky liniek a z nich vezmeme najkratsiu
k = min([int(b) - int(a) + 1 for a, b in konecne_zastavky])

print(k)

plan = [i % k for i in range(n)]

print(' '.join(map(str, plan)))

Kód v Pythone ich pre prehľadnosť používa.↩

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.

3. Zanedbané zastávky vzorové riešenie