i have WA #2 #include <iostream> #include <stdio.h> using namespace std; int main() { int n, m; cin >> n >> m; int win = 0; for(int i = 0; i < m; i++) { int a; cin >> a; n -= a; if(i % 2 == 0) win = 2; else win = 1; }
cout << win << endl;
return 0; } I think, this problem should have lower difficulty... 15 3 1 5 11 correct output:1 This is a big point I think should take care. what the algo of this problem? please^_^ bottom-up DP, where DP[i] show will the first player win or lose the game with i rocks left, if everybody plays right and it's 1st player turn. Obviously, if i rocks left, and 1st player will lose, than i + k[j] is winning position for him (because if he throws away k[j] rocks, 2nd player will have i-th position, which is losing position for him an winning position for the first player). It's almost ready solution, just write a programm. Good luck! 4 3 1 1 3 1 4 or 1 3 4 1 3 1 4 sum of all is 17 and first player wins not second, can somebody explan? Edited by author 18.10.2012 17:08 Edited by author 18.10.2012 17:11 can it be solved with backtracking? but i think recursion depth will exceed memory and also lime will not pass, right? try a test where first player wins Can someone write the sequence of stone that lead to player 2 lose plz ? 15 3 3 5 7 AC return "1", but the right answer is "2", isn't it ?? NO the first man can get 5,then leave 10 stones. if second man get 3 ,the firtst man get 7 if second man get 5 ,the firtst man get 5 if second man get 7 ,the firtst man get 3 so,right answer is "1"
The First man can get 5, then leave 10 stones: -> if Second man get 3, the Firtst man get 7 -- First loose; -> if Second man get 5, the Firtst man get 5 -- First loose; -> if Second man get 7, the Firtst man get 3 -- First loose; So, the Second -- WIN! => Right answer "2"!!! Edited by author 04.08.2009 16:54 It is not a valid test. Because if first take 7, and second take 7, then nobody can take last 1 stone. Test is valid only if GCD(of all amounts and N) equal to smallest amount. I think, that tests for this problem are bad. For test 3 3 3 2 1 my AC program gives answer 2, while answer 1 is correct. P.S. My first AC solution is incorrect, but i hope, that my second AC solution is correct. a lot of thnx the numbers k1, …, km, are not sorted this test is available 17 3 1 4 3 try to sort k1, …, km, i get AC when i do it #include<math.h> #include<stdio.h> int main() { int t[100],n,m,i,j,tr[10010]; scanf("%d",&n); scanf("%d",&m); for(i=1;i<=m;i++) {
scanf("%d",&t[i]); } for(i=1;i<=n;i++) { if(i<=t[1]) tr[i]=2; else { for(j=1;j<=m;j++) { if(i>t[j]) {printf("hhhhhhhhhhhh %d %d %d \n",i,t[j], tr[i-t[j]]); if(tr[i-t[j]]==2) {tr[i]=1; printf("hahaha\n"); break; } } } if(j==m+1) tr[i]=2;
} printf("%d %d\n",i,tr[i]); }
printf("%d",tr[n]);
return 0; } (excuesme for my bad english) if the test like this: 5 3 2 4 5 correct ans is: 2 because: stones:-------0-1-2-3-4-5 winner player:1-0-2-0-2-2 (0 for unknown position) but AC solution returns 1 the numbers of the second line are not the positions of the stones,but the numbers of stones you can take each time Edited by author 25.03.2009 13:31 #include<stdio.h> #include<stdlib.h> #include<string.h> void main() { int i,j,len,count=0,m,n; char ch[2001]; scanf("%s",ch); len=strlen(ch); if(len%2==0) { m=i=len/2-1; n=j=len/2; } else { m=i=len/2; n=j=len/2; } for(m,n;m>=0;m--,n++) { if(ch[m]>ch[n]) { break; } if(ch[m]<ch[n]) { count=1; break; } } if(count) { ch[i]=ch[i]+1; } else { ch[i]=ch[i]; } for(;i>=0;i--,j++) { ch[j]=ch[i]; } ch[j]='\0'; printf("%s\n",ch); } Moya programma ne prohodit test#5... Na chto on napravlen??? |
|