263

wjomlex · Post by **wjomlex** » Sat Dec 27, 2008 11:52 am

I'm getting TLE, but I've tried to optimize my code as much as is reasonable. The only meaningful improvement I can see is that when I search for previous numbers in the chain I could use a binary search, but then I'd have to sort the array, and that would take even longer than doing a linear search. Is this just yet another one of those problems that can't be done in time in Java? I don't see anybody that's managed this in Java on the forums.

Code: Select all

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String args[]) throws IOException
	{
		BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));

		while(true)
		{
			int n = Integer.parseInt(scan.readLine());

			if(n == 0)
				break;

			int[] p = new int[1005];
			int pn = 1;
			p[0] = n;

			System.out.println("Original number was " + n);

			while(true)
			{
				String str = n + "";

				int[] tmp = new int[str.length()];

				for(int i=0;i < tmp.length;i++)
					tmp[i] = str.charAt(i) - '0';

				Arrays.sort(tmp);

				int ia = 0;
				int ib = 0;

				for(int i=0;i < tmp.length;i++)
				{
					ia = (ia*10) + tmp[i];
					ib = ib + tmp[i] * (int)Math.pow(10,i);
				}

				n = ib - ia;
				System.out.println(ib + " - " + ia + " = " + n);

				boolean found = false;
				for(int i=0;i < pn;i++)
					if(p[i] == n)
						found = true;

				if(!found)
					p[pn++] = n;
				else
				{
					System.out.println("Chain length " + pn);
					System.out.println();
					break;
				}
			}
		}
	}
}

annhy · Post by **annhy** » Thu Mar 19, 2009 4:33 pm

You can try StringBuilder as a buffer rather than using a lot of System.out.println().
Then call the System.out.print() only once before your program exit.

It can highly improves your Java I/O.
Good luck!

cse08_konok · Post by **cse08_konok** » Sun Dec 13, 2009 1:36 pm

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50000

int compare (const void * a, const void * b)
{
  return ( *(char*)b - *(char*)a );
}
int mysearch(long long i,long long *judge, long long j)
{
long low=1,mid,high;
high=j-1;
mid=(low+high)/2;
while(low<=high){
	if(i<judge[mid])high=mid-1;
	else if(i>judge[mid])low=mid+1;
	else return 1;
	mid=(low+high)/2;
}
return 0;
}
 
 
 
int main ()
{
long long i,j,k,x,prnt=0;
int xa,ya,za;
char tempa;
char number[30000];
long long judge[50000];
while(gets(number)){
	if(!number[0])break;
	printf("Original number was %s\n",number);
	 for(j=1;j<=MAX;j++){
		x=strlen(number);
		qsort(number,x,sizeof(char),compare);
		sscanf(number,"%lld",&i);
		za=strlen(number);
		xa=za-1;
		for(ya=0,xa;ya<(za/2);ya++,xa--){
			tempa=number[ya];
			number[ya]=number[xa];
			number[xa]=tempa;
		}
		sscanf(number,"%lld",&k);
		printf("%lld - %lld = ",i,k);
		i-=k;
		sprintf(number,"%lld",i);
		printf("%lld\n",i);
                 if(mysearch(i,judge,j))break;
		xa=(int)j;
		while((xa>1)&&(judge[xa-1]>i)){
			judge[xa]=judge[xa-1];
			xa--;
		}
		judge[xa]=i;
	}
	printf("Chain length %lld\n\n",j);
}
return 0;
}

every time i'm getting wrong answer. plz anyone help......

jfvs · Post by **jfvs** » Thu Mar 31, 2011 8:50 pm

Im getting WA in this C++ code, I got the java version of this accepted... so I dont know whats happening here...

Code: Select all

#include <cstdio>
#include <algorithm>
#include <map>
#include <string.h>
#include <cstdlib>

using namespace std;
void ltos(long n, char *c){
	long copy = n;
	int size = strlen(c), i = size - 1, nsize = 0;
	for(; copy != 0; i--){
		c[i] = (copy % 10) + '0';
		copy /= 10;
		nsize++;
	}
	i = 0;
	for(int j = size - nsize; j < size; i++, j++) c[i] = c[j];
	c[i] = '\0';
}

int main(){
	char numb[11], cnumb[11];
	map<char*, char*> resps;
	while(scanf("%s", &numb) != EOF && strcmp(numb, "0") != 0){
		strcpy(cnumb, numb);
		if(resps.find(numb) == resps.end()){
			char resp[10000];
			sprintf(resp, "Original number was %s\n", numb);
			bool go = true;
			map<long, int> mp;
			mp[atol(numb)] = 1;
			int cycle = 0;
			while(go){
				int size = strlen(numb);
				sort(numb, numb + size);
				long desc = atol(numb);
				char ascc[size];
				for(int i = size -1, j = 0; i >= 0; i--, j++) ascc[j] = numb[i];
				long asc = atol(ascc), rest = asc - desc;
				sprintf(resp, "%s%ld - %ld = %ld\n", resp, asc, desc, rest);
				if(mp.find(rest) == mp.end()){
					mp[rest] = 1;
				}else{
					go = false;
				}
				ltos(rest, numb);
				cycle++;
			}
			sprintf(resp, "%sChain length %d\n\n", resp, cycle);
			resps[cnumb] = resp;
		}
		printf(resps[cnumb]);
	}
	return 0;
}

thanks

coralblue · Post by **coralblue** » Sun Jan 27, 2013 11:22 am

@annhy thanks for the tip!

shuvokr · Post by **shuvokr** » Fri Mar 22, 2013 9:33 pm

Why i got RE , please anyone help

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

#define sf scanf
#define pf printf

void convert(int num);
int cou;

int main()
{
    char inum[11];
    int i, j, tmp, sk, len, bs, sb, carry, t, k, num, c, cc;
    memset(inum, 0, 11);
    while(gets(inum))
    {
        if(inum[0] == '0') return 0;
        sscanf(inum, "%d", &num);
        len = strlen(inum);
        cc = len / 2;
        c = len - 1;

        bool ck = true;
        for(i = 0; i < cc; i++)
        {
            if(inum[i] != inum[c--])
                ck = false;
        }

        if(ck)
        {
            pf("Original number was %d\n", num);
            pf("%d - %d = 0\n", num, num);
            puts("0 - 0 = 0");
            puts("Chain length 2");
        }
        else
        {
            sort(inum, inum + len);
            for(i = 0; i < len; i++)
                if(inum[i] != '0') break;
            sb = 0;
            carry = 0;
            k = (len - i) - 1;
            for(j = i; j < len; j++)
            {
                tmp = (inum[j] - 48);
                t = pow(10, k);
                if(t % 10 != 0 && t != 1) t++;
                k--;
                sb += tmp * t;
            }
            bs = 0;
            k = len - 1;
            if(inum[len - 1] == '0') bs = 0;
            else
            {
                for(i = len - 1; i >= 0; i--)
                {
                    tmp = (inum[i] - 48);
                    t = pow(10, k);
                    if(t % 10 != 0 && t != 1) t++;
                    k--;
                    bs += tmp * t;
                }
            }
            k = bs - sb;
            cou = 1;
            pf("Original number was %d\n%d - %d = %d\n", num, bs, sb, k);
            if(k == num)
            {
                puts("Chain length 1");
            }
            else
            {
                convert(k);
            }
        }
        puts("");
    }
}
void convert(int num)
{
    int i, j, k = num, tmp, len = log10(k) + 1, sb, bs, t;
    char ch[11];
    memset(ch, 0, 11);
    t = 0;
    for(i = 0; i < len; i++)
    {
        tmp = k % 10;
        ch[t++] = tmp + 48;
        k /= 10;
    }
    sort(ch, ch + len);
    for(i = 0; i < len; i++)
        if(ch[i] != '0') break;
    sb = 0;
    k = (len - i) - 1;
    for(j = i; j < len; j++)
    {
        tmp = (ch[j] - 48);
        t = pow(10, k);
        if(t % 10 != 0 && t != 1) t++;
        k--;
        sb += (tmp * t);
    }
    bs = 0;
    k = len - 1;
    if(ch[len - 1] == '0') bs = 0;
    else
    {
        for(i = len - 1; i >= 0; i--)
        {
            tmp = (ch[i] - 48);
            t = pow(10, k);
            if(t % 10 != 0 && t != 1) t++;
            k--;
            bs += (tmp * t);
        }
    }
    k = bs - sb;
    cou++;
    pf("%d - %d = %d\n", bs, sb, k);
    if(k == num)
    {
        pf("Chain length %d\n", cou);
        return;
    }
    else
    {
        convert(k);
    }
}

shuvokr · Post by **shuvokr** » Fri Mar 22, 2013 10:02 pm

Try rewriting your code without using floating point.

rukhsana · Post by **rukhsana** » Mon Jan 20, 2014 12:45 pm

I think there is something wrong with the judge for this problem then. I submitted a program that checked for palindromes of lengths 3 and 4 only, and it got Accepted. However, it does not pass your input :\

uDebug · Post by **uDebug** » Fri May 30, 2014 1:23 pm

Here's some input / output I found useful during testing / debugging.

Remember to print a newline after every test case - including the last one.

Input:

Code: Select all

AC Output:

Code: Select all

Original number was 92482438
98844322 - 22344889 = 76499433
99764433 - 33446799 = 66317634
76664331 - 13346667 = 63317664
76664331 - 13346667 = 63317664
Chain length 4

