I've used DP approach.Towhid wrote:What is the idea behind the problem. I have not much studies in probability. Should I learn/ study something to solve this problem???
My AC's output:sluga wrote:Could someone give me your outputs for these inputs?
Code: Select all
9
18
35
86
171
257
342
428
513
770
856
1283
1350
1541
1617
1711
Yes, both of them always use maximum allowed number of soldiers.sluga wrote:It seems my code has a bug somewhere... I was affraid it was precision error, but this is much easier to solve
One more question: does the opponent always use maximum allowed number of soldiers?
problem statement wrote:It should not be a surprise that usually each player uses as many armies in a combat as he can, even though the rules allow him to use less.
Code: Select all
#include <iostream>
#include <cmath>
using namespace std ;
double prob [2000][1001] ;
int result [1001] ;
int main ()
{
for ( int i=0 ; i<2000 ; i++ )
prob [i][0] = 1 ;
for ( int i=0 ; i<=1000 ; i++ )
prob [1][i] = prob [0][i] = 0 ;
for ( int attack = 2 ; attack < 2000 ; attack ++ )
for ( int defend = 1 ; defend <= 1000 ; defend ++ )
prob [attack][defend] = (double)(15.0/36.0)* prob[attack][defend-1] + (double) (21.0/36.0)*prob[attack-1][defend] ;
memset ( result , 0 , sizeof result ) ;
int X ;
while ( cin >> X )
{
if ( !X ) break;
if ( result [X] == 0 )
{
for ( int attack = 2 ; attack < 2000 ; attack ++ )
if ( prob [attack][X] > 0.5 )
{
result [X] = attack ;
break ;
}
}
cout << result [X] << endl;
}
}
Could you explain us how did you get the following formula?arsalan_mousavian wrote:i got WA on this problem , can some one read my code and tell me if my approach is correct or not ?
arsalan_mousavian's main() wrote:.....prob[attack][defend] = (double) (15.0 / 36.0) * prob[attack][defend-1] +
.................................................. (double) (21.0 / 36.0) * prob[attack-1][defend];
on each level they roll the dice attakers hava the probabillity of 15/36 to kill one defender ( becauese there is 15 pair of numbers between 1 and 6 that the first one is greater than the second one ) and defender has the probabilty of 21/36 to kill one attackerMartin Macko wrote:Could you explain us how did you get the following formula?arsalan_mousavian wrote:i got WA on this problem , can some one read my code and tell me if my approach is correct or not ?arsalan_mousavian's main() wrote:.....prob[attack][defend] = (double) (15.0 / 36.0) * prob[attack][defend-1] +
.................................................. (double) (21.0 / 36.0) * prob[attack-1][defend];
Well, but in each attack both of them may use up to 3 armies, therefore on each side up to 3 armies may die in one attack.arsalan_mousavian wrote:on each level they roll the dice attakers hava the probabillity of 15/36 to kill one defender ( becauese there is 15 pair of numbers between 1 and 6 that the first one is greater than the second one ) and defender has the probabilty of 21/36 to kill one attacker
actually there are exactly bno = min (Attack, Defense) (<= 3) battles can happen in 1 attack, and exactly that many armies (in total, counting from both side) will die.Martin Macko wrote:Well, but in each attack both of them may use up to 3 armies, therefore on each side up to 3 armies may die in one attack.arsalan_mousavian wrote:on each level they roll the dice attakers hava the probabillity of 15/36 to kill one defender ( becauese there is 15 pair of numbers between 1 and 6 that the first one is greater than the second one ) and defender has the probabilty of 21/36 to kill one attacker