## VM7WC '16 #5 Silver - Jayden Plays Video Games

View as PDF

Points: 15
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

I made a mistake while writing this problem, causing it to be much harder than originally intended. My flawed solution used simple recursion, but the actual solution requires segment trees. To fix this problem, I've made a new silver problem for this contest. Please solve that one instead.

Jayden is a little kid that likes to play video games. One of the games that he likes to play is Lumberjack, where the player, a lumberjack, must make a living by cutting down trees in a forest and selling them to a carpenter.

While playing the game, Jayden finds trees in the forest, all in a line. The tree will be at position on the line, with no tree sharing the same point. Since Jayden is a smart kid, he realizes that the trees will act like dominoes. When cutting a tree, it will fall to either the left or the right of the tree. If the tree has a height of and falls to the right, it will cause all trees located at positions to , inclusive, to fall to the right as well. Similarly, if that tree falls to the left, all trees located at positions to , inclusive, will also fall to the left.

For example, say that there are four trees of height at positions , , , and . If Jayden cuts down the tree at position and causes it to fall to the right, the second and third trees will also fall as a result. When the tree at position falls, it causes the tree at position to fall as well. By cutting down just one tree, the tree at position , Jayden can cause all of the trees in the line to fall.

Jayden can control the direction a tree falls when he cuts it. Given the line of trees he has found, what is the least amount of trees that Jayden has to cut in order to cause the entire line of trees to fall?

#### Input Specification

On the first line will be the integer . The next lines will contain and , two integers that describe the position and height of the tree.

#### Output Specification

On a single line, print out the least amount of trees that Jayden has to cut down.

#### Sample Input

4
1 2
3 9
7 1
6 1

#### Sample Output

1

• commented on Feb. 7, 2016, 2:58 p.m. edited
• commented on Feb. 5, 2016, 6:52 p.m. edit 5

Do the test cases include cases such as:

input: 4 1 1 3 1 5 1 7 6

output: 1

My code cannot pass the case above and i get AC.

• commented on Feb. 5, 2016, 11:31 p.m.

Not the same case, but two of my AC solutions give a different answer for

6
10 1
20 1
30 1
40 100
50 1
60 1
• commented on Feb. 5, 2016, 9:28 p.m.

It should -- I remember having something similar as a case.