시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 10 | 6 | 6 | 100.000% |
W zadaniu Kłopoty z ogrodem (FallSpot 2009) mieliśmy okazję poznać pana Wincentego - właściciela ogrodu i wielkiego antymiłośnika grabienia opadłych liści.
Od czasu ostatnich kłopotów minęło już trochę czasu, zmniejszony (por. oryginalne zadanie) ogród nie wymaga już tyle uwagi jesienią. Niestety, wraz z nadejściem tegorocznej wiosny pojawiły się nowe problemy - w ogrodzie zaczęły plenić się chwasty, doprowadzając pana Wincentego do szaleństwa (świadkowie twierdzą, że widzieli pana Wincentego nucącego słowa Chwasty chwaściki chwaściory chwaścięta - cała to roślinność wiecznie nie przycięta! na melodię jednej z symfonii Beethovena). Pewnego dnia pan Wincenty po długich godzinach spędzonych w warsztacie stanął w ogrodzie z przenośnym miotaczem płomieni w rękach.
Ogród pana Wincentego składa się z N pól ponumerowanych od 1 do N. W każdym polu znajduje się liczba chwastów wyrażona liczbą całkowitą ci. Jednokrotne użycie miotacza płomieni na polu i powoduje zmniejszenie o połowę liczby chwastów w polu i oraz w sąsiednich polach i-1 oraz i+1.
Przez zmniejszenie o połowę rozumiemy dzielenie całkowite przez 2, tj. z 8 chwastów zostają 4, z 5 zostają 2. Jako cel miotacza płomieni można wybrać także nieistniejące pola 0 i N+1, wtedy jedyne redukowane pola to - odpowiednio - 1 i N.
Oblicz ile minimalnie razy pan Wincenty musi skorzystać z miotacza ognia, aby usunąć wszystkie chwasty.
W pierwszej linii wejścia znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.
Pierwsza linia opisu zestawu testowego zawiera jedną liczbę naturalną N ( 1 <= N <= 1000000) oznaczającą liczbę pól w ogrodzie pana Wincentego.
W drugiej linii opisu zestawu znajduje się N oddzielonych spacjami liczb naturalnych ci oznaczających liczbę chwastów w poszczególnych polach ogrodu ( 0 <= ci <= 1000000 ).
Dla każdego testu należy w osobnej linii wypisać ile minimalnie razy pan Wincenty będzie musiał użyć miotacza płomieni.
3 1 1 3 4 2 4 5 2 0 0 0 2
1 3 4
Contest > Spot > SpringSpot 2011 2-2번