Dalsze kłopoty z ogrodem
13.04.2011
Dalsze kłopoty z ogrodemLimit czasowy: 2000 milisekund 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. WejścieW 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 ). WyjścieDla każdego testu należy w osobnej linii wypisać ile minimalnie razy pan Wincenty będzie musiał użyć miotacza płomieni. Przykład
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com