Najdłuższy ciąg jedynek

Zadanie 1 z 10 · rozdział 24Trudność: 2 z 3list0/1analizaindeksy

Treść zadania

Otrzymujesz listę składającą się wyłącznie z zer i jedynek. Znajdź indeks zera, którego zamiana na 1 da najdłuższy nieprzerwany ciąg jedynek.

  • Jeśli kilka zer daje ciąg o tej samej, maksymalnej długości — wybierz zero o najmniejszym indeksie.
  • Jeśli lista składa się wyłącznie z zer albo wyłącznie z jedynek — wypisz -1.

Dane wejściowe

  • 1. linia: n — długość listy
  • 2. linia: n liczb 0 lub 1 oddzielonych spacjami

Dane wyjściowe

Jedna liczba całkowita: indeks szukanego zera albo -1.

Ograniczenia

  • 1 ≤ n ≤ 1000

Uwagi

  • Po zamianie zera łączą się jedynki stojące bezpośrednio przed nim i za nim — wystarczy więc znać pozycje sąsiednich zer. Da się to policzyć w jednym przejściu po liście, w czasie $O(n)$.

Przykład

Wejście
10
0 0 1 0 1 1 1 0 1 1
Wyjście
7

Zamiana zera o indeksie 7 daje sześć jedynek pod rząd (indeksy 4–9). Zamiana zera o indeksie 3 dałaby tylko pięć jedynek (indeksy 2–6).

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 24

Trudniejsze zadania na listach: przekształcenia w miejscu, sumy prefiksowe, kopiec i programowanie dynamiczne. Liczy się nie tylko poprawny wynik, ale też dobry algorytm — w testach są także długie listy, na których rozwiązanie „sprawdzające wszystkie możliwości” nie zdąży się wykonać.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Lista liczb jest podawana w dwóch liniach: w pierwszej jest liczba elementów n, w drugiej n liczb całkowitych oddzielonych spacjami (o ile zadanie nie mówi inaczej).
  • Listę wynikową wypisuj w jednej linii, a jej elementy oddzielaj pojedynczą spacją (o ile zadanie nie mówi inaczej).
  • Indeksy liczymy od 0.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
0
Oczekiwane wyjście
-1

Test 2

Nie uruchomiono
Wejście
1
1
Oczekiwane wyjście
-1

Test 3

Nie uruchomiono
Wejście
5
1 1 1 1 1
Oczekiwane wyjście
-1

Test 4

Nie uruchomiono
Wejście
4
0 0 0 0
Oczekiwane wyjście
-1

Test 5

Nie uruchomiono
Wejście
2
1 0
Oczekiwane wyjście
1

Test 6

Nie uruchomiono
Wejście
4
0 1 1 1
Oczekiwane wyjście
0

Test 7

Nie uruchomiono
Wejście
5
1 0 1 0 1
Oczekiwane wyjście
1

Test 8

Nie uruchomiono
Wejście
7
1 0 0 1 1 1 0
Oczekiwane wyjście
2

Test 9

Nie uruchomiono
Wejście
6
1 1 0 1 0 0
Oczekiwane wyjście
2

Test 10

Nie uruchomiono
Wejście
1000
1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1
Oczekiwane wyjście
37
Uruchom z własnymi danymi