Płatności

02.06.2009
Trudność

Zadanie Płatności, zgodnie z zamierzeniami autorów, okazało sie najprostszym zadaniem pierwszej rundy. Po przebrnięciu przez treść rozwiązujący szybko odkrywali, że cały problem sprowadza się do policzenia najmniejszej wspólnej wielokrotności (LCM) ośmiu liczb danych na wejściu. Oczywiście LCM dwóch liczb obliczamy jako ich iloczyn podzielony przez ich największy wspólny dzielnik (GCD). Analogicznie LCM ośmiu liczb jest to ich iloczyn podzielony przez ich GCD (spróbuj to udowodnić).

Drobnym haczykiem (z którym nikt nie miał problemów dzięki wybranemu przez nas testowi przykładowemu) był typ danych używany w obliczeniach. Odpowiedź często nie mieściła sie bowiem w typie int, wymagane było użycie typu long long. Niektórzy zawodnicy posunęli się jeszcze dalej i użyli typu unsigned long long (którego zakres to od 0 do 18 446 744 073 709 551 615) - niepotrzebnie. Proste szacowanie maksymalnego wyniku (sto do potęgi ósmej) ogranicza go do 10 000 000 000 000 000 - mieści się on w typie long long z prawie tysiąckrotnym zapasem.

Wiktor Janas

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com