Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Taksówki (taksowki) Limit pamięci: 32 MB Limit czasu: 0.50 s Pociąg z Bitowa Górnego do Bitowa Dolnego utknął w połowie trasy! Na szczęście Bajtockie Koleje Państwowe już załatwiają taksówki, aby przewieźć zmarzniętych pasażerów, którzy stoją teraz w polu. Zastanawiają się jednak, ile najmniej taksówek muszą wysłać, aby pasażerowi byli zadowoleni. Pasażerowie pociągu nie chcieliby być rozdzieleni z osobami, z którymi jechali w jednym przedziale. Na szczęście przedziały są czteroosobowe, tak samo jak taksówki. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba przedziałów w pociągu. W drugim (ostatnim) wierszu wejścia znajduje się N liczb naturalnych Ai – liczba osób w i-tym przedziale. Wyjście Należy wypisać minimalną liczbę taksówek, jaką BKP potrzebuje, aby wysłać wszystkie osoby na dworzec w Bitowie Dolnym. Ograniczenia 1 ≤ N ≤ 100 000, 1 ≤ Ai ≤ 4. Przykład Wejście Wyjście 5 1 2 4 3 3 4

Wejście	Wyjście
`5 1 2 4 3 3`	`4`