COCI '14 Contest 6 #1 Paprika

View as PDF

Points: 4 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Young Marin is working as an assistant chef in a popular restaurant called Plavi 9 where the daily offer includes, among other things, stuffed peppers. Every assistant chef knows that the peppers are stuffed when they are young, so he decided to prepare the meal using only peppers not older than days. Marin will serve all the other peppers fresh, as an appetizer. Luckily, as Croatia entered the EU, there is a new law enforced. The law states that every pepper has to have its ID card at any moment. Marin can easily determine the age of a pepper by looking at its ID card.

It is less known that peppers have, besides official documents, their own life purposes and ambitions. More precisely, every pepper knows from an early age whether they want to be served as a fresh or stuffed pepper when they grow up. Bearing that in mind, you are aware of the problems peppers are facing while waiting in line to be filled. The life purpose of some peppers is to be a part of the dish, but they are too old, and some peppers want to be served fresh, but will be filled.

Because the peppers aren't aware of Marin's number , they have decided to rectify the injustice using the following strategy. The first pepper tries to switch its ID card with second pepper, then the second pepper tries to switch its ID card with the third pepper and so on until the end of the line. Two peppers will switch their ID cards if the pepper that has a larger number on the ID card it's currently holding wants to become a filled pepper, and the one with the smaller number doesn't. The peppers will not switch ID cards if they have equal numbers on them. Your task is to determine the number of peppers that will have their life purpose completed.

Input Specification

The first line of input contains two integers and from the task.

Each of the following lines contains two integers and that describe the peppers in the order which they're waiting in line to be filled.

The number is printed on the ID card of a pepper and represents its age in days, and number represents its life purpose ( if pepper wants to be served fresh or if it wants to be served as a filled pepper).

Output Specification

The first and only line of output must contain the number of peppers that will have their life purpose completed.

4 5
2 0
3 0
4 0
5 0

0

Explanation for Sample Input 1

All peppers are young enough, but not a single one of them wants to be stuffed.

5 5
3 1
2 0
13 1
2 0
10 1

5

Explanation of Sample Input 2

Every two adjacent peppers switched their ID cards.

6 10
15 1
12 1
8 0
10 1
3 0
1 1

4