VENOM - Touch of Venom

no tags 

Sometimes you have to try fighting even though you know that your enemy is very powerful than you. Your hero with initial health H is about to fight against a venomous enemy who has a poisonous value of P. The enemy's poison deals i*P damage at it's ith attacking chance(i>=1). The hero dies when his health becomes <=0. After enemy's attack, if the hero survives, he heals himself with a health of A by using his skills. Then the enemy gets the chance again and the cycle continues till the hero dies. Find the survival time of the hero. You can safely assume that the hero is mortal.

Example Scenario:

Initial Health(H) = 10, Poison (P) = 2, Heal value(A) = 1

At time 1, enemy does 1*2 damage reducing the hero's health to 8

At time 2, hero heals himself by 1 increasing his health to 9

At time 3, enemy does 2*2 damage reducing the hero's health to 5

At time 4, hero heals himself by 1 increasing his health to 6

At time 5, enemy does 3*2 damage and kill the hero.

The hero survived 5 units of time.

Input:

The first line consists of an integer t, the number of test cases. For each test case there is a line with 3 integers H, P and A.

Output:

For each test case, find the survival time of the hero.

Input Constraints:

1<=t<=10^6

1<=H<=10^6

1<=P<=10^6

0<=A<P

Sample Input:

3

3 7 2

81 4 1

87 8 4

Sample Output:

1

13

9


hide comments
[Lakshman]: 2014-06-12 14:55:30

@XYZ read the comment of cegprakash he already told that this can be done in O(1) if you have O(1) algorithm you can get AC with scanf & printf if not try fast I/O, my algorithm is [spoiler removed]. will try to find out O(1).

Last edit: 2014-12-08 13:22:33
XYZ: 2014-06-12 14:43:33

@cegprakash : Could you give me a hint as to what more I can do to avoid a TLE? Submission number 11745710. Thanks.

___Durgesh___: 2014-06-08 23:19:19

AC in 1 go ^-^

cegprakash: 2014-06-04 21:50:03

O(1) solution is also possible for this problem!

785227: 2014-06-04 18:12:59

Awesome problem.... Enjoyed a lot while solving it :)

cegprakash: 2014-05-31 15:49:10

[themighty] deathsurgeon : Try to get ACC without using Fast IO. Use scanf/printf to get ACC.

Reply (mighty) -> I always try scanf/printf first to get AC. Then I go for fast IO, when I find no other optimization possible. My first solution run in 1.06 secs. :( :( Is it possible for a better solution without fast IO?

Last edit: 2014-06-05 12:56:33
shiv prasad chabarval: 2014-05-26 09:52:48

a silly mistake caused me 3 WA :(

[themighty] deathsurgeon: 2014-05-23 23:29:37

AC in 1 go! Thats rare! And here I was waiting for TLE.
@cegprakash: Great question! Enjoyed solving it!

Last edit: 2014-05-23 23:31:20
RIVU DAS: 2014-05-22 21:15:41

I wouldn't call it easy!!

cegprakash: 2014-04-17 09:19:59

@Bhavik: Is it that hard to write a test case generator and compare your output against a brute force solution?


Added by:cegprakash
Date:2014-03-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF