fork(1) download
copy 
  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
comments (?)
stdin
copy 
4
15022
1528
00000000000000
0000000001
0000000005
0
stdout
copy 
5220
825
0
0
https://ideone.com/6dvkFD
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!