11061 - Playing War

[Towhid]

What is the idea behind the problem. I have not much studies in probability. Should I learn/ study something to solve this problem???

[Martin Macko]

What is the idea behind the problem. I have not much studies in probability. Should I learn/ study something to solve this problem???

I've used DP approach.

[Dreamer#1]

Yes, DP works fine. Nice problem, enjoyed solving it at the contest.
I wish we had such nice problems in my region.

[sluga]

Could someone give me your outputs for these inputs?

5
10
20
50
100
150
200
250
300
450
500
750
789
901
945
1000
0

[Martin Macko]

Could someone give me your outputs for these inputs?

My AC's output:

Code: Select all

9
18
35
86
171
257
342
428
513
770
856
1283
1350
1541
1617
1711

[sluga]

Thank you very much!

[sluga]

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?

[Martin Macko]

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?

Yes, both of them always use maximum allowed number of soldiers.

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.

[sluga]

got ACC, thanks

[arsalan_mousavian]

i got WA on this problem , can some one read my code and tell me if my approach is correct or not ?

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;

	}


}

thanks in Adavnce . . .
Arsalan

[Martin Macko]

i got WA on this problem , can some one read my code and tell me if my approach is correct or not ?

Could you explain us how did you get the following formula?

.....prob[attack][defend] = (double) (15.0 / 36.0) * prob[attack][defend-1] +
.................................................. (double) (21.0 / 36.0) * prob[attack-1][defend];

[arsalan_mousavian]

i got WA on this problem , can some one read my code and tell me if my approach is correct or not ?

Could you explain us how did you get the following formula?

.....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 attacker

[Martin Macko]

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

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.

[Mg9H]

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

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.

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.

[Towhid]

Well, how the winning of a single combat is determined? I thought, in a 3 against 3 battle the combat is continued until all 3 of any side are died. But in that case there can be more than 3 battles...