Toys & DS - a fun DSA questions
Little Axel has N toys numbered from 1 to N. Each toy has two properties:
Ei—enjoyment, which is the number of minutes Axel can play with toy number i without getting bored with it Ri—remembrance, which is the number of minutes it takes Axel to forget toy number i after having played with it. The toys are arranged in a circle, from 1 to N clockwise. Axel plays with them one by one.
When Axel reaches toy i which he has not played with yet, or which he has already forgotten about, he plays with it for Ei minutes and then immediately moves to the next one (clockwise).
If he reaches a toy that he has not forgotten yet (if less than Ri minutes have passed since the last time he finished playing with it), he will stop and cry.
We can define the time Axel spent playing as the sum of Ei of every toy Axel played with before stopping. If Axel played with a toy several times, it should be counted that many times.
Given the description of the toys, remove the smallest possible number of them in order to make Axel play either an indefinitely long time, or (if that is not possible) as long as possible before he stops.
Note:
Axel has never played with these toys before he cannot be left without toys he always starts with the toy that has the smallest number after finishing playing with the toy that has the largest number, he will move to the toy that has the smallest number.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. Next N lines contain 2 integers each: Ei and Ri. The i-th line is describing the toy number i.
Output
For each test case, output one line containing Case #x: y z, where:
x is the test case number (starting from 1)
y is the minimal number of toys to remove so that Axel could play with the rest of them either indefinitely or as long as possible
z is the longest time Axel will play in minutes or "INDEFINITELY" (without quotes) if he will play indefinitely long time.
Example
4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11
Output
Case #1: 0 5
Case #2: 0 INDEFINITELY
Case #3: 1 INDEFINITELY
Case #4: 0 25
Ei—enjoyment, which is the number of minutes Axel can play with toy number i without getting bored with it Ri—remembrance, which is the number of minutes it takes Axel to forget toy number i after having played with it. The toys are arranged in a circle, from 1 to N clockwise. Axel plays with them one by one.
When Axel reaches toy i which he has not played with yet, or which he has already forgotten about, he plays with it for Ei minutes and then immediately moves to the next one (clockwise).
If he reaches a toy that he has not forgotten yet (if less than Ri minutes have passed since the last time he finished playing with it), he will stop and cry.
We can define the time Axel spent playing as the sum of Ei of every toy Axel played with before stopping. If Axel played with a toy several times, it should be counted that many times.
Given the description of the toys, remove the smallest possible number of them in order to make Axel play either an indefinitely long time, or (if that is not possible) as long as possible before he stops.
Note:
Axel has never played with these toys before he cannot be left without toys he always starts with the toy that has the smallest number after finishing playing with the toy that has the largest number, he will move to the toy that has the smallest number.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. Next N lines contain 2 integers each: Ei and Ri. The i-th line is describing the toy number i.
Output
For each test case, output one line containing Case #x: y z, where:
x is the test case number (starting from 1)
y is the minimal number of toys to remove so that Axel could play with the rest of them either indefinitely or as long as possible
z is the longest time Axel will play in minutes or "INDEFINITELY" (without quotes) if he will play indefinitely long time.
Example
4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11
Output
Case #1: 0 5
Case #2: 0 INDEFINITELY
Case #3: 1 INDEFINITELY
Case #4: 0 25
https://www.cplusplus.com/forum/beginner/272345/
You're never going to learn how to cook by simply standing in the kitchen watching other people create recipes.
By now, you've glossed over way too many earlier (and easier) problems to catch up.
Unless you put in the time and effort yourself to solving problems, each new problem will look harder and more opaque than the last.
Learning this stuff is the journey, not the destination.
How you learn to navigate all those road blocks, dead ends, narrow passes, rickety bridges etc is what makes you a programmer. Not you arrival in programmer-town.
This isn't the matrix where you can simply download experience on demand and then calmly announce you "know kung-fu".
Because as soon as someone in the real world asks you "show me", you're screwed.
You can watch other people solve problems for the rest of your life, and only get 10% of what it takes to actually solve them yourself.
Make an effort, or just give up.
Go back to the beginning and start with the first problem you didn't solve entirely yourself without asking for outside help, and see if you now know enough to solve it yourself.
You're never going to learn how to cook by simply standing in the kitchen watching other people create recipes.
By now, you've glossed over way too many earlier (and easier) problems to catch up.
Unless you put in the time and effort yourself to solving problems, each new problem will look harder and more opaque than the last.
Learning this stuff is the journey, not the destination.
How you learn to navigate all those road blocks, dead ends, narrow passes, rickety bridges etc is what makes you a programmer. Not you arrival in programmer-town.
This isn't the matrix where you can simply download experience on demand and then calmly announce you "know kung-fu".
Because as soon as someone in the real world asks you "show me", you're screwed.
You can watch other people solve problems for the rest of your life, and only get 10% of what it takes to actually solve them yourself.
Make an effort, or just give up.
Go back to the beginning and start with the first problem you didn't solve entirely yourself without asking for outside help, and see if you now know enough to solve it yourself.
Topic archived. No new replies allowed.