Last Updated: 19 Mar, 2021
Ninja and the Storyteller
Easy
Asked in companies
Ninja is an avid story lover. Today, he decides to go to the famous Storyteller of Ninjaland to listen to new stories. The Storyteller takes 'Y' coins to tell one story. The Storyteller has also put on a special offer for Ninja that for every 'X' story that the Storyteller tells to Ninja, the Storyteller will tell one story to Ninja free of cost, i.e., without taking any extra coins. Ninja currently has 'Z' coins with himself. He wants to know how many stories the Storyteller will tell him if he goes to the Storyteller with 'Z' coins.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first and the only line of each test case contains three space-separated integers,'X', 'Y' and 'Z', denoting the number of stories to get one free story, the cost of one story, and the number of coins that Ninja has respectively.
Output Format:
For each test case, print a single line containing a single integer denoting the number of stories that the Storyteller will tell to Ninja.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10 ^ 4
2 <= X <= 10 ^ 9
1 <= Y , Z <= 10 ^ 9
Where 'T' denotes the number of test cases, 'X' denotes the number of stories that Ninja needs to listen to get one free story, 'Y' denotes the number of coins the Storyteller takes to tell one story, and 'Z' denotes the number of coins that Ninja has.
Time Limit: 1 sec.
Approaches
The idea is to first listen to all the paid storíes first, then listen to as many free stories as possible. Finding the number of paid stories is easy as the number of paid stories will always be floor(Z/Y) as Ninja needs exactly Y coins to listen to one story, and he has Z coins with him. To know the number of free stories that Ninja will listen to, we will store a count of the stories whose corresponding free stories have not been claimed by Ninja. Initially, the count of such stories will be equal to the number of paid stories (floor(Y/Z)) itself as Ninja has listened to only paid stories till now. After getting the count Ninja will use them to claim their corresponding free stories which can be expressed as paidStories/X, and then we will do the same with the remaining stories, i.e, the new stories we have listened to (paidStories/X) and the stories whose corresponding free stories were not claimed in the last iteration (paidStories%X). The sum of the two values paidStories/X and paidStories%X will be used as the new value of paidStories for the next iteration. Our final answer will be the sum of the total paid stories and the total free stories.
Steps:
- Let paidStories be a variable that stores the number of paid stories. Initialize it as Z / Y.
- Let freeStories be a variable that stores the count of free stories. Initialize it as 0.
- Define two variables storyCount to store the current count of stories whose free stories we have not claimed till now. Initialize it as paidStories
- While storyCount is greater than or equal X, then
- Let the number newStories store the stories that we will listen to in the current iteration. Initialize it as storyCount/X.
- Add newStories to freeStories.
- Let the number storiesLeft store the count of stories whose free stories were not claimed. Initialize it as storyCount%X. We will be using these stories in the next iteration to get free stories.
- Update storyCount to the sum of newStories and storiesLeft, as this is the count of stories, whose corresponding free stories have not been claimed till now.
- Return the final answer, i.e., the sum of paidStories and freeStories.