New tests have been added to the problem. 82 authors have lost AC. My ac program gives wrong answer on this test: Input 1 101234 Output: 14231 Edited by author 31.08.2017 22:02 Edited by author 31.08.2017 22:02 Your test is added. Thank you! Edited by author 11.09.2017 21:42 is this problem supposed to be solved with random shuffling, or i just got lucky? >I think only search is okey. >I think only search is okey. ur solution is not good. the better way is use remainder(mod) I wanna offer my solution (I think, author had in view same method). Arrange digits of the number in a such way: (non-zero digits in arbitrary order)1234(all zeroes). Then, we can permute only 1234 among them in order to receive a number, dividing by 7 (You can prove it). Edited by author 12.04.2005 01:20 Is anybody willing to tell me why it works? @Nickolas > Is anybody willing to tell me why it works? You can write a sample program and see, that permutations of 1234 produce all possible remainders in division by 7. So <some non-zero numbers><permutation on 1234><zeros> always fits. I wanna offer my solution (I think, author had in view same method). Arrange digits of the number in a such way: (non-zero digits in arbitrary order)1234(all zeroes). Then, we can permute only 1234 among them in order to receive a number, dividing by 7 (You can prove it). Edited by author 12.04.2005 01:20 No sorting, just "cutting" one : 1,2,3,4 from input number; selecting zeros and constructing "possible answer" :) cant we use dynamic programming.It is a O(2^numberofdigits) algorithm. Can any one tell me why the other solution works? all numbers in the input have at least one '1', one '2', one '3' and one '4' in their decimal form, is this clear now ? ;) Thank you for you help. Now I guess it's the key of this problem. If I can get any of 0~6 by putting 1,2,3,4 as the first 4 digits. Validator was updated. Sample input and output were changed (sample input is Test 1). 109 authors lost AC. New tests were added. 66 authors lost AC. I solved this problem by probabilistic approach and brute-force. No TLE, just stupid WA :) Hahaha. It's guro method! [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich WA#4 [3] // Problem 1095. Nikifor 3 9 Jan 2007 15:47 Please, give me some difficult tests... Send them please on snipious@mail.ru!!! Can anyone give some tests??? I have found a mistake in the decision!!! The test was from a series: 1 10234 a very useful test! i may make the mistake. I really don't like to do it, but i just can't find what is wrong in my code... In my pc it works pretty fine.. but, i got WA 4#... my bugged code: ========================================================== #include <iostream> using namespace std; void reordena(int *numeros[],int difzero,int num) { int rdn1,rdn2,aux; rdn1 = rand() % difzero; rdn2 = rand() % difzero; aux = numeros[num][rdn1]; numeros[num][rdn1] = numeros[num][rdn2]; numeros[num][rdn2] = aux; } void permuta(int *numeros[],int num,int tam) { int cont,cont2,aux,difzero=0,resp=0; int mult; long int contador=0; for(cont=0;cont<tam-1;cont++) { for(cont2=0;cont2<tam-1;cont2++) { if(numeros[num][cont2]==0) { aux = numeros[num][cont2]; numeros[num][cont2] = numeros[num][cont2+1]; numeros[num][cont2+1] = aux; } } } for(cont=0;cont<tam;cont++) { if(numeros[num][cont]!=0) difzero++; } mult=1; for(cont=difzero-1;cont>=0;cont--) { aux=(numeros[num][cont]*mult); resp+=aux; mult*=10; } while(resp%7!=0) { reordena(numeros,difzero,num); mult=1; resp=0; for(cont=difzero-1;cont>=0;cont--) { aux=(numeros[num][cont]*mult); resp+=aux; mult*=10; } contador++; if(contador>=1000000) { numeros[num][0]=0; resp=0; } } } int main() { int N,cont,**numeros,*tam; char aux[200]; cin >> N; if(N<0) exit(0); if(N>10000) exit(0); tam = new int[N]; numeros = new int*[N]; for(cont=0;cont<N;cont++) { numeros[cont] = new int[20]; } for(cont=0;cont<N;cont++) { cin >> aux; tam[cont] = strlen(aux); if(tam[cont]>20) { exit(0); } for(int cont2=0;cont2<tam[cont];cont2++) { numeros[cont][cont2]=aux[cont2]-'0'; } permuta(numeros,cont,tam[cont]); } system("cls"); for(cont=0;cont<N;cont++) { for(int cont2=0;cont2<tam[cont];cont2++) { if(numeros[cont][0]==0) { if(cont2==0) cout << "0"; } else if(numeros[cont][cont2]!=0) cout << numeros[cont][cont2]; } if(cont!=N-1) cout << endl; } delete [] numeros; delete [] tam; return 0; } ======================================================== please, help if you can =/ May be late=) but if input data contain 0 all zeroes must be output for example input: 1 12300134 example output: 13124300 int pre[8]={4123,1324,1234,1324,1243,2413,2134,4123};
LL solve(LL n) { if (n/10000==0) return 4123;
int k,j,i,p,b[5]={0}; LL m=0; LL res=10000; while (true) { p=n%10; n/=10;
if (p==0) b[0]++; else if (p==1 && !b[1]) b[1]=1; else if (p==2 && !b[2]) b[2]=1; else if (p==3 && !b[3]) b[3]=1; else if (p==4 && !b[4]) b[4]=1; else { m+=p*res; res*=10; } if(n==0) break; }
if (m==0) { i=-1; res=1; for (j=1;j<=b[0];j++) res*=(LL)10; while (true) { i++; if ((pre[i]*res)%7==0) break; } return pre[i]*res; } else if(b[0]>0) { for (i=0;i<b[0];i++) { m*=(LL)10; res*=(LL)10; } k=m%7; return m+pre[7-k]; }
else { k=m%7; m+=pre[7-k]; return m; } } where LL is unsigned long long. Can give me some tests if possible Edited by author 19.07.2006 14:18 wa too,trace my code remainder[7-((a%7)*4)%7],so when a%7 ==0; the remainder[7] is uninitilized, Notification. In your answer there are no leading zeroes and the length of your answer is equal to the length of corresponding number. (Otherwise possible WA4) Hey, dude, thank you. I just wanted to make sure everybody understand what Evgeniy tries to explain here. If you have something like this 1 100200300400 your answer should be something like this 324100000000 (not 000000003241 and not 3241) Good luck
Thank you! I've got AC now. What method or algorithm can we use? I don't get it... please help.. If you've got a mistake, check your program on the test: 1 1234567890 ;) Can you give me the test which answer is =0. And I got WA#4 please give me the tests. Edited by author 25.06.2008 12:15 Edited by author 25.06.2008 12:15 I have WA (5) but I think there is no such input (if all numbers contain 1,2,3 and 4) It is said: "Nikifor knows that a certain positive integer has in its decimal form each of the digits 1,2,3,4." and in input data there is a number with 5. Where is mistake? Its example 531234 could be 531342 and more over, why not a special judge?!! Edited by author 12.07.2005 07:38 I'm curious is unsigned long long enough to contain all positive numbers from input ? Can I avoid dealing with strings? Edited by author 22.07.2006 01:59 Edited by author 22.07.2006 01:59 This problem has a little trick. So you don't need to use big num . "int" or "short int" is enough :) My algo is o(N*length(ch)) DELETED!!! NOW AC!! Edited by author 05.08.2005 23:02 please help me!! There are long numbers! Even unsigned __int64 is not enough! |
|