I, found, my bug. :) I get TLE for test13,it is because that my idea is to circulate all the SG-values. Can you give me some ideas?Thank you so much. I've also using a period of 68, but WA 36 #include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<cstring> #include<map> #include<queue> #include<stack> #include<utility> #include<cstdlib> #include<string> #include<set> #include<limits> #include<iomanip> #include<fstream> #include<sstream> #define INF 2147483647 #define LLD int #define clr(a) memset(a,0,sizeof(a)) #define reset(a) memset(a,-1,sizeof(a)) #define BD(i, j) (i >= 0 && i < N && j >= 0 && j < M) #define PRINT_VAR(X) (cout << #X << " -> " << X << endl) #define PI acos(0) #define MAX_INT 2147483647 #define SIZE 1005 #define MOD 1000000009 using namespace std; int X[] = {0, 1, 0, -1}; int Y[] = {1, 0, -1, 0}; /* right, down, lft, up */ int M, N; long long res; typedef pair<int, int> Point; int dp[SIZE]; int solve(int n) { if (dp[n] == -1) { set<int> s; s.insert(solve(n - 2)); for (int i = 2; i < n; i++) { s.insert(solve(i-2) ^ solve(n-i-1)); } dp[n] = 0; while (s.find(dp[n]) != s.end()) dp[n]++; }
return dp[n]; } int main() { int t, tc, x, y, z; int i, j, k, l, h; char ch; #ifndef ONLINE_JUDGE //freopen("input.txt", "r", stdin); #endif
reset(dp); dp[0] = 0; dp[1] = dp[2] = 1; cin >> N; cout << (solve(N % 68) ? "White" : "Black") << endl;
return 0; } I changed ``` cout << (solve(N % 68) ? "White" : "Black") << endl; ``` to ``` cout << (solve(N % (68*2)) ? "White" : "Black") << endl; ``` and it got AC Пролистал кучу форумов, нахожу везде очень сложные формулы, может я слишком загоняюсь и есть какой то простой алгоритм решения? Кто нибудь может помочь? Ну ты короче берешь формулу (сложную). Считаешь по ней на своей машине ответы для первых i досок. Ищешь в ответах периодичность. Находишь периодичность, вбиваешь в программу минимально необходимые данные (первые j ответов и период) и сдаешь. Edited by author 21.05.2017 16:25 987654321 => white 123456789 => white 666 => black 999 => white 8 => black 13 => white 19 => white 5 => white Edited by author 26.12.2015 22:50 Edited by author 31.08.2014 01:20 I'll give you two hints: 1) You must be familiar with nimbers. 2) Look for a cycle. I used another program to find a cycle when generating nimbers up to let's say 10 000. Good luck ;) can you tell me what the cycle is? thanks. The sequence of answers is periodic(period length=34). But it becomes periodic from a certain position. can you send your AC code to me?please to this e-mail: mwhaea123456@163.com Thank you so much nim[0] = 0, nim[1] = 1; i = 2..n, b = {0..i} j = 0..i { left = max(0, j-1); right = max(0, i - j -2); v = nim[left] ^ nim[right]; exclude (b, v) } nim[i] = min{x, which, x in b} ...... Is This way right? who can tell me what's the circle is (I have tested 1000,10000...all wrong) ask for help!!!! can you help me!!! Thank you very much! Finally I got AC. I've calculating the nim-sequence for this game about 3 hours)))) Thank you! Very useful articles. thank you sincerely!!!!!!!!!!!!!!!!! wonderful artical!!!!!!!!!!!!!! great ideas!!!!!!!!!!!!!!!!!!!!!!1 Edited by author 13.12.2011 17:50 WA84... What it can be? P.S. Accepted)) Very stupid bag... Edited by author 30.11.2011 03:25 Edited by author 02.12.2011 02:23 22 White 45 White 72 Black 90 White 1421 White 1448 Black 999998 Black 5326236 White 9999992 White 523637458 Black How can white win, if n=12??? I think white showld start the game using the pawn with number 4. Edited by author 19.06.2007 16:36 Thank you! Good Luck) Спасибо... А как-таки выигрывают черные при n=20, если белые толкают седьмую пешку, и после размена остается с одной стороны 5, а с другой 12 пешек? Напиши мыло здесь, я тебе все расскажу) Edited by author 23.06.2007 00:13 Edited by author 23.06.2007 00:13 Edited by author 23.06.2007 00:22 ivanovalexalex@mail.ru Спасибо If a pawn move to the bottom,will it become another one? Edited by author 12.08.2006 14:16 i think yes Are you thinking? It can't be with any play of players :) second ;) BOTH!!! You can generate answers with stupid Grundi but you must to see rule of answers period!!! Also... It is related in a sense that Sprague-Grundy Function is the way to find answer in both games. Thanks. I got it :) I heard about using Spraga-Grundi numbers a lot...but I don't especially know how to use them and can't smb post here some links or words to know more about them? Thanks for such a cool link. Yes. Really cool link. Now we see, this problem is just a book-problem. which chapter should i read? are these correct 14 White 123456 White 70 Black 1960 Black 2944384 Black Or not? Black Why "black"? 1. white moves a pawn black beats 2. white beats black has no move Yes, it seems to me, that white. If so, then only n = 4 is blackwinners for N=8,9 the answer is black, isn't it? I think if N==9 the answer is white, even I think we can easily see this holds for all odd N Why N=5, the answer is WHITE? White move middle pawn and win. how to paly the chess? co-ask Pawn can 1) move one cell forward (if that cell is empty) or 2) attack cell which is one step diagonally forward, and occupied by opponent's pawn (which is beaten and removed after attack; player's pawn is moved to the cell of beaten one) In that problem if player can attack with one of his pawns he must attack in that turn. Edited by author 12.08.2006 13:33 I still don't understand....... A pawn can move one field along the vertical and beat one field along the diagonal. Black pawns move from i'th row to (i-1)'th only. White pawns move from i'th row to (i+1)'th only. The row number 1 is the bottom and the row number 3 is the top. |
|