| UFPE Starters Final Try-Outs 2026 |
|---|
| Finished |
Pou, Grisi, and Guilherme were starving, so they decided to have dinner at Subway. While they sat waiting for their meals and playing Brawl Stars, the kitchen exploded out of nowhere, sending food flying everywhere! Pou, being the only one quick on his feet, decided to take advantage of the situation to satisfy his hunger. He closed his game and prepared to attack!
All food items and Pou are located on a two-dimensional plane, where $$$y = 0$$$ represents the ground. At time $$$t = 0$$$, Pou is at position $$$(0,0)$$$ and the $$$i$$$-th food is at position $$$(x_i,y_i)$$$. Each food falls at a constant vertical speed of $$$1$$$ unit per second, while Pou can move left or right at a constant speed of $$$1$$$ unit per second.
In other words, if in a time $$$t$$$ a food item is at $$$(x,y)$$$, at time $$$t+1$$$ it will be at $$$(x,y-1)$$$. Simultaneously, if in a time $$$t$$$ Pou is at $$$(x,0)$$$, at time $$$t+1$$$ he can be at $$$(x,0)$$$, $$$(x+1,0)$$$, or $$$(x-1,0)$$$.
Pou can eat food item $$$i$$$ if and only if he is at position $$$x_i$$$ at the exact moment the food hits the ground ($$$y = 0$$$). For hygiene reasons, he will not eat any food that has already touched the ground before his arrival.
Grisi and Guilherme were so stunned by the explosion that they forgot how many food items Pou ate, but they remember the initial positions of all the food items. Knowing that Pou ate the maximum possible amount of food, your mission is to determine that number.
The input consists of several lines. The first line contains $$$n$$$ ($$$1 \le n \le 2 \cdot 10^3$$$), the number of food items.
The following $$$n$$$ lines contain two integers $$$x$$$ and $$$y$$$ ($$$1 \le x,y \le 10^6$$$), the $$$i$$$-th line represents the initial position of food $$$i$$$.
It is guaranteed that no two food items occupy the same initial position, that is: $$$\forall i\forall j((i\neq j) \implies (x_i,y_i) \neq (x_j,y_j))$$$.
The output must contain a single integer: the maximum number of food items Pou could have eaten.
32 24 36 6
2
32 32 4727 67
2
| Name |
|---|


