Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky? | xurshid_n | 1465. Игра в пешки | 18 июн 2020 17:23 | 5 |
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 |
Алгоритм | Ruslan | 1465. Игра в пешки | 21 май 2017 16:24 | 2 |
Пролистал кучу форумов, нахожу везде очень сложные формулы, может я слишком загоняюсь и есть какой то простой алгоритм решения? Кто нибудь может помочь? Ну ты короче берешь формулу (сложную). Считаешь по ней на своей машине ответы для первых i досок. Ищешь в ответах периодичность. Находишь периодичность, вбиваешь в программу минимально необходимые данные (первые j ответов и период) и сдаешь. Edited by author 21.05.2017 16:25 |
Tests | Felix_Mate | 1465. Игра в пешки | 14 июл 2015 15:22 | 1 |
Tests Felix_Mate 14 июл 2015 15:22 987654321 => white 123456789 => white 666 => black 999 => white 8 => black 13 => white 19 => white 5 => white Edited by author 26.12.2015 22:50 |
what formula for Sprague-Grundy ? I don't understand this sequences solve(i-2) ^ solve(n-i-1),what values in solve[0],solve[1],solve[2]?. Please help me | Anastasia | 1465. Игра в пешки | 31 авг 2014 01:14 | 1 |
Edited by author 31.08.2014 01:20 |
The N is too large to use an array... Do you have any ideas? | Moya | 1465. Игра в пешки | 13 янв 2012 18:16 | 5 |
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 |
Idea here | IIIeFF[PermSU] | 1465. Игра в пешки | 27 дек 2011 13:59 | 1 |
|
How to solve this problem in 0.015 s. I always got 0.031 s.!!!! | xurshid_n | 1465. Игра в пешки | 19 дек 2011 01:55 | 1 |
|
for calculating Nim-value ? | xurshid_n | 1465. Игра в пешки | 17 дек 2011 16:00 | 1 |
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? |
ask for circle !!!!! | mwh | 1465. Игра в пешки | 13 дек 2011 18:21 | 1 |
who can tell me what's the circle is (I have tested 1000,10000...all wrong) ask for help!!!! can you help me!!! |
Read this lessons | DixonD (Lviv NU) | 1465. Игра в пешки | 11 дек 2011 13:04 | 5 |
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... Help! | Dima_Philippov | 1465. Игра в пешки | 30 ноя 2011 03:25 | 1 |
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 |
Tests | Martin Ivanov | 1465. Игра в пешки | 18 апр 2009 02:48 | 1 |
Tests Martin Ivanov 18 апр 2009 02:48 22 White 45 White 72 Black 90 White 1421 White 1448 Black 999998 Black 5326236 White 9999992 White 523637458 Black |
Please, help!!!!!!!!!! | Ivanov Alexander | 1465. Игра в пешки | 23 июн 2007 21:03 | 8 |
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 Спасибо... А как-таки выигрывают черные при 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 Спасибо |
Can a pawn become a queen? | angel may cry | 1465. Игра в пешки | 23 дек 2006 01:57 | 3 |
If a pawn move to the bottom,will it become another one? Edited by author 12.08.2006 14:16 Are you thinking? It can't be with any play of players :) |
It's formula or there used theory of Grandi? | EfremovAleksei | 1465. Игра в пешки | 23 дек 2006 01:46 | 3 |
BOTH!!! You can generate answers with stupid Grundi but you must to see rule of answers period!!! |
I'm quite interested in this problem, is it related with "Nim"? | RoBa | 1465. Игра в пешки | 2 ноя 2006 03:24 | 10 |
It is related in a sense that Sprague-Grundy Function is the way to find answer in both games. 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? |
Are black can win, when board is bigger than 3x14? | Sni | 1465. Игра в пешки | 18 сен 2006 11:36 | 2 |
|
who will win if N=2? | Bill | 1465. Игра в пешки | 13 авг 2006 11:59 | 6 |
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? | Ziang Song | 1465. Игра в пешки | 12 авг 2006 15:14 | 2 |
Why N=5, the answer is WHITE? White move middle pawn and win. |
how to paly the chess? | boaz | 1465. Игра в пешки | 12 авг 2006 14:41 | 5 |
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. |