Show all threads Hide all threads Show all messages Hide all messages |
Solution 3(Idea). | Felix_Mate | 1398. Bishop and Pawn | 22 Jun 2015 14:00 | 1 |
Можно решить задачу эмпирически. В начале найдем решения по-честному,когда пешка стоит на 1 горизонтали(т.е. игра почти завершена). Все состояния A[x,y,1] нам уже известны,а состояния A[x,y,i] i>1 неизвестны. Из очередного состояния (т.е. увеличив i и рассмотрев любые x,y-коорд. слона) будем выбирать макс. значение среди всех переходов. Если состояние,в которое мы попадаем неизвестно,то снова вызываем рекурсию,пока не попадем в известное(такое всегда будет,т.к. на каждом шаге пешка сдвигается хотя бы на 1,а состояния А[x,y,1] известны). Как только из данного состоя ния мы попадаем во все известные, то данное состояние становится известным. |
Solution 2( Idea) | Felix_Mate | 1398. Bishop and Pawn | 22 Jun 2015 13:44 | 1 |
This problem can solve DP. DP[x,y,i] где x,y-координаты слона and i- ордината пешки. DP[x,y,1] найти легко( либо сразу съели и выигр.,либо проиграли). Ответ: DP[x1,y1,y2]. Учитываем,в какой вертикали находится пешка(первая вертикаль-нижняя строка). Рассмотрим очередное состояние(т.е. момент,когда i>1 и все состояния [х,y,j] j<i известны). Во-первых, возможно,что состояние тривиально(т.е. мы съедаем пешку). Тогда DP[x,y,i]:=1; Во-вторых, возможно,состояние непонятно. Тогда сделаем все возможные ходы слоном, пешка соответственно сдвигается на 1 или 2 позиции(в зависимости от горизонтали) и мы попадаем в предыдущую позицию(т.е. уже известную). Среди таких переход выбираем переход с макс. итогом( особый случай это горизонталь 2,где пешка может сходить на 2 клетки, но суть та же).Так же не следует забывать,что мы можем перегородить дорогу пешки. В этом случае нам(слону) ничья как минимум обеспечена. Сложность O(n^4) (n*n- размеры поля; параметр i<=n, все переходы - это <=2*n позиций(не считая случая с 2 горизонталью,но это реально не влияет), позиций слона n*n). Edited by author 22.06.2015 13:50 Edited by author 22.06.2015 13:51 Edited by author 22.06.2015 13:55 |
About Solution (Idea) | Felix_Mate | 1398. Bishop and Pawn | 22 Jun 2015 13:31 | 1 |
It's problem has mathematical solution in O(1). You must analyze several variants ( when y2=1,2,3,>=4 ) and find strategy for white. |
Some tests | Vavan | 1398. Bishop and Pawn | 25 Jun 2013 13:40 | 3 |
? Edited by author 10.05.2012 01:08 c2 b2 WHITE a2 b2 DRAW a1 f7 WHITE d2 f7 WHITE g6 e2 BLACK h2 g2 DRAW h8 g7 WHITE |
some hints to ... | Oleg Strekalovsky aka OSt [Vologda SPU] | 1398. Bishop and Pawn | 25 Jul 2009 21:05 | 2 |
1.If bishop can eat pawn - he can Win. 2.Use matrix (rows - digits, columns - letters). Left-top cell has coords (8,a), right-bottom has coords (1,h) 3. Pawn go down (to row "1" ). 3.If you use recursive functions : 1 - goPawn() 2 - goBishop() Pay attention, that checking (bishop win,pawn win,draw) must be only in special places(goPawn() and/or goBishop() ) Good luck. Edited by author 25.07.2009 21:04 Edited by author 25.07.2009 21:04 kill yourself by hitting the wall. =) it's very simple problem, to my mind. |
What if pawns eats bishop? | Denis Koshman | 1398. Bishop and Pawn | 22 Apr 2009 19:11 | 2 |
It's not clear if black player can continue movement or not after eating white bishop. Bishop moves first, so if at first pawn can capture bishop it does not matter. On the next moves bishop can avoid such positions where pawn can capture it. |
Tests | Брэнд | 1398. Bishop and Pawn | 15 Mar 2008 20:16 | 4 |
Tests Брэнд 6 Mar 2008 21:50 Please, give me several tests because I cannot find my mistake. And explain why I have WA#2. Edited by author 15.03.2008 20:17 Re: * Nikita 15 Mar 2008 16:42 You have a mistake in "Draw". Change in 6 line a='h' to a='g' and c='g' to c='h'. And in 9 vice versa. * Брэнд 15 Mar 2008 20:16 I'm a stupid man... Thanks! |
Tests | Брэнд | 1398. Bishop and Pawn | 6 Mar 2008 21:50 | 1 |
Tests Брэнд 6 Mar 2008 21:50 Please, give me several tests because I cannot find my mistake. |
please help me? I have question. | {AESC USU} Dembel | 1398. Bishop and Pawn | 16 Jan 2007 17:59 | 3 |
"with the usual chess rules"? if (pawn on the 7th horisontal) then can pawn go on the 5th horisontal? Edited by author 16.01.2007 15:44 |
Test#10 incorrect... | RockBeat | 1398. Bishop and Pawn | 4 Jan 2007 01:28 | 7 |
........ ........ char a[3],b[3]; scanf("%s%s",b,a); x0=*a-'a',y0=a[1]-'1'; x1=*b-'a',y1=b[1]-'1'; if(x0<0||x0>7||y0<0||y0>6|| x1<0||x1>7||y1<0||y1>7) x0/=0; ........ ........ This code receive Crash (integer division by zero). Edited by author 01.01.2007 07:28 Algebraic chess notation(srandart chess notation): ...First, the files (that is, lines running parallel to the direction the players are facing) are labelled with LOWERCASE letters a through h... Test#10 has uppercase letters. To admins: please fix bug. It seems you are right, I have AC. Many thanks! I think Test#20 has uppercase letters, too! The problem statement is unclear. It is not said that the letters might be capital. And the sample does not show it either. So the statement will be 99% misunderstood. That is why the authors should avoid such fuzzy expressions as "standard chess notation". Surely, the problem statement (or the tests) should be fixed. Now tests contain only LOWERCASE latin letters. Problem has been rejudged, 4 authors got AC. Edited by author 04.01.2007 01:29 |
Free Pascal sucks again (+) | Dmitry 'Diman_YES' Kovalioff | 1398. Bishop and Pawn | 2 Jan 2007 13:19 | 2 |
Such code gets CE: bx:=ord(LowerCase(ch)[1])-96; You should use explicit typecast like that: bx:=ord(LowerCase(string(ch))[1])-96; Edited by author 01.01.2007 17:41 Download FreePascal 2.0.4 and have no problem... I did so!!! |
To admins | Loky_Yuri [USTU] | 1398. Bishop and Pawn | 1 Jan 2007 21:06 | 3 |
In the task said that the bishop is white. And then said that "the bishop is initially positioned at any square different from the pawn’s square". But it is WHITE bishop. Something strange... But it is WHITE bishop. And what? White bishop can be situated on black field too. Sorry! I understood my mistake... |
New problem is available to solve! 1398 "Bishop and Pawn" (-) | Vladimir Yakovlev (USU) | 1398. Bishop and Pawn | 31 Dec 2006 06:46 | 3 |
Program that getfor test b1 a3 answer WHITE receives AC. I think this test should be added because there are only 4 draw cases. |