Złodziejki (omówienie)

03.03.2010

Aby dostać maksymalną liczbe punktów można było obliczyć zwarty wzór wyliczający wynik w złożoności O(1).

Można było również po prostu zasymulować algorytm jaki Hektor zastosował czyli "Dopóki miał do dyspozycji za mało wolnych gniazdek, wpinał w jedną z nich rozgałęźnik. Kiedy tylko uzyskał potrzebną liczbę wolnych gniazdek, wpiął wszystkie N wtyczek."

scanf("%d %d",&n,&k);
int wolne = 1;
while(wolne<n) wolne+=k-1;

Algorytm ma złożoność O(n) co przy danych n<=10^6 jest rezultatem gwarantującym maksymalną ilość punktów.
Pozostaje wypisać wynik, czyli ilość wolnych wtyczek po wykonaniu tego algorytmu minus wtyczki które Hektor musi podłączyć. Cały kod wygląda następująco:

int main(){
    int test,n,k;
    scanf("%d",&test);
    while(test--){
        scanf("%d %d",&n,&k);
        int wolne = 1;
        while(wolne<n) wolne+=k-1;
        printf("%d\n",wolne-n);
    }
    return 0;
}

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com