Zadanie

Čo by to bolo za hry v Koloseu, keby sa ich nezúčastnili aj Galovia? Emanix1 sa rozhodol zúčastniť sa na gladiátorských súbojoch. Na chrbát si pripol svoju obľúbenú zbraň2, do ruky zobral štít3 a so svojím druidom Prefixom sa vydal na cestu. Pred cestou sa, samozrejme, poriadne najedol – presne tak, ako sa na Gala patrí.

Cesta bola plná nástrah, preto sa Emanix musel pohybovať rýchlo. Po namáhavom dni sa dostali na rázcestie. Tam Prefix zazrel tabuľu, ktorá hovorila o úžasnej skratke ku Koloseu, ktorá vedie cez záhradky Rímskeho impéria. Čo však je horšie, miestni majú už plné zuby Galov, čo si tadiaľ skracujú cestu. Preto v momente, ako naši dvaja hrdinovia vkročia do nejakej záhradky, rozbehne sa za nimi strážny diviak. Ako správny projekt Rímskeho imperiálneho fondu regionálneho rozvoja má každá záhrada na začiatku tabuľku, na ktorej je napísané, za aký čas diviak votrelca v tejto záhradke chytí. Akonáhle votrelec opustí záhradku, diviak ho prestane prenasledovať (nejedná sa už o jeho územie, tak prečo by sa mal namáhať?).

Keďže bol Emanix po celom dni unavený4, pohyboval sa konštantnou rýchlosťou \(0.5\, m/s\). Prefix sa ako verný pomocník ponúkol, že Emanixovi pomôže odniesť zbroj. Emanix ako silný emancipovaný Gal však odmietol. Namiesto toho sa rozhodol, že pokiaľ nebude stíhať ujsť pred diviakom, napije sa zo svojho čarovného nápoja, ktorý zvýši jeho rýchlosť dvojnásobne. Čarovný nápoj však účinkuje iba \(k\) sekúnd a Prefix ako skúsený druid neodporúča užívať viac dávok naraz – môže to mať veľmi nepriaznivé účinky na Emanixov metabolizmus. Hneď ako účinok nápoja vyprchá, Emanix si môže dať ďalší dúšok.

Emanix je teraz zvedavý, či sa dokáže dostať touto cestou až do Kolosea. Pomôžte mu zistiť, či dokáže prejsť cez všetky záhradky bez toho, aby ho dobehol nejaký diviak. Ak to Emanix dokáže, zistite, koľkokrát sa musí napiť zo svojho čarovného nápoja.

Úloha

Na ceste sa nachádza \(n\) záhradiek tesne za sebou (tam, kde jedna záhradka končí, ďalšia začína). Vašou úlohou je zistiť, či sú Emanix s Prefixom schopní dostať sa cez všetky záhradky bez toho, aby ich ktorýkoľvek diviak dohnal. Ak to dokážu, musíte tiež zistiť, koľko najmenej krát sa musí Emanix napiť zo svojho čarovného nápoja. O každej záhradke viete jej dĺžku \(l\) a čas \(t\) – najdlhší čas, ktorý môže byť Emanix v danej záhradke (ak by tam bol dlhšie, dobehol by ho diviak).

Formát vstupu

Na prvom riadku vstupu sa nachádzajú dve čísla \(n\) a \(k\) (\(1 \leq n \leq 5 \cdot 10^5\), \(1 \leq k \leq 10^{12}\)). \(n\) je počet záhradiek, \(k\) je trvanie účinku čarovného nápoja v sekundách. Na druhom riadku sa nachádzádza postupnosť medzerami oddelených čísiel \(l_1, l_2, \dots, l_n\) (\(1 \leq l_i \leq 10^6\)), ktoré označujú dĺžky jednotlivých záhradiek v metroch. Na posledom riadku sa nachádza postupnosť medzerami oddelených čísiel \(t_1, t_2, \dots, t_n\) (\(1 \leq t_i \leq 10^7\)) - časy, za ktoré Emanixa a Prefixa v jednotlivých záhradkách dobehne diviak, v sekundách.

Formát výstupu

Na výstup vypíšte, najmenej koľkokrát sa bude musieť Emanix napiť čarovného nápoja, aby cez záhradky stihli prejsť. Ak Emanix nedokáže cez záhradky prejsť, vypíšte \(-1\).