Original number was 57878377
88777753 - 35777788 = 52999965
99996552 - 25569999 = 74426553
76554432 - 23445567 = 53108865
88655310 - 1355688 = 87299622
99876222 - 22267899 = 77608323
87763320 - 2336778 = 85426542
86554422 - 22445568 = 64108854
88654410 - 1445688 = 87208722
88772220 - 2227788 = 86544432
86544432 - 23444568 = 63099864
99866430 - 3466899 = 96399531
99965331 - 13356999 = 86608332
88663320 - 2336688 = 86326632
86663322 - 22336668 = 64326654
66654432 - 23445666 = 43208766
87664320 - 2346678 = 85317642
87654321 - 12345678 = 75308643
87654330 - 3345678 = 84308652
88654320 - 2345688 = 86308632
88663320 - 2336688 = 86326632
Chain length 20

Original number was 34131232
43332211 - 11223334 = 32108877
88773210 - 1237788 = 87535422
87554322 - 22345578 = 65208744
87654420 - 2445678 = 85208742
88754220 - 2245788 = 86508432
88654320 - 2345688 = 86308632
88663320 - 2336688 = 86326632
86663322 - 22336668 = 64326654
66654432 - 23445666 = 43208766
87664320 - 2346678 = 85317642
87654321 - 12345678 = 75308643
87654330 - 3345678 = 84308652
88654320 - 2345688 = 86308632
Chain length 13

Original number was 3434453
5444333 - 3334445 = 2109888
9888210 - 128889 = 9759321
9975321 - 1235799 = 8739522
9875322 - 2235789 = 7639533
9765333 - 3335679 = 6429654
9665442 - 2445669 = 7219773
9777321 - 1237779 = 8539542
9855432 - 2345589 = 7509843
9875430 - 345789 = 9529641
9965421 - 1245699 = 8719722
9877221 - 1227789 = 8649432
9864432 - 2344689 = 7519743
9775431 - 1345779 = 8429652
9865422 - 2245689 = 7619733
9776331 - 1336779 = 8439552
9855432 - 2345589 = 7509843
Chain length 16

Original number was 9833
9833 - 3389 = 6444
6444 - 4446 = 1998
9981 - 1899 = 8082
8820 - 288 = 8532
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 6

Original number was 1
1 - 1 = 0
0 - 0 = 0
Chain length 2

Original number was 3589458
9885543 - 3455889 = 6429654
9665442 - 2445669 = 7219773
9777321 - 1237779 = 8539542
9855432 - 2345589 = 7509843
9875430 - 345789 = 9529641
9965421 - 1245699 = 8719722
9877221 - 1227789 = 8649432
9864432 - 2344689 = 7519743
9775431 - 1345779 = 8429652
9865422 - 2245689 = 7619733
9776331 - 1336779 = 8439552
9855432 - 2345589 = 7509843
Chain length 12

Shafayat · Post by **Shafayat** » Mon Jan 19, 2015 11:39 am

Code: Select all

#include <stdio.h>
#include<string.h>
#include<math.h>

int main ()
{
    long long int a,b,c,d,e,f[10],g,h,i,j=0,k[2000],l,n,o=0,p;
    char m[100];
    while(scanf("%s",m))
    {
        if(strcmp(m,"0")==0)
            break;
        a=0;
        n=0;
        if(o>0)
            printf("\n");
        p=0;
        while(a!=1)
        {
            for(c=0;c<10;c++)
                f[c]=0;
            d=0;
            e=1;
            b=strlen(m);
            for(c=b-1;c>=0;c--)
            {
                d=d+(m[c]-'0')*e;
                e=e*10;
                f[m[c]-'0']++;
            }
            if(p==0)
                printf("Original number was %lld\n",d);
            p++;
            if(n==0)
            	k[n]=d;
            g=0;
            e=1;
            i=0;
            j=1;
            for(c=0;c<10;c++)
            {
                if(f[c]>0)
                {
                    for(h=1;h<=f[c];h++)
                    {
                        g=g+c*e;
                        e=e*10;
                    }
                }
                if(f[9-c]>0)
                {
                    for(h=1;h<=f[9-c];h++)
                    {
                        i=i+(9-c)*j;
                        j=j*10;
                    }
                }
            }
            l=g-i;
            printf("%lld - %lld = %lld\n",g,i,l);
            for(c=0;c<=n;c++)
            {
                if(l==k[c])
                {
                    break;
                }
            }
            if(c<n+1)
            {
                a=1;
                printf("Chain length %lld\n",n+1);
                break;
            }
            n++;
            k[n]=l;
            d=log10(l);
            if(l<10)
                d=0;
            for(c=d;c>=0;c--)
            {
                m[c]=l%10+'0';
                l=l/10;
            }
            m[d+1]='\0';
        }
        p=0;
        o++;
    }
    return 0;
}

brianfry713 · Post by **brianfry713** » Mon Jan 19, 2015 9:44 pm

