11061 - Playing War

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

11061 - Playing War

Post by Towhid »

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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 11061: Playing War

Post by Martin Macko »

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???
I've used DP approach.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 »

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

sluga
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia

Post by 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
A sta da radim

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

sluga wrote: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
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia

Post by sluga »

Thank you very much!
A sta da radim

sluga
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia

Post by 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?
A sta da radim

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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?
Yes, both of them 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.

sluga
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia

Post by sluga »

got ACC, thanks
A sta da radim

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by 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
In being unlucky I have the record.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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 ?
Could you explain us how did you get the following formula?
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];

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

Martin Macko wrote:
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 ?
Could you explain us how did you get the following formula?
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 attacker
In being unlucky I have the record.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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
New poster
Posts: 18
Joined: Sun Oct 14, 2001 2:00 am
Location: Ohio University
Contact:

Post by Mg9H »

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.

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by 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...
From 0 to 0

Post Reply

Return to “Volume 110 (11000-11099)”