Príklady

Input:

1 3
7
10

Output:

2

Emanix sa môže napiť napríklad hneď na začiatku. Za prvé \(3\) sekundy prejde \(3\) metre. Potom sa napije znovu a za ďalšie \(3\) sekundy prejde ďalšie \(3\) metre. Potom nápoj prestane účinkovať a posledný meter teda Emanixovi bude trvať \(2\) sekundy. Ak by sa napil iba raz, počas trojsekundového účinku nápoja by stihol prejsť \(3\) metre a na zvyšné \(4\) by potreboval \(8\) sekúnd, čo je dokopy viac než povolených \(10\) sekúnd.

Input:

3 100000
5 5 5
5 7 8

Output:

1

Input:

4 1000
1 2 3 4
10 9 10 9

Output:

0

Input:

3 3
3 3 3
3 3 2

Output:

-1

Cez poslednú záhradku Emanix nestihne prejsť, ani keby bol celý čas pod účinkom nápoja.

  1. Emanix v preklade znamená bojovník Pásomničej légie Galskej domobrany.↩

  2. squashovú raketu↩

  3. jeho časom takmer zabudnuté frisbee↩

  4. Musel predsa nosiť svoju zbroj.↩

Ešte pred tým, ako sa pustíme do riešenia, si zopakujeme parametre zo vstupu. Zadanú máme dĺžku účinku čarovného nápoja \(k\), dĺžky jednotlivých záhrad \(l_1, \dots, l_n\) a počty sekúnd \(t_1, \dots, t_n\), koľko sa v jednotlivých záhradách môže Emanix zdržať.

Najskôr sa pozrieme na to, ako by sa táto úloha dala vyriešiť, ak by Emanix prechádzal len cez jednu záhradu. Následne si ukážeme, ako takéto riešenie rozšíriť na viacej záhrad.

Riešenie pre jednu záhradu

Predpokladajme, že Emanix chce prejsť cez záhradku dlhú \(l\) a môže sa v nej zdržať maximálne \(t\) sekúnd. Môžu nastať 3 prípady:

  1. Emanix stihne ujsť pred diviakom bez použitia elixíru. Keďže jeho rýchlosť je \(0.5 \,\mathrm{m}/\mathrm{s}\), čas ktorý sa Emanix v záhrade zdrží zrátame ako \(2 \cdot l\). Tento prípad teda nastane práve vtedy, keď \(2 \cdot l \leq t\).

  2. Emanix nevie utiecť pred diviakom ani s použitím elixíru. Jeho rýchlosť s elixírom je \(1 \,\mathrm{m}/\mathrm{s}\), takže utiecť nestihne ak \(l > t\).

  3. Emanix nestihne prejsť bez elixíra, ale s elixírom to stihne. Toto nastane ak \(l \leq t < 2 \cdot l\)

V treťom prípade nás zaujíma, koľko elixírov potrebuje Emanix vypiť. Tu nám pomôže to, že za \(s\) sekúnd s elixírom prejde Emanix rovnakú vzdialenosť ako za \(2 \cdot s\) sekúnd bez elixíru. Na toto sa dá pozerať aj tak, že ak chceme, aby nejakú vzdialenosť prešiel o \(s\) sekúnd rýchlejšie, stačí aby bol \(s\) sekúnd pod vplyvom elixíru. My si teda zrátame o koľko sekúnd by diviakovi nestihol ujsť ak by nepoužil elixír (\(s = 2 \cdot l - t\)) a následne Emanix vypije aspoň toľko elixíru (\(\lceil \frac{s}{k}\rceil\)).

Viacero záhrad

Rozšírenie pre viacero záhradiek by bolo veľmi jednoduché, keby záhradky neboli nalepené jedna na druhú, lebo by sme ich mohli riešiť samostatne. Keďže však nasledujú tesne za sebou, tak elixír použitý v jednej záhradke môže posobiť aj v niekoľkých nasledujúcich, čo nám vie ušetriť niekoľko napití elixíru.

Ak pri niektorej záhradke nastane 2. prípad, Emanix nedokáže cez záhradky prejsť, teda môžeme rovno vypísať -1. Zamerajme sa ďalej už len na možnosť, že cez všetky záhradky Emanix stíha (možno len za pomoci elixíru) prejsť, teda vždy nastáva prípad 1. alebo prípad 3..

