263 - Number Chains

[Raiyan Kamal]

The given number is not consiedered as a member of the chain.

[mukeshtiwari]

here is my code plz help me
#include<stdio.h>
#include<string.h>
void sort(char* a,int l)
{
int i,j,temp;
for(i=0;i<l-1;i++)
{
for(j=i+1;j<l;j++)
{
if(a>a[j])
{
temp=a[j];
a[j]=a;
a=temp;
}
}
}

}
void reverse(char *a,char *b,int l)
{ int i;
for(i=l-1;i>=0;i--)
b[(l-1)-i]=a;
}
void subtract(char* a,char* b,char* c,int* l)
{ int k=0,i,j,v,p[20],flag=1,u=0;
int o;
o=*l;
for(i=0;i<o;i++)
p=a;
for(i=0;i<(*l);i++)
{
if(a>=b)
{
c=a-b[i];
if(c[i]==0 && i==(*l)-1)
(*l)--;
if((*l)==0)
(*l)++;
flag=0;
}
if(a[i]<b[i] && a[i]!=0)
{

a[i]+=10;
a[i+1]-=1;
c[i]=a[i]-b[i];

}
if(a[i]==0 && flag==1)
{
for(j=i;;j++)
{
if(a[j]==0)
k++;
else
break;
}
a[i]=a[i]+10;
for(j=i+1;j<k;j++)
a[j]=9;
a[j]=a[j]-1;
c[i]=a[i]-b[i];
if(k==o-1)
(*l)--;
}
flag=1;
}
for(i=0;i<(*l);i++)
{
if(c[i]==0)
u++;
}
if(u==(*l))
(*l)=1;
for(i=0;i<o;i++)
printf("%d",p[(o-1)-i]);
printf(" - ");
for(i=0;i<o;i++)
if(b[(o-1)-i]!=0)
printf("%d",b[(o-1)-i]);
if((*l)==1 && b[0]==0)
printf("%d",b[0]);
printf(" = ");
for(i=0;i<(*l);i++)
printf("%d",c[((*l)-1)-i]);
printf("\n");
}
int compare(char* e,char* c,int l,int j)
{
int i,flag=1;
//printf("\n value of e in compare fun in % d call\n",j);
// for(i=0;i<l;i++)
//printf("%d",e[i]);
//printf("\n");
for(i=0;i<l;i++)
{
if(e[i]==c[(l-1)-i])
{
//printf("e[%d]=%d c[%d]=%d ",i,e[i],l-1-i,c[l-1-i]);
flag=0;
}
else
{
flag=1;
//printf("e[%d]=%d c[%d]=%d ",i,e[i],l-1-i,c[l-1-i]);
break;
}
//printf("\n");
}
//printf("flag=%d\n",flag);
return(flag);
}
void copy(char* c,char* a,int l)
{
int i;
for(i=0;i<l;i++)
a[i]=c[(l-1)-i];
}
void copy1(char* c,char* e,int l )
{
int i,j;

for(i=0;i<l;i++)
e[i]=c[(l-1)-i];
}
main()
{
char a[20],b[20],c[20],e[2000][20];
int t,l,count,flag=0,i,j;
while(scanf("%s",a) && a[0]!='0')
{
printf("Original number was ");
count=0;
l=strlen(a);
for(i=0;i<l;i++)
{
a[i]=a[i]-'0';
e[0][i]=a[i];
printf("%d",a[i]);
}
// printf("\ne is \n");
// for(i=0;i<l;i++)
//printf("%d",e[0][i]);
printf("\n");
for(t=0;;t++)
{
count++;
sort(a,l);
reverse(a,b,l);
subtract(a,b,c,&l);
for(i=0;i<count;i++)
{
flag=compare(e[i],c,l,i);
//printf("\n value of flag in main %d\n",flag);
if(flag==0)
break;
}
if(flag==0)
break;
copy(c,a,l);
copy1(c,e[count],l);

}
printf("Chain length %d\n\n",count);
for(i=0;i<20;i++)
{
a[i]='\0';
b[i]='\0';
c[i]='\0';

}
for(i=0;i<2000;i++)
for(j=0;j<20;j++)
e[i][j]='\0';
}
}

[chulin nagasaki]

Would that imput be valid? Which would the output be for this imput?
192
00192
55694
what does he mean with "Note that 0 is a permitted digit"?

I GOT MANY WA
THANKS FOR ADVANTAGE

[mamun]

Output for above input:

Code: Select all

Original number was 192
921 - 129 = 792
972 - 279 = 693
963 - 369 = 594
954 - 459 = 495
954 - 459 = 495
Chain length 5
Original number was 192
921 - 129 = 792
972 - 279 = 693
963 - 369 = 594
954 - 459 = 495
954 - 459 = 495
Chain length 5
Original number was 55694
96554 - 45569 = 50985
98550 - 5589 = 92961
99621 - 12699 = 86922
98622 - 22689 = 75933
97533 - 33579 = 63954
96543 - 34569 = 61974
97641 - 14679 = 82962
98622 - 22689 = 75933
Chain length 8

So you see there is no difference between 192 and 00192. Most probably such are not there.

what does he mean with "Note that 0 is a permitted digit"?

