Zadanie

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Merlinovi na [email protected] alebo Matejovi na [email protected].

Začala sa karanténa a dedko Repa má kopu voľného času. Rozhodol sa s ním preto spraviť niečo produktívne. Zrenovuje svoju záhradku! Teda presnejšie už konečne vymení dlaždice na tom porozbíjanom chodníku. Nevie si ale vybrať, ktoré dlaždice má kúpiť. Pomôžte mu.

Úloha

Chodník, ktorý chce dedko vydláždiť má dĺžku \(d\). Na výber má z \(n\) typov kachličiek, z ktorých \(i\)-ty má dĺžku \(l_i\). Vašou úlohou je nájsť taký typ kachličiek, ktorého keď kúpi ľubovoľne veľa, tak dokáže vydláždiť celý chodník bez toho aby musel rezať kachličky. Ak sa to dá dosiahnuť viacerými typmi kachličiek, nájdite taký typ, z ktorého treba kúpiť najmenej kusov.

Formát vstupu

Na prvom riadku vstupu sú čísla \(1 \leq n \leq 10^6\) a \(1 \leq d \leq 10^8\), počet typov kachličiek a dĺžka chodníka, ktorý chce dedko vydláždiť. V druhom riadku nasleduje \(n\) čísel. Číslo \(l_i\) (\(1 \leq l_i \leq 10^8\)) je dĺžka \(i\)-teho typu kachličky.

Formát výstupu

Vypíšte jedno číslo, najmenší možný počet kachličiek, ktorý musí dedko nakúpiť aby vydláždil svoj chodník. Ak to nedokáže žiadnym typom kachličky bez rezania, vypíšte \(-1\).

Hodnotenie

Existuje 5 sád vstupov. Pre prvú sadu navyše platí, že \(n,d \leq 100\). Pre druhú a tretiu sadu platí, že \(n \leq 10^4\). Pre posledné dve sady neplatia žiadne ďalšie obmedzenia.

Príklad

Input:

5 12
3 8 4 6 1

Output:

2

Kachličiek prvého typu by sme potrebovali 4 kusy, druhým typom sa chodník bez rezania vydláždiť nedá, z tretieho potrebujeme 3 kusy, zo štvrtého 2 kusy a z posledného 12. Teda potrebujeme kúpiť najmenej 2 kusy kachličiek.

Input:

3 7
2 3 4

Output:

-1

Teória

V úlohe potrebujeme zistiť, či sa dá chodník vydláždiť danou kachličkou bez rezania. Inak povedané, je treba zistiť, či je dĺžka chodníka deliteľná dĺžkou kachličky. Na to našťastie v programovacích jazykoch existuje vstavaná matematická operácia modulo, ktorá spočíta zvyšok prvého čísla po delení druhým. Napríklad \(5\%2=1\), alebo \(8\%3=2\).

V programovacích jazykoch C++, Python a mnohých iných, sa táto operácia zapisuje pomocou znaku \(\%\). V úlohe taktiež použijeme for cyklus, pomocou ktorého dokážeme prejsť cez každú kachličku na vstupe.

Riešenie

Postupne prejdeme cez všetky kachličky na vstupe a zistíme, ktorými sa dá vydláždiť celý chodník. Z týchto potom vezmeme tú z nich, ktorej treba kúpiť najmenej. Časová zložitosť tohto riešenia je \(O(n)\), lebo pre každú kachličku len zistíme zvyšok \(d\) po delení veľkosťou tejto kachličky. Pamäťová zložitosť je \(O(1)\), lebo nám stačí si pamätať len aktuálne najlepšiu kachličku.

Riešenie v C++ môže vyzerať napríklad takto:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,d,kachlicka,vysledok = -1;
    cin >> n >> d;
    for(int i = 0; i < n; i++){ //postupne nacitame kazdu kachlicku a skusime, ci je najlepsia
        cin >> kachlicka;
        if(d % kachlicka == 0){ //skusime, ci sa da vydlazdit cely chodnik bez zvysku
            if(vysledok == -1) vysledok = d / kachlicka;
            else vysledok = min(vysledok,d / kachlicka);
        }
    }
    cout << vysledok << endl;
}

Riešenie v Pythone môže vyzerať napríklad takto:

#nacitanie vstupu
n,d = list(map(int,input().split()))
kachlicky = list(map(int,input().split()))
najvacsia_kachlicka = -1

#prejdenie cez kachlicky
for kachlicka in kachlicky:
    # ak sa da vydlazdit cely chodnik bez zvysku a kachliciek staci kupit menej, nasli sme lepsiu kachlicku
    if d % kachlicka == 0 and kachlicka > najvacsia_kachlicka:
        najvacsia_kachlicka = kachlicka
if najvacsia_kachlicka != -1:
    vystup = d // najvacsia_kachlicka
else:
    vystup = najvacsia_kachlicka

print(vystup)

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