Runda 3: Formuła (rozwiązanie)

01.12.2009

Autor zadania: Jarosław Gomułka

Podstawą rozwiązania jest obliczenie minimalnego czasu potrzebnego na przejechanie dokładnie N okrążeń dla każdego rodzaju oponu.

Znamy czas potrzebny na przejechanie dokladnie jednego okrążenia na danym rodzaju opony. Załóżmy, że mamy obliczony minimalny czas potrzebny na przejechanie dokładnie Y okrążeń dla wszystkich Y < X.

Minimalny czas potrzeby na przejechanie X okrążeń to:

  • MT[X] = min { MT[A] + MT[X-A] + pitstop_time | A in [1..X-1] } suma {czas potrzebny na przejechanie X okrążeń bez używania pitstopów }

W ten sposób obliczymy w czasie O(n^2) całą tablice MT dla każdego rodzaju opony.

Mając tablice MT1 i MT2 (minimalne czasy dla pierwszego i drugiego rodzaju opony) wynik to min { MT1[A] + MT2[N-A] + pitstop_time | A in [1..N-1] }

Złożoność O(N^2)

Organizatorzy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com