I'm not so sure what he exactly mean. Maybe telling to continue processing when you get 0 (like the 3rd input in the problem sample) or he simply meant arranging digits, say 6509, in decreasing order you get 9650 and in increasing order you get 0569 => 569.

[gabox]

I think you're not giving importance to a little detail:
"4. and repeat these steps unless the new number has already appeared in the chain"

You gotta verify if the number has already appeared on the chain, so, you gotta have a register of each number and search the new number. That's all you need to fix.

[chetan]

here is my code . i dont know why CE......
it compiles properly on my machine..........

[

[chetan]

i have modified the code a bit.
i use only C - style character arrays instead of strings.
but inspite of that judge gives me CE............
it compiles and runs properly on my machine.........

[Darko]

You forgot to include cstdio. This should be in C++ forum, btw.

[chetan]

ok fine here is the final code and the judge gives me a WA
plz give some test cases atleast ...........

Code: Select all

CODE DELETED AFTER AC....

[rhsumon]

I have the same problem -------- 1st i got CE bcoz of ignoring cstdio but after that i have got WA plz help someone...........
Here is my code

Code: Select all

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

char str[100],a[100];
int len;

void str_rev(){
	int i,x = 0;
	for(i=0; i<100; i++) { a[i] = 0;}
	for(i=len-1; i>=0; i--)
		a[x++] = str[i];
}

void strc(long long n){
	char su_b[100];
	int i=0,j,x=0;
	while(n >= 10){
		su_b[i++] = (n%10)+48;
		n = n/10;
	}
	su_b[i] = n+48;
	for(j=0; j<len; j++) str[j] = NULL;
	for(j=i; j>=0; j--)
		str[x++] = su_b[j];
	str[x] = 0;
	
}

int main()
{
	long long num1,num2,arr[100],sub = 0,l = 0,k,i;
	char nstr[100];
	while(gets(str) != NULL){
		if(!strcmp(str,"")) break;
		l = 0; sub = 0; k = 0;
		len = strlen(str);
		if(str[0] == '0'){
			for(i=0; i<len; i++){
				if(str[i] != '0')
					nstr[k++] = str[i];
			}
			nstr[k] = 0;
			len = k;
			strcpy(str, nstr);
		}
		printf("Original number was %s\n",str);
		while(1){
			sort(str,str+len);
			num1 = atol(str);
			str_rev();
			num2 = atol(a);
			sub = num2-num1;
			if(l>0){
				if(binary_search(arr,arr+l,sub)){
					printf("%lld - %lld = %lld\n",num2,num1,sub);
					printf("Chain length %lld\n",l+1);
					break;
				}
			}
			arr[l++] = sub;
			sort(arr,arr+l);
			printf("%lld - %lld = %lld\n",num2,num1,sub);
			strc(sub);
		}
		printf("\n"); 
	}
	return 0;
}

Plz give me some tricks plz!!!!!!!!!!!

[Bappi_cuet]

I can't figure out why output limit excessed. I try this a lot but still OLE.
Please help me.

Code: Select all

ACCEPTED

Thanks for Help.

[Sohel_Cuet]

Hi bappy i run your code on my machine and got some bugs.Some I/O do not match with my acc code.I am giving u those I/O

Input :

Code: Select all

1000
100
100000000
67779000

Output Of My Accepted Code :

Code: Select all

Original number was 1000
1000 - 1 = 999
999 - 999 = 0
0 - 0 = 0
Chain length 3

Original number was 100
100 - 1 = 99
99 - 99 = 0
0 - 0 = 0
Chain length 3

Original number was 100000000
100000000 - 1 = 99999999
99999999 - 99999999 = 0
0 - 0 = 0
Chain length 3

Original number was 67779000
97776000 - 67779 = 97708221
98772210 - 1227789 = 97544421
97544421 - 12444579 = 85099842
99885420 - 2458899 = 97426521
97654221 - 12245679 = 85408542
88554420 - 2445588 = 86108832
88863210 - 1236888 = 87626322
87663222 - 22236678 = 65426544
66554442 - 24445566 = 42108876
88764210 - 1246788 = 87517422
87754221 - 12245778 = 75508443
87554430 - 3445578 = 84108852
88854210 - 1245888 = 87608322
88763220 - 2236788 = 86526432
86654322 - 22345668 = 64308654
86654430 - 3445668 = 83208762
88763220 - 2236788 = 86526432
Chain length 17

Note That for the input 67779000 your code generates infinite number of output lines!!!!!!!! Fix it.Hope you will get Acc.Good Luck..

[Bappi_cuet]

Thanks for your sample input and output.
I got the error of my and fixed it and got AC
I remove my code!

[kbr_iut]

who says that the chain length of 59994 is 3,,,probably is wrong.coz my AC prgram gives 2.http://uvatoolkit.com also gives 2.
and I would like to remind u.

and repeat these steps unless the new number has already appeared in the chain

so i considered every number existing in the chain.thus initial number is one of the numbers in the chain.
if ur AC code gives 3 for 59994,ensure ,so that we can say that there is no such cases.
thanx everybody.

[rajib_sust]

may be 59994 is not in list becoz my AC also give output result 3
after modify i also get AC and result is 2

Rajib, sust