Budeme postupne riešiť jednotlivé záhradky od prvej až po poslednú. Vezmime si riešenie pre prvú záhradku. Ak nastane prípad 1., nič zaujímavé sa nám na probléme nezmení.

Rozoberme si teda prípad 3, kde Emanix potrebuje byť pod vplyvom elixíru \(s\) sekúnd. Keďže elixíry vieme piť len po \(k\)-sekundových dávkach, tak sa nám mohlo stať, že musíme vypiť \(a > s\) elixíru. Keďže v prvej záhradke potrebuje byť Emanix pod vplyvom elixíru iba \(s\) sekúnd, môže si jeho vypitie načasovať tak, aby mu zvyšných \(a-s\) sekúnd zostalo do ďalšej záhradky (inými slovami, vypiť elixír čo najneskôr ako môže). Toto sa zjavne oplatí, keďže riešenie prvej záhradky tým nijako nepokazíme a vieme len získať lepšie riešenie nasledujúcich záhradiek.

Pri riešení každej ďalšej záhradky už budeme predpokladať, že na začiatku \(e\) sekúnd už Emanix má vypitý elixír. Ak celú záhradu prejde na \(e\) elixíru, tak od zostávajúceho elixíru odrátame čas prejdenia tejto záhradky a presunieme sa na ďalšiu s novou hodnotou \(e := e - l_i\) (kde \(l_i\) je dĺžka aktuálnej záhradky).

Elixír sa nám však môže minúť aj uprostred. V tomto prípade je najjednoduchšie ,,odrátať’’ od dĺžky záhrady a času diviaka časť, keď bol Emanix pod vpluvom zvyšku elixíru a ďalej záhradu riešiť ako záhradu bez počiatočného elixíru: \(l_i := l_i - e;~ t_i := t_i - e\).

Pre každú záhradu teda zistíme, koľko elixírov na nej vypijeme. Už nám to len stačí sčítať (alebo počítať priebežne) a vypísať.

Zložitosť

Pre každú záhradu robíme len niekoľko operácií v konštantnom čase. Náš algoritmus teda bude mať časovú zložitosť lineárnu od počtu záhrad \(n\), čo označujeme ako \(O(n)\). Ďalej si musíme pamatať dĺžku každej záhrady a čas, ktorý v nej môžme stráviť. No a keďže si pre každú záhradku potrebujeme pamätať konštantne veľa informácie, pamäťová zložitosť bude tiež \(O(n)\).

//
//  sol_fast.cpp
//  KSP_KOLOSEUM_2
//
//  Created by Denis on 5.7.17.
//  Copyright © 2017 Denis. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    long long n, r;
    cin >> n >> r;
    vector<long long> dlzka_zahrady(n), cas(n);
    
    for (int i = 0; i < n; i++)
        cin >> dlzka_zahrady[i];
    for (int i = 0; i < n; i++)
        cin >> cas[i];
    for (int i = 0; i < n; i++) {
        if (dlzka_zahrady[i] > cas[i]) {
            cout << "-1\n";
            return 0;
        }
    }
    
    long long timer = 0, zostavajuci_ucinok_elixiru = 0, celkovy_pocet_pouzitych_elixirov = 0;
    
    for (int i = 0; i < n; i++) {
        if (zostavajuci_ucinok_elixiru > 0) {
            long long zrychleny = min(zostavajuci_ucinok_elixiru,
                                      dlzka_zahrady[i]);
            
            zostavajuci_ucinok_elixiru -= zrychleny;
            dlzka_zahrady[i] -= zrychleny;
            cas[i] -= zrychleny;
            timer += zrychleny;
        }
        
        if (dlzka_zahrady[i] == 0 || 2 * dlzka_zahrady[i] <= cas[i])
            continue;
        
        long long m = 2 * dlzka_zahrady[i] - cas[i];
        long long pocet_pozitych_elixirov = m / r + (m % r > 0);
        celkovy_pocet_pouzitych_elixirov += pocet_pozitych_elixirov;
        zostavajuci_ucinok_elixiru = pocet_pozitych_elixirov * r - m;
    }
    
    cout << celkovy_pocet_pouzitych_elixirov << "\n";
    
    return 0;
}

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ť.