After each number chain and chain length, including the last one, there should be a blank line.

Shafayat · Post by **Shafayat** » Tue Jan 20, 2015 7:36 pm

Thanks a lot. Got accepted

sabuj_aiub14 · Post by **sabuj_aiub14** » Thu Jul 02, 2015 3:07 pm

why wa???
please help...
here is my code...

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[100],b[100];
int c[10000];
int cmpfunc2(const void *a,const void *b)
{
    return (*(int*)a-*(int *)b);
}
int cmpfunc(const void *a,const void *b)
{
    return (*(int*)b-*(int *)a);
}

int main()
{
    char str[100],str1[1000];

    int size1,i,s1,s2,s,flag,t,m,mod,n1,q,count1;
    while(scanf("%s",str)==1)
    {
        t=0;
        flag=0;
        count1=0;
        if(str[0]=='0')
            break;
        cout<<"Original number was "<<str<<endl;
    while(flag==0)
    {
        size1=strlen(str);
        for(i=0;i<size1;i++)
        {
            a[i]=str[i]-'0';
            b[i]=str[i]-'0';
        }
        qsort(a,size1,sizeof(int),cmpfunc);
        qsort(b,size1,sizeof(int),cmpfunc2);
        s1=0;
        s2=0;
        for(int j=0;j<size1;j++)
        {
            s1=s1*10+a[j];
            s2=s2*10+b[j];
        }
        s=s1-s2;

        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
        //cout<<s;
        c[t]=s;
        n1=0;
        q=s;
        while(s>0)
        {
            mod=s%10;
            s=s/10;

            str[n1]=mod+'0';
            n1++;

        }


        if(q==0)
        {
            flag=1;
            count1=count1+2;

             flag=1;
             s1=s2=s=0;
             break;


        }
        else
        {
            if(t>0)
            {
                m=t-1;
                while(m>=0)
                {
                    if(c[t]==c[m])
                    {

                        flag=1;
                        break;
                    }
                    m--;
                }
            }
        }
        count1++;
        t++;

    }
    if(q==0)
    {
        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
    }
    cout<<"Chain length "<<count1<<endl<<endl;

    }


return 0;
}

BaronRED · Post by **BaronRED** » Thu Jul 02, 2015 4:32 pm

Put your source code inside the "code" tags to keep the indentation, w/o it it's very difficult to read the code!

sabuj_aiub14 · Post by **sabuj_aiub14** » Thu Jul 02, 2015 5:11 pm

why wa pls help....

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[100],b[100];
long long c[10000];
int cmpfunc2(const void *a,const void *b)
{
    return (*(int*)a-*(int *)b);
}
int cmpfunc(const void *a,const void *b)
{
    return (*(int*)b-*(int *)a);
}

int main()
{
    char str[100],str1[1000];

    int size1,i,s1,s2,s,flag,t,m,mod,n1,q,count1;
    while(scanf("%s",str)==1)
    {
        t=0;
        flag=0;
        count1=0;
        if(str[0]=='0')
            break;
        cout<<"Original number was "<<str<<endl;
    while(flag==0)
    {
        size1=strlen(str);
        for(i=0;i<size1;i++)
        {
            a[i]=str[i]-'0';
            b[i]=str[i]-'0';
        }
        qsort(a,size1,sizeof(int),cmpfunc);
        qsort(b,size1,sizeof(int),cmpfunc2);
        s1=0;
        s2=0;
        for(int j=0;j<size1;j++)
        {
            s1=s1*10+a[j];
            s2=s2*10+b[j];
        }
        s=s1-s2;

        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
        //cout<<s;
        c[t]=s;
        n1=0;
        q=s;
        while(s>0)
        {
            mod=s%10;
            s=s/10;

            str[n1]=mod+'0';
            n1++;

        }


        if(q==0)
        {
            flag=1;
            count1=count1+2;

             flag=1;
             s1=s2=s=0;
             break;


        }
        else
        {
            if(t>0)
            {
                m=t-1;
                while(m>=0)
                {
                    if(c[t]==c[m])
                    {

                        flag=1;
                        break;
                    }
                    m--;
                }
            }
        }
        count1++;
        t++;

    }
    if(q==0)
    {
        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
    }
    cout<<"Chain length "<<count1<<endl<<endl;

    }


return 0;
}

OJ Board

263 - Number Chains

263 - TLE in Java

Re: 263 - TLE in Java

WA in 263... help please

Re: 263 - TLE in Java

Re: 263 - RE

Re: 263 - TLE in Java

Re: 263 - TLE in Java

Re: 263 - TLE in Java

Why WA in 263 - Number Chains?

Re: 263 - Number Chains

Re: 263 - Number Chains

Re: 263 - Number Chains

Re: 263 - Number Chains

Re: 263 - Number Chains