시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 80 | 62 | 45 | 73.770% |
JOI 高校の生徒である葵は,文化祭で廊下に電飾を飾ることにした.
電飾は,N 個の電球を東西方向に一列に並べて作る.電球には西側から順に 1 から N までの番号が付けられている.各電球にはオンとオフの 2 つの状態があり,はじめ電球はすべてオフの状態である.
葵が目標とする電飾の模様は数列 A1, A2, ..., AN で表され,Ai = 1 のときは電球 i をオンに,Ai = 0 のときはオフにしたい.葵はできるだけ短い時間でこの模様にしようと考えた.
葵は最初に次の操作を 1 回だけ行うことができるが,行わなくてもよい.
この操作を行うのにかかる時間は無視できる.
その後,次の操作を何回でも行うことができる.
この操作を行うには 1 回につき 1 分かかる.
電球の個数,目標とする電飾の模様が与えられたとき,葵が目標の模様にするのに最短で何分かかるかを求めるプログラムを作成せよ.
入力は以下の形式で標準入力から与えられる.
N A1 A2 … AN
標準出力に,目標の模様にするのに最短で何分かかるかを 1 行で出力せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 45 | N ≦ 2 000. |
2 | 55 | 追加の制約はない. |
6 0 1 1 0 0 1
2
例えば,葵は最初に r = 3 を選び,電球 1, 2, 3 をオンにする.この操作にかかる時間は 0 分である.その後,電球 1 をオンからオフに,電球 6 をオフからオンに状態を変更する.この操作にはそれぞれ 1 分ずつ合計で 2 分かかる.2 分未満で目標の模様にすることはできないので,2 を出力する.
4 0 0 0 1
1
この入力例では,葵は最初の操作は行わない.その後,電球 4 をオフからオンに状態を変更する.この操作には 1 分かかり,1 分未満で目標の模様にすることはできないので,1 を出力する.
4 1 1 1 1
0
この入力例では,葵は最初に r = 4 を選び電球 1, 2, 3, 4 をオンにすることで,目標の模様にすることができる.この操作にかかる時間は 0 分であるので,0 を出力する.
15 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1
6
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics for Girls > JOIG 2020/2021 3번