Page 3 of 4
263 - TLE in Java
Posted: Sat Dec 27, 2008 11:52 am
by wjomlex
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;
}
}
}
}
}
Re: 263 - TLE in Java
Posted: Thu Mar 19, 2009 4:33 pm
by annhy
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!
263
Posted: Sun Dec 13, 2009 1:36 pm
by cse08_konok
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......
WA in 263... help please
Posted: Thu Mar 31, 2011 8:50 pm
by jfvs
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
Re: 263 - TLE in Java
Posted: Sun Jan 27, 2013 11:22 am
by coralblue
@annhy thanks for the tip!
Re: 263 - RE
Posted: Fri Mar 22, 2013 9:33 pm
by shuvokr
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);
}
}
Re: 263 - TLE in Java
Posted: Fri Mar 22, 2013 10:02 pm
by shuvokr
Try rewriting your code without using floating point.
Re: 263 - TLE in Java
Posted: Mon Jan 20, 2014 12:45 pm
by rukhsana
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 :\
Re: 263 - TLE in Java
Posted: Fri May 30, 2014 1:23 pm
by uDebug
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
92482438
57878377
34131232
3434453
9833
1
3589458
0
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
Why WA in 263 - Number Chains?
Posted: Mon Jan 19, 2015 11:39 am
by Shafayat
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;
}
Re: 263 - Number Chains
Posted: Mon Jan 19, 2015 9:44 pm
by brianfry713
After each number chain and chain length, including the last one, there should be a blank line.
Re: 263 - Number Chains
Posted: Tue Jan 20, 2015 7:36 pm
by Shafayat
Thanks a lot. Got accepted
Re: 263 - Number Chains
Posted: Thu Jul 02, 2015 3:07 pm
by sabuj_aiub14
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;
}
Re: 263 - Number Chains
Posted: Thu Jul 02, 2015 4:32 pm
by BaronRED
Put your source code inside the "code" tags to keep the indentation, w/o it it's very difficult to read the code!
Re: 263 - Number Chains
Posted: Thu Jul 02, 2015 5:11 pm
by sabuj_aiub14
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;
}