|
|
Anti WA11 Test: #X# #OX XOO Crosses win Anti WA12 Test: #X# O#O XOX Crosses win I hope these tests will be useful for you....... thanks a lot, i've AC with your test! It turns out that wrong tests are given. In a condition it is told that one player can win party one course. And it turns out what not one. No! "Head Judge observed that one player was able to win the game in one move." But Head Judge could be wrong. :) Is that true? Or i shouldn't implement case when nobody could win in one move? My code answers correct to your test cases, but Online Judge is saying W#11, I cannot find any case my solution fails. Can you provide more test cases, pls? And how people find the test case, do they figure it out or is there any way to know? У меня WA 9 и эти тесты работают Try this X## O#X XOO Crosses win But description says that one of teams must win in one move if we imagine that its their turn So I think that this test cant be real Statement lies: there are test cases when crosses needs two moves to win. That pisses me off, because it's always a great challange to understand the right meaning of a statement, but this one just doesn't give you a chance to do that. I think, there is no cases when crosses win in two moves I think, there is no cases when crosses win in two moves There are at least 3 cases that I found in the discussions: #X# #OX XOO #X# O#O XOX X## O#X XOO I'm sure, there're incorrect tests. Probably there're tests breaking these lines of statements: "However, Head Judge observed that one player was able to win the game in one move" If u had WA 14 (just like I do), take my notice into account. For example,
X## O#X XOO this one is incorrect. I've got WA#11. Here is my algorithm: For each row, column and two diagonals count number of 'X' and 'O'. - If in any case number of 'X' is 2 and # of 'O' is zero, then crosses win (coz it's crosses turn). - If # of 'X' is 1 and # of 'O' is 0, then increase counter for X wins (if it's larger than 1 Crosses win). - If # of 'O' is 2 and # of 'X' is 0, then increase counter for O wins (if it's larger than 1 Ouths win).
Then I'll check if counter for X wins is larger than 1, print crosses win - else if counter for O wins is larger than 1, print Ouths win - else Draw Do not use the fact that there are only 3 moves left. The traditional minimax is fast and simpler to write. Finally I decided to use your way and I got AC. First of all, I cost tree leafs and then run minimax on the tree. You did in the same way ? On the leaf-costing I don't like how I find index for the child nodes. Is there a more beautiful way then in function below: void costIt( char val=1, char pos = 2 ){ char res = 0; for( char i = 0; i < 3; i++ ){ if ( !arr[ f_x[ i ] ][ f_y[ i ] ] ){ arr[ f_x[ i ] ][ f_y[ i ] ] = val; res = check(); if ( res == 0 ) costIt( val == 1 ? -1 : 1, pos*2+1 ); else if ( !set[ pos > 10 ? (pos-1)/2 : pos ] ){ cost[ pos > 10 ? (pos-1)/2 : pos ] = res; set[ pos > 10 ? (pos-1)/2 : pos ] = true; } arr[ f_x[ i ] ][ f_y[ i ] ] = 0; pos++; } } } Edited by author 20.12.2011 10:24 Edited by author 25.01.2011 21:45 Hi, I got WA 4 because I missed out a case where the crosses can win the match straightaway with the first move itself. For example on a board like: #XX #OX #XO Answer will be crosses as he can place X at position (0, 0) and the game is over here itself. Varun I got AC but i have a question: why when i use: int f(char **v){ . . . } int main (){ char m[5][5]; f (m); } my code have compile error. and when i use : int f(char v[][5]){ . . . } int main (){ char m[5][5]; f (m); } it's correct. is'nt the type of m char **? if "yes" what's the type of m? sorry for my poor english. Edited by author 07.11.2010 21:51 Edited by author 23.07.2010 22:46 X## O#X XOO MY AC CODE SAY: DRAW (BUT IT CROSSES WIN) MAY BE IT WA11? Edited by author 22.03.2009 16:51 VERY THANKS! I'v got AC after your mess!) I found that an AC program(by others) gave me a incorrect answer in this test: #XO X#O X#O my program outputs:Ouths win but the AC program outputs:Crosses win So i think this test should be added up and the problem should be rejudged.thanks. Read "Site news". Your test is incorrect, because game is already finished by Noughts. I have Wrong Answer 14. I am testing my program nearly 2 hours and I can't find mistake. who had WA14 please tell me what kind of test is it? please help huh I got AC. very silly mistake :(( Edited by author 24.02.2007 01:11 I had WA 14 too. There is a mistake in my program: one of my functions used the global variables but some of variables shouldn't be global. Now is AC. What if: #OO OXX O## for example?! Your program will count two winning lines for Ouths and judges win for them, but it's a draw, isn't it. > What if: > > #OO > OXX > O## > > for example?! > > Your program will count two winning lines for Ouths and judges win > for them, but it's a draw, isn't it. > > What if: #OO OXX O## for example?! It's cann't be. Crosses and ouths must do only three moves, but in your example, ouths made 4. No recursion or brute force would needed, if you could guess some regularity. Of course this requires some thoughts from you ;) My main() contains only these lines but input: if(canWinNow('X') > 0 || existsMagicCell('X')) CROSSESWIN else if(canWinNow('O') > 1) OUTHSWIN else DRAW What canWinNow() does you may guess yourself, and existsMagicCell() contains about 10 lines and is not recursive. Who wants to find out my algo write a-zakh [at] yandex.ru i studied "experting systems" (Artificial intelligence (AI)) first home task was creating an intelligence to 3x3 CZ ) if any question about minimax write to my email - erko2@inbox.ru #include<iostream.h> int main() { char a[4][4];int i,j;bool p=true,k=true; for(i=1;i<=3;i++) for(j=1;j<=3;j++) cin>>a[i][j]; if(a[2][2]=='#'&&(a[1][1]=='X'&&a[1][3]=='X')||(a[3][1]=='X'&&a[3][3]=='X')) cout<<"Crosses win"<<endl; else{ for(i=1;i<=3;i++) for(j=1;j<=3;j++) if(a[i][j]=='#'&&p) {if(a[i-1][j-1]=='X'&&a[i+1][j+1]=='X') {cout<<"Crosses win"<<endl;p=false;} else if(a[i-1][j+1]=='X'&&a[i+1][j-1]=='X') {cout<<"Crosses win"<<endl;p=false;} else if(a[i][j-1]=='X'&&a[i][j+1]=='X') {cout<<"Crosses win"<<endl;p=false;} else if(a[i-1][j]=='X'&&a[i+1][j]=='X') {cout<<"Crosses win"<<endl;p=false;} else if(a[i-1][j-1]=='O'&&a[i+1][j+1]=='O') {cout<<"Ouths win"<<endl;p=false;} else if(a[i-1][j+1]=='O'&&a[i+1][j-1]=='O') {cout<<"Ouths win"<<endl;p=false;} else if(a[i][j-1]=='O'&&a[i][j+1]=='O') {cout<<"Ouths win"<<endl;p=false;} else if(a[i-1][j]=='O'&&a[i+1][j]=='O') {cout<<"Ouths win"<<endl;p=false;}
} for(i=1;i<=3;i++) for(j=1;j<=3;j++) {if(a[i][j]!='#'&&k&&p) {if(a[i][j]=='X'&&k&&p) if((a[i-1][j-1]=='X') ||(a[i+1][j+1]=='X')||(a[i+1][j-1]=='X')||(a[i-1][j+1]=='X')||(a[i-1][j]=='X')||(a[i+1][j]=='X')||(a[i][j-1]=='X')||(a[i][j+1]=='X')) {cout<<"Crosses win"<<endl;k=false;p=true;} } else if(a[i][j]=='O'&&k&&p) if((a[i-1][j-1]=='O') ||(a[i+1][j+1]=='O')||(a[i+1][j-1]=='O')||(a[i-1][j+1]=='O')||(a[i-1][j]=='O')||(a[i+1][j]=='O')||(a[i][j-1]=='O')||(a[i][j+1]=='O')) {cout<<"Ouths win"<<endl;k=false;p=true;} }
if(p==true&&k==true) cout<<"Draw"<<endl; } return 0; } On my computer for 1-st test from problem's statement answer is right. Where mistake?Thank!!! I can't find my mistake... using System; using System.Collections; namespace граф_1 {
class Class1 {
[STAThread] static void Main(string[] args)
{ //читаем int n = int.Parse(Console.ReadLine()); int m = int.Parse(Console.ReadLine()); int[,] graf = new int[n,n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) graf[i, j] = 0; for (int i = 0; i < m; i++) { string s = Console.ReadLine(); string[] s1 = s.Split(' '); graf[int.Parse(s1[0]) - 1, int.Parse(s1[1]) - 1] = 1; graf[int.Parse(s1[1]) - 1, int.Parse(s1[0]) - 1] = 1; } //Обходим все вершины int[] part = new int[n]; Queue q = new Queue(n); bool[] discovered = new bool[n]; for (int i = 0; i < n; i++) { part[i] = 0; discovered[i] = false; } part[0] = 1; bool b = true; //определяем, к какой доле они принадлежат q.Enqueue(0); discovered[0] = true; while(q.Count != 0) { int v = (int) q.Dequeue(); for(int i = 0; i < n; i++) { if(graf[v,i] == 1) { if (!discovered[i]) { discovered[i] = true; q.Enqueue(i); } if (part[i] != part[v]) part[i] = -part[v]; else b = false; } } if (!b) break; } if (b) { for (int i = 0; i < n; i++) if(part[i]==1) Console.WriteLine(i+1); } else Console.WriteLine(0);
} } } |
|
|