B - Batters Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

高橋君は野球をモチーフにしたゲームを作ろうとしましたが、うまくコードが書けなくて困っています。
高橋君の代わりに次の問題を解くプログラムを作ってください。

マス 0, マス 1, マス 2, マス 3 の 4 つのマス目があります。はじめマスの上には何もありません。
また、整数 P があり、はじめ P = 0 です。
正の整数からなる数列 A = (A_1, A_2, \dots, A_N) が与えられるので、i = 1, 2, \dots, N について順番に次の操作を行います。

  1. マス 0 に駒を 1 個置く。
  2. マス上のすべての駒を番号が A_i 大きいマスに進める。言い換えると、駒がマス x にあればその駒をマス x + A_i に移動する。
    ただし移動先のマスが存在しない (すなわち x + A_i が 4 以上になる) 駒たちに関しては、それらを取り除いて P に取り除いた個数を加算する。

すべての操作を行った後の P の値を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 4
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

操作終了時点での P の値を出力せよ。

入力例 1

4
1 1 3 2

出力例 1

3

操作を説明すると次のようになり、操作終了時点での P の値は 3 になります。

  • i=1 での操作
    1. マス 0 に駒を置く。この時点でマス 0 にコマが乗っている。
    2. すべての駒を 1 大きいマスに進める。移動を終えた時点でマス 1 に駒が乗っている。
  • i=2 での操作
    1. マス 0 に駒を置く。この時点でマス 0, 1 にコマが乗っている。
    2. すべての駒を 1 大きいマスに進める。移動を終えた時点でマス 1, 2 に駒が乗っている。
  • i=3 での操作
    1. マス 0 に駒を置く。この時点でマス 0, 1, 2 にコマが乗っている。
    2. すべての駒を 3 大きいマスに進める。
      この時、マス 1,2 にある駒は移動先のマスが存在しないため (それぞれ 1+3=4,2+3=5 なので) 、盤上から取り除いて P に 2 を加算する。P の値は 2 になる。
      移動を終えた時点でマス 3 に駒が乗っている。
  • i=4 での操作
    1. マス 0 に駒を置く。この時点でマス 0, 3 にコマが乗っている。
    2. すべての駒を 2 大きいマスに進める。
      この時、マス 3 にある駒は移動先のマスが存在しないため (3+2=5 なので) 、盤上から取り除いて P に 1 を加算する。P の値は 3 になる。
      移動を終えた時点でマス 2 に駒が乗っている。

入力例 2

3
1 1 1

出力例 2

0

P の値が操作中に変化しない場合もあります。

入力例 3

10
2 2 4 1 1 1 4 2 2 1

出力例 3

8

Score : 200 points

Problem Statement

Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.

There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:

  1. Put a piece on Square 0.
  2. Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
    If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.

Print the value of P after all the operations have been performed.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 4
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the value of P after all the operations have been performed.

Sample Input 1

4
1 1 3 2

Sample Output 1

3

The operations are described below. After all the operations have been performed, P equals 3.

  • The operations for i=1:
    1. Put a piece on Square 0. Now, Square 0 has a piece.
    2. Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
  • The operations for i=2:
    1. Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
    2. Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
  • The operations for i=3:
    1. Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
    2. Advance every piece on the squares 3 squares ahead.
      Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
  • The operations for i=4:
    1. Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
    2. Advance every piece on the squares 2 squares ahead.
      Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
      After these moves, Square 2 has a piece.

Sample Input 2

3
1 1 1

Sample Output 2

0

The value of P may not be updated by the operations.

Sample Input 3

10
2 2 4 1 1 1 4 2 2 1

Sample Output 3

8