OJ Board

Martin Macko wrote:

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

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 wrote:

Martin Macko wrote:

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

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.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std ;
double prob [2000][1001] ;
int result [1001] ;
double f ( int attack , int defend ) 
{
	if ( attack <= 1 || defend <=0 ) return 0 ;
	return prob [attack][defend] ;
}
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 ++ ) 
		{
			int size ;
			size = min ( attack  ,  defend ) ;
			if ( size > 3 ) size = 3 ;
			prob[attack][defend] = 0 ;
			for ( int state = 0 ; state<(1<<size) ; state ++ )// generating all the possible result ( one from attack or defend kill ) 
			{
				double temp;
				int countAttack , countDefend ;
				countAttack = countDefend = 0 ;
				temp = 1 ;
				for ( int pos = 0 ; pos < size ; pos ++ ) 
				{
					if ( ( 1<<pos ) & state ) // if in the pos th dice attackers win and kill one defendent
					{
						temp *= ( 15.0/36.0 );
						countDefend ++ ;// the number of killed defenders
					}
					else
					{
						temp*=(21.0/36.0) ;
						countAttack ++ ;// the number of killed attackers
					}
				}
				temp *= prob [attack - countAttack][defend - countDefend ];
				prob [attack][defend] += temp ;
			}
		}
	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;

	}


}

arsalan_mousavian wrote:i think it should be min ( defend , attack -1 ) , since the attackers should always keep one soldier in their territory , by the way i got still WA , can someone check my code plz ?

arsalan_mousavian's main() wrote:.........int size ;
.........size = min ( attack..,..defend ) ;
.........if ( size > 3 ) size = 3 ;
.........prob[attack][defend] = 0 ;
.........for ( int state = 0 ; state<(1<<size) ; state ++ )// generating all the possible result ( one from attack or defend kill )
.........{
...............
.........}

arsalan_mousavian wrote:

Mg9H wrote:

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.

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.

i think it should be min ( defend , attack -1 ) , since the attackers should always keep one soldier in their territory , by the way i got still WA , can someone check my code plz ?

Martin Macko wrote:

arsalan_mousavian wrote:i think it should be min ( defend , attack -1 ) , since the attackers should always keep one soldier in their territory , by the way i got still WA , can someone check my code plz ?

Note, that there may be different numbers of attacker's and defender's armies in one attack. Suppose somewhere before the end of the game the attacker has 4 armies and the defender has just 1 army. In that case there are 3 attacking armies and 1 defending army in the next attack. However, in the following part of your ode you assume that in each attack both the defender and the attacker have the same number of armies (namely size):

arsalan_mousavian's main() wrote:.........int size ;
.........size = min ( attack..,..defend ) ;
.........if ( size > 3 ) size = 3 ;
.........prob[attack][defend] = 0 ;
.........for ( int state = 0 ; state<(1<<size) ; state ++ )// generating all the possible result ( one from attack or defend kill )
.........{
...............
.........}

Read the third paragraph of the problem statement more carrefully.

when one side has attackers and the other side has 1 defender they only compare the maximum dice of each side

joeluchoa wrote:I've used DP in my solution for this problem!
However, i got WA for a precision error.
How to I solve this error?

joeluchoa wrote:I think that is precision error. For example, if I have 2 armies and my enemy have 1000, the prabability of me win is too low.

joeluchoa wrote:I've got probability[100][171] = 0.499692911297
and probability[100][172] = 0.512962827527

( probability[D][A] is the probability of win with A armies attack and D armies defence)

joeluchoa wrote:Here is my code:

joeluchoa's main() wrote:.......
....probability[2][3] = prob_combat[1][1][2]
........................+ prob_combat[1][1][1] * probability[1][2];
.......

joeluchoa's main() wrote:.......
....for ( i = 3; i < MAX_DEFENCE; i++ ){.
...........
........probability[i][2] = prob_combat[1][1][1] * probability[i-1][2];.
...........
....}
.......