VM7WC '16 #5 Silver - Jayden Plays Video Games

View as PDF

Submit solution

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

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 N trees in the forest, all in a line. The i^\text{th} tree will be at position x_i 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 h_i and falls to the right, it will cause all trees located at positions x_i+1 to x_i+h_i, inclusive, to fall to the right as well. Similarly, if that tree falls to the left, all trees located at positions x_i-h_i to x_i-1, inclusive, will also fall to the left.

For example, say that there are four trees of height 2 at positions 1, 2, 3, and 5. If Jayden cuts down the tree at position 1 and causes it to fall to the right, the second and third trees will also fall as a result. When the tree at position 3 falls, it causes the tree at position 5 to fall as well. By cutting down just one tree, the tree at position 1, 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 N (1 \le N \le 10^3). The next N lines will contain x_i and h_i (1 \le x_i, h_i \le 10^8), two integers that describe the position and height of the i^\text{th} tree.

Output Specification

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

Sample Input

1 2
3 9
7 1
6 1

Sample Output



  • 7
    jeffreyxiao  commented on Feb. 7, 2016, 2:58 p.m. edited

  • 0
    XIAOAGE  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.

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

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

      10 1
      20 1
      30 1
      40 100
      50 1
      60 1

    • -1
      JeffreyZ  commented on Feb. 5, 2016, 9:28 p.m.

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