fork(1) download
  1. #include<stdio.h>
  2. #include<string.h>
  3. char s[1100];
  4. int digitCount[10];
  5. int main() {
  6. int t,l,last,i,flag;
  7.  
  8. scanf("%d",&t);
  9. while(t--){
  10. scanf("%s",s);
  11. l=strlen(s);
  12. flag=0;
  13. int sum=0;
  14.  
  15. for(i=0;i<10;i++) digitCount[i]=0;
  16.  
  17. for(i=0;i<l;i++){
  18. digitCount[s[i]-'0']++;//count the numbers
  19. sum+=s[i]-'0'; // storing the sum
  20. }
  21.  
  22. if(digitCount[0]>0){
  23. last=0;
  24. digitCount[0]--;
  25. }
  26. else if(digitCount[5]>0){
  27. last=5;
  28. digitCount[5]--;
  29. }
  30. else{
  31. printf("impossible\n");continue;
  32. } //to check the divisibility by 5
  33.  
  34.  
  35. if(sum%3==1){
  36. // if remainder is 1 then number can be 1 4 7
  37.  
  38. if(digitCount[1]>0){
  39. digitCount[1]--;
  40. }
  41. else if(digitCount[4]>0){
  42. digitCount[4]--;
  43. }
  44. else if(digitCount[7]>0){
  45. digitCount[7]--;
  46. }
  47.  
  48. // (2*2)%3=1
  49. // as removing 2 single digit is costlier than removing single digit so
  50. // i have put this condition at last
  51.  
  52. else if(digitCount[2]>=2){
  53. digitCount[2]-=2;
  54. }
  55. else if(digitCount[2]>=1&&digitCount[5]>=1){
  56. digitCount[2]--;digitCount[5]--;
  57. }
  58. else if(digitCount[5]>=2){
  59. digitCount[5]-=2;
  60. }
  61.  
  62. else if(digitCount[8]>=1&&digitCount[2]>=1){
  63. digitCount[8]--;digitCount[2]--;
  64. }
  65.  
  66. else if(digitCount[8]>=1&&digitCount[5]>=1){
  67. digitCount[8]--;digitCount[5]--;
  68. }
  69.  
  70. else if(digitCount[8]>=2){
  71. digitCount[8]-=2;
  72. }
  73.  
  74. else{
  75. printf("impossible\n");continue;
  76. }
  77. }
  78.  
  79. else if(sum%3==2){
  80. // if remainder is 2 then number can be 2 5 8
  81. if(digitCount[2]>0){
  82. digitCount[2]--;
  83. }
  84. else if(digitCount[5]>0){
  85. digitCount[5]--;
  86. }
  87. else if(digitCount[8]>0){
  88. digitCount[8]--;
  89. }
  90.  
  91. else if(digitCount[1]>=2){
  92. digitCount[1]-=2;
  93. }
  94. else if(digitCount[4]>=1&&digitCount[1]>=1){
  95. digitCount[4]--;digitCount[1]--;
  96. }
  97. else if(digitCount[4]>=2){
  98. digitCount[4]-=2;
  99. }
  100. else if(digitCount[7]>=1&&digitCount[1]>=1){
  101. digitCount[7]--;digitCount[1]--;
  102. }
  103. else if(digitCount[7]>=1&&digitCount[4]>=1){
  104. digitCount[7]--;digitCount[4]--;
  105. }
  106. else if(digitCount[7]>=2){
  107. digitCount[7]-=2;
  108. }
  109.  
  110. else{
  111. printf("impossible\n");continue;
  112. }
  113.  
  114. sum-=2;
  115. }
  116.  
  117. //now sum%3=0
  118. // now selecting the last digit
  119.  
  120. if(last==0){
  121. for(i=1;i<10;i++){
  122. if(digitCount[i]>0) break;
  123. }
  124. }
  125.  
  126. if(i==10) {printf("0\n");continue;}
  127.  
  128. for(i=9;i>=0;i--){
  129. while(digitCount[i]>0){
  130. printf("%d",i);
  131. digitCount[i]--;
  132. }
  133. }
  134.  
  135. // now printing the last digit
  136.  
  137. printf("%d\n",last);
  138.  
  139. }
  140. return 0;
  141. }
Success #stdin #stdout 0s 3472KB
stdin
4
15022
1528
00000000000000
0000000001
0000000005
0
stdout
5220
825
0
0