All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Dhoni and holidays!
Tag(s):
No tags
Problem
Editorial
Analytics

Dhoni has n days of vacations! So he decided to go either driving or do his cricket practice. Dhoni knows the following information about each of these n days: whether he can drive his car or not (due to odd-even rule) and whether the cricket academy is open for practice on that day. For the i-th day there are four options:

1.He can not drive his car and the academy is closed.

2.He can not drive his car and the academy is open.

3.He can drive his car and the academy is closed.

4.He can drive his car and the academy is open.

On each of these days Dhoni can either have rest or drive his car (if it is possible on this day), or go to academy (if the academy is open on this day).

Find the minimum number of days on which Dhoni will have rest (it means, he will not go driving and academy at the same time). The only limitation that Dhoni has — he does not want to do the same activity on two consecutive days: it means, he will not go for driving on two consecutive days, and academy for practice on two consecutive days.

Input Format

The first line contains a positive integer n (1 ≤ n ≤ 100) — the number of days of Dhoni's holidays.

The second line contains the sequence of integers a1, a2, ..., an (0 ≤ ai ≤ 3) separated by space, where:

ai equals 0, if on the i-th day of holiday he can not drive his car and the academy is closed.

ai equals 1, if on the i-th day of holiday he can not drive his car and the academy is open.

ai equals 2, if on the i-th day of holiday he can drive his car and the academy is closed.

ai equals 3, if on the i-th day of holiday he can drive his car and the academy is open.

Output format

Print the minimum possible number of days on which Dhoni will have rest.

SAMPLE INPUT
4
1 3 2 0
SAMPLE OUTPUT
2
Explanation

In the first test case Dhoni can go to academy on the day number 1 and go for driving on the day number 3. Thus, he will have a rest for only 2 days

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Netaji Subhas Institute of Technology

Challenge Name

NOVICE - The Online Programming Challenge

Notifications
View All Notifications

?