Show all threads Hide all threads Show all messages Hide all messages |
WA6 :) | pperm | 1540. Battle for the Ring | 28 Aug 2021 19:29 | 3 |
WA6 :) pperm 25 Sep 2007 20:21 Give me some tests. Some my tests Input: 3 9 2 1 3 1 4 1 1 1 5 3 1 2 1 3 1 2 1 Output: G 1 2 Input: 1 5 2 3 1 4 5 Output: G 1 3 Input: 1 5 5 4 1 3 2 Output: G 1 1 Edited by author 25.09.2007 20:24 AAAA, yea, how stupid was I(( |
WA6 | chenyushuo | 1540. Battle for the Ring | 3 Apr 2015 17:59 | 1 |
WA6 chenyushuo 3 Apr 2015 17:59 Could you give me some tests to train my code? I WA in test 6 many times and I don't know why anymore.. I need some people to help me. Here is my code: #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; int sg[55][110][110]; int a[110][110]; int n; bool v[110], l[110]; int mex ( int l, int r, int x ){ if ( sg[x][l][r] != -1 ) return sg[x][l][r]; if ( l > r ) return 0; int i, j, k; int p, ss; memset ( v, false, sizeof (v) ); for ( i = l; i <= r; i ++ ){ p = a[x][i]; ss = 0; k = l; for ( j = l; j <= r; j ++ ){ if ( a[x][j] <= p ){ ss ^= mex ( k, j-1, x ); k = j+1; } } ss ^= mex ( k, r, x ); v[ss] = true; } for ( i = 0; ; i ++ ){ if ( v[i] == false ){ sg[x][l][r] = i; return i; } } } int get_sg ( int x ){ int i, j, k; for ( i = 1; i <= a[x][0]; i ++ ) sg[x][i][i] = 1; return mex ( 1, a[x][0], x ); } void get_way ( int ans ){ int i, j, k, x, y, o; int p, s; for ( i = 1; i <= n; i ++ ){ for ( j = 1; j <= a[i][0]; j ++ ){ p = a[i][j]; s = 0; o = 1; for ( k = 1; k <= a[i][0]; k ++ ){ if ( a[i][k] <= p ){ s ^= mex ( o, k-1, i ); o = k+1; } } s ^= mex ( o, a[i][0], i ); if ( (ans^sg[i][1][a[i][0]]^s) == 0 ){ printf ( "%d %d\n", i, j ); return; } } } } int main (){ int i, j, k; scanf ( "%d", &n ); k = 0; memset ( sg, -1, sizeof (sg) ); for ( i = 1; i <= n; i ++ ){ scanf ( "%d", &a[i][0] ); for ( j = 1; j <= a[i][0]; j ++ ) scanf ( "%d", &a[i][j] ); get_sg (i); k ^= sg[i][1][a[i][0]]; } if ( k == 0 ) printf ( "S\n" ); else{ printf ( "G\n" ); get_way (k); } return 0; } |
WA #12 | Spatarel Dan Constantin | 1540. Battle for the Ring | 31 Oct 2014 06:15 | 1 |
WA #12 Spatarel Dan Constantin 31 Oct 2014 06:15 The following test helped me: Input: 17 84 47 44 99 60 43 14 91 8 39 26 15 41 70 90 41 72 48 20 59 3 68 15 21 78 95 5 22 60 61 88 43 59 84 94 19 26 7 61 85 97 86 51 89 55 40 29 78 39 100 89 41 19 3 62 97 98 18 70 9 79 57 51 37 92 96 55 17 55 67 54 3 52 4 92 59 44 20 36 34 72 24 27 90 79 88 38 28 57 7 36 35 16 38 24 7 34 30 76 88 97 29 90 100 32 33 58 27 5 46 61 76 69 87 65 99 26 3 26 34 61 13 69 76 51 92 83 36 73 10 23 69 38 64 69 21 49 78 100 53 23 12 28 92 50 44 42 27 98 20 60 59 32 28 34 82 71 68 17 96 77 91 64 66 7 84 87 55 62 86 59 84 49 86 27 98 29 69 24 27 88 83 37 19 63 22 53 85 90 21 80 18 64 44 84 70 79 22 76 40 59 34 24 7 71 2 4 51 70 27 29 9 61 65 80 23 87 84 8 28 4 87 45 67 82 80 88 61 53 15 100 11 100 75 69 70 77 24 73 98 50 1 59 63 18 38 85 4 73 92 83 76 31 79 95 64 59 34 24 63 49 76 26 100 2 94 70 30 18 42 80 19 94 38 81 11 27 18 14 99 61 48 26 91 27 72 55 37 6 30 99 6 57 24 5 11 18 26 92 87 19 71 57 13 60 38 23 38 55 89 88 15 36 66 58 62 37 64 98 42 45 97 99 54 72 56 64 41 81 55 27 100 78 36 64 37 73 86 27 79 26 14 45 62 79 54 75 16 17 25 9 62 73 60 67 44 15 30 85 47 36 63 98 13 50 61 2 22 99 28 52 24 93 49 37 72 2 12 39 19 36 99 32 8 10 98 3 24 79 39 23 14 54 20 27 3 81 80 77 79 7 80 2 99 28 39 22 30 2 12 100 89 11 31 48 20 80 50 96 58 41 18 23 94 37 1 48 69 80 76 47 38 56 1 89 83 91 10 12 44 22 11 32 84 93 79 55 24 80 50 81 20 19 4 65 56 56 65 76 36 40 75 73 95 75 61 30 17 23 93 60 44 56 43 79 48 73 33 72 52 35 4 24 53 59 40 60 15 4 36 2 96 10 74 42 36 87 71 4 9 64 15 4 19 57 34 18 29 66 41 32 52 45 55 5 55 47 16 69 50 3 70 97 64 96 39 99 34 9 54 42 24 68 97 94 24 30 12 4 47 4 36 99 48 90 55 55 36 70 75 38 25 45 86 88 92 24 39 25 85 92 18 60 60 66 54 35 47 17 39 93 20 26 43 20 15 49 74 3 71 48 92 95 44 29 82 35 53 20 11 89 12 80 48 23 45 53 57 91 69 47 36 89 72 30 8 39 79 33 93 49 80 36 95 24 64 76 10 68 96 73 56 59 52 56 81 49 8 89 91 29 88 78 17 59 8 76 49 38 8 41 38 39 76 32 62 40 7 24 59 54 96 15 12 47 22 44 47 81 85 38 9 72 15 77 30 22 4 79 11 63 71 48 2 99 79 15 90 38 38 48 43 33 62 7 32 35 50 78 16 86 67 76 57 82 5 39 55 8 17 66 71 39 65 72 37 96 86 26 33 76 74 27 8 87 33 91 74 35 21 89 20 87 16 77 68 20 15 23 28 83 40 50 73 4 73 10 99 58 87 83 85 60 10 93 99 94 35 72 28 55 12 48 42 27 76 61 99 42 35 78 24 74 27 96 30 99 57 80 8 44 15 93 55 24 37 53 17 71 76 97 78 39 96 71 18 71 31 16 12 66 93 87 91 71 34 72 69 91 52 76 86 66 20 40 41 56 45 9 79 72 5 56 11 100 26 80 70 8 47 33 73 39 71 16 9 5 87 29 47 38 56 84 55 76 23 95 31 19 4 61 43 8 68 5 60 93 84 29 Output: G 1 67 |
In case of WA 13 | MVM | 1540. Battle for the Ring | 28 Jul 2014 21:48 | 1 |
If you have WA 13, try this test: 3 1 1 1 1 1 1 It may help you. |
Thanks a lot for author! Very fun problem! | EfremovAleksei | 1540. Battle for the Ring | 20 Aug 2013 00:14 | 4 |
It's the 3rd day I'm trying do break that "fun"... :D can anyone provide any idea? I personally solved in a bruteforce manner with DSU. |
WA6 | Tranvick | 1540. Battle for the Ring | 20 Apr 2012 14:23 | 1 |
WA6 Tranvick 20 Apr 2012 14:23 What is this test? I cannot find my mistake. |
WA 5 | MarioYC | 1540. Battle for the Ring | 16 Jan 2012 15:44 | 1 |
WA 5 MarioYC 16 Jan 2012 15:44 Hi, I'm using grundy numbers for this problems, however I get WA 5. #include <cstdio> #include <cstring> using namespace std; int n[50],a[50][100]; int g[50][100][100]; int main(){ int K;
scanf("%d",&K);
for(int i = 0;i < K;++i){ scanf("%d",&n[i]);
for(int j = 0;j < n[i];++j) scanf("%d",&a[i][j]); }
memset(g,0,sizeof g);
bool have[201];
for(int k = 0;k < K;++k){ for(int l = 1;l <= n[k];++l){ for(int i = 0;i + l <= n[k];++i){ memset(have,false,sizeof have);
for(int j = i;j < i + l;++j){ int x = a[k][j],sum = 0;
for(int s = i;s < i + l;){ if(a[k][s] <= x) ++s; else{ int e = s;
while(e < i + l && a[k][e] > x) ++e;
sum ^= g[k][s][e - 1]; s = e + 1; } }
have[sum] = true; }
while(have[ g[k][i][i + l - 1] ]) ++g[k][i][i + l - 1]; } } }
int G = 0;
for(int k = 0;k < K;++k) G ^= g[k][0][n[k] - 1];
if(G){ puts("G");
bool found = false;
for(int k = 0;k < K && !found;++k){ for(int i = 0;i < n[k] && !found;++i){ G = 0;
for(int j = 0;j < K;++j) if(j != k) G ^= g[k][0][n[j] - 1];
int x = a[k][i],sum = 0;
for(int s = 0;s < n[k];){ if(a[k][s] <= x) ++s; else{ int e = s;
while(e < n[k] && a[k][e] > x) ++e;
G ^= g[k][s][e - 1]; s = e + 1; } }
if(G == 0){ found = true; printf("%d %d\n",k + 1,i + 1); } } } }else puts("S");
return 0; } |
Does title contain 2 'l's and one 't' on purpose? | SkidanovAlex | 1540. Battle for the Ring | 23 Oct 2009 03:02 | 1 |
I mean, why is it Batlle instead of Battle? |
Please help, admins please also look here! | Denis Koshman | 1540. Battle for the Ring | 21 Sep 2008 13:53 | 3 |
After trying to solve this most-likely-not-the-hardest-one problem for more than a week I started doubting in my understanding of its statement. The question is: what does it mean "remaining chains"? Are players enforced to finish up some chain before touching others (and so recursively) or are they allowed to pick ANY chain after breaking up some other? I.e. what is the answer for the following test: 2 2 1 2 2 1 2 Is it G 1 1 or is it S ? If Gandalf converts chain -1-2- into chain -2- by dematiarilizing ring 1, is Sauron allowed to pick some ring in the other -1-2- chain or is he enforced finish off that -2- remnant of the first chain before getting hands onto the 2nd one? And what is the answer to this test? 3 3 1 2 3 2 1 2 1 1 Edited by author 21.09.2008 12:17 Answers to both tests are S. Players are allowed to pick any chain in their turn. |
please explain the example for me | Viktorianka | 1540. Battle for the Ring | 6 Mar 2007 17:10 | 2 |
thie example: 3 1 2 1 1 1 answer 1 1 if G choose the first ring from the first row, then the first row will be dematerialised, because there is 3 and all numbers of the first row <=3. So S will win in the next move. Read the statement more carefully: "Each of the next K lines describes the corresponding chain in the following format: the first number is the length of the chain" So 3 is the number of elements in the first chain. |