Runda 1: Wymiana żarówki (rozwiązanie)

25.11.2009

Autor zadania: Jarosław Gomułka

Zauważmy, że na każdym kolejnym poziomie(patrząc od góry w dół) znajduje sie 4 razy więcej ludzi niż na poprzednim. Jest tak, ponieważ każdy człowiek (poza osobami na ostatnim poziomie) musi stać na stole który podtrzymuje 4 ludzi. Wiemy, że na najwyższym poziomie jest jedna osoba.

W takim razie nastepujący pseudokod obliczy dokładną ilość osób potrzebną do zbudowania wieży o wysokości H.

ilosc_w_sumie = 1;
osoby_na_pietrze = 1;
for(int numer_poziomu=2; numer_poziomu<=H; numer_poziomu++){
osoby_na_pietrze = osoby_na_pietrze * 4; //aktualizujemy osoby na kolejnym poziomie
ilosc_w_sumie += osoby_na_pietrze; //aktualizujemy wynik
}

Jednak takie rozwiązanie nie zostanie zaakceptowane.
Jest to spowodowane tym, że wynik bardzo szybko rośnie:

  • Dla H = 17 wynik przekroczy zakres int'a
  • Dla H = 33 wynik przekroczy zakres long long'a


Reszty z dzielenia (oznaczone jako mod ) mają pewne specyficzne własności:
Dla każdych a,b,p>0

  • (a+b) mod p = ((a mod p) + (b mod p)) mod p
  • (a*b) mod p = ((a mod p) * (b mod p)) mod p


Wobec tego aby uzyskać program który oblicza ilość osób potrzebną do zbudowania wieży o wysokości H modulo 500000009 trzeba zmodyfikować podany wcześniej pseudokod by wszystkie obliczenia wykonywał modulo 500000009.

Organizatorzy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com