Nivelul concursului: Național
Grupe
#3582
Pe asfalt este desenat cu cretă un şotron, caroiaj format din n*n
căsuţe având aceleaşi dimensiuni (câte n
căsuţe pe fiecare din cele n
rânduri).
În fiecare căsuţă este scris câte un număr întreg din intervalul [-100, 100]
. Fiecare jucător are câte o piatră pe care o aruncă într-o căsuţă a şotronului, şi sărind într-un picior, împinge piatra din căsuţă în căsuţă, pe un anumit traseu astfel încât punctajul obţinut din suma numerelor de pe traseul parcurs să fie cât mai mare.
Numerele din căsuţele şotronului sunt scrise cu două culori albastru şi alb, astfel încât să nu existe două căsuţe alăturate (pe cele patru direcţii Nord
, Est
, Sud
, Vest
) având numere scrise cu aceeaşi culoare. Întotdeauna, prima căsuţă din primul rând al şotronului are înscris un număr de culoare albastră.
Se stabilesc apoi, următoarele reguli ale jocului:
Nord
;Est
;Să se scrie un program care să determine cel mai mare punctaj care se poate obţine jucând şotron după regulile stabilite.
ONI 2007, Clasa a IX-a
#2431
Se consideră N
intervale închise, având extremităţile numere naturale cuprinse între 1
şi L
. Fiecare număr natural i
din intervalul [1, L]
are asociată o pondere c[i]
. Numim acoperire o mulţime de numere naturale cuprinse între 1
şi L
cu proprietatea că fiecare interval conţine cel puţin un element al mulţimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
Pentru un set de intervale dat să se determine costul minim al unei acoperiri.
ONI 2007 Baraj