701

emotional blind · Post by **emotional blind** » Sat Mar 05, 2005 1:32 pm

> > = [0, 2, 3, 9, 2, 2, ... ] in continuous

..../\....
....||....
how it comes

WHO WILL HELP ME?

eyhk · Post by **eyhk** » Tue Mar 22, 2005 7:25 am

For sedafcho's input, I got a different output, the last two.
I'm not able to find 2^31 though.

SiburNY · Post by **SiburNY** » Mon Apr 11, 2005 10:04 pm

2 Sedefcho

I got the same results. How long does it take to get them ? On my AMD 2200 it took like 10 minutes or more.

2 All

What is the maximum E ? I used LOG method. It's fairly fast, but this ludge gives just 10 sec for execution. So if there is number that definately does not have answer, it'll take my script a lot of time till it figures that out

Any ideas ?

Sedefcho · Post by **Sedefcho** » Mon Apr 11, 2005 10:29 pm

Hi SiburNY,

I have a machine with 512 MB RAM and
with a 1.6 GHz processor. My program is in C++.

For the input/output I have given above my C++ terminates
for about 3 mins.
So my algorithm is not efficient ( for the limits of
this problem as stated in the problem statement ).

But the Online Judge says my program terminates
( for Judge's input ) in 0.2 secs. So the Judge's input is not
so "hard" as mine ( see above ).

Apparently your algorithm could be made even more efficient.

I don't remember any details about the algorithm I've used.
I just ran my program once again.

Let me know if you need some hints. I can check my code
to see what algorithm I use.

But for sure the Judge's Input is not hard which means it contains
no numbers like 100 000 000 let's say.

One more thing - I am pretty sure
there's no limit for E.

SiburNY · Post by **SiburNY** » Mon Apr 11, 2005 10:44 pm

I doubt that input is not hard. When you have chance, can you creat not hard input set and feed it to your script so then I can compare to my output. Thanks a lot.

Just thought: for previous input I have the same output. So my program works right. And because Judge gives TLE to me, that means it has at least one "no power of 2" case.

Sedefcho · Post by **Sedefcho** » Tue Apr 12, 2005 12:55 am

How fast is your computer ( memory/processor ) ?
If we could say it is as fast as mine
than your algorithm is about 3 times slower.
But still this does not explain the TLE you get.
You should get into these 10 secs which the
Judge gives us even if your algorithm is 3 times slower.

You can easily create some "not hard" test cases.
Simply use values which are below 100 000 or below
1000 000 let's say ( second could be better ).

Make a lot ( 20-30 ) such cases and then we will compare them with
my output for the same values. Just post your I/O here.

If then the two outputs are the same there's a great chance
then that there exists some special case in which your program
goes into an endless loop ( or least in a loop which takes too much
to complete ) . This could explain the TLE. Of course I am
just guessing ( logically guessing, at least trying to ... ) .

Are you using C/C++ or Java ?
That also shouldn't make any great difference but ...
Still, who knows.

That is my opinion.

SiburNY · Post by **SiburNY** » Tue Apr 12, 2005 1:37 am

Thanks for trying to help me. I use C. I have Athlon XP 2200 768Mb computer. This time I tweaked my code a little. It took 11-12 seconds to finish the following numbers:

Input:

Code: Select all

Output:

Code: Select all

Thank you.

Sedefcho · Post by **Sedefcho** » Tue Apr 12, 2005 10:47 am

Hi again SiburNY,

for your input I get the following output

Code: Select all

Seems the same , right ?

With my program it takes about 1 sec to get this
output on a machine with 2GB RAM and
with a 2.66 GHz processor.

I will test it on the other machine too ( the one having
512 MB RAM and a 1.6 GHz processor ). And I will tell you
how much time my program needs to
complete on that machine for the input from your last post.

Why don't you e-mail me your code ? Or just send it to
me via a private message.

SiburNY · Post by **SiburNY** » Wed Apr 13, 2005 7:31 am

Yes, it's the same

. So my program works fine. I guess Judge has now more hard test input.

I just sent you my source code. Thank you.

Abednego · Post by **Abednego** » Tue May 03, 2005 7:55 pm

I don't believe Ivan Golubev's method works. This is the fastest way I can think of implementing it, and it times out. Is there some tweak that can make it faster?

Code: Select all

works now.

Thanks.

Abednego · Post by **Abednego** » Tue May 03, 2005 8:02 pm

Ok. Nevermind. I switched _everything_ to long double, and it got accepted in 0.123 seconds. Strange problem....

Alec · Post by **Alec** » Sun Aug 07, 2005 7:43 am

eyhk wrote:For sedafcho's input, I got a different output, the last two.
I'm not able to find 2^31 though.
Code: Select all
7
8
15
12
20
31
28748
24559
4813
325147
325148
11036
37937
6432163
146964308
146964307

I had calculated the 2^146964308 with big number.
the first 20 digits is 99999999281501361389...

Alec · Post by **Alec** » Sun Aug 07, 2005 7:58 am

My computer is P-M 1.6G with 512MB. it is about 2sec to finished
but my code got WA or TL on the judge......
my output

Code: Select all

7
8
15
12
9
143
629
314
1600
1597
224296
26399
123446
254370
194220
94220
2250226
225093
5766432
63293
78171
70777
325148
3606692
325149
325146

real    0m1.819s
user    0m1.650s
sys     0m0.038s

SiburNY wrote:Thanks for trying to help me. I use C. I have Athlon XP 2200 768Mb computer. This time I tweaked my code a little. It took 11-12 seconds to finish the following numbers:

Input:
Code: Select all
1
2
3
4
5
111
222
333
444
555
66666
77777
88888
99999
111111
111222
333444
555666
999900
123456
654321
100000
200000
300000
400000
500000
Output:
Code: Select all
7
8
15
12
9
143
629
314
1600
1597
224296
26399
123446
254370
194220
94220
2250226
225093
5766432
63293
78171
70777
325148
3606692
325149
325146
Thank you.

Moussa · Post by **Moussa** » Tue Aug 30, 2005 7:01 pm

it took me much time in problem 701 but give me run time error
and also i want to know an effecient way to solve this problem cuz i think my way will lead to Time limit exceed
i appreciate the effort of the one who is gonna help

Code: Select all

#include<iostream>
#include<string>
#include<stdio.h>
#include<cmath>
using namespace std;
string mult(string,int);
bool check(string,char*);
int main()
{
	float x,k;
	int div=1;
	string str = "1";
	int n=1;
	char ch[10];
	while(cin>>x)
	{
		div = 1;
		str = "1";
		n=1;
		sprintf(ch,"%d",(int)x);
		while(!check(str,ch))
		{
			
			k = log10(x)/log10((double)2) + (strlen(ch)+n)*1/log10((double)2);
			for(int i=div;i<=ceil(k);i++)
			{
				str=mult(str,2);
			}
			div = ceil(k)+1;
			n++;
			
		}
		cout<<div-1<<endl;

	}
return 0;

}
string mult(string s,int n)
{
	int carry=0;
	int k;
	string result = "";
	for(int i=s.length()-1;i>=0;i--)
	{
		k=(s[i]-'0')*n;
		result.insert(0,(char)((k%10)+48+carry));
		if(k>=10)
		{
			carry = k/10;
		}
		else
			carry = 0;
	}
	if(carry!=0)
	{
		result.insert(0,(char)(carry+48));
	}
	return result;
}
bool check(string s1,char* s2)
{
	int n;
	n = s1.length();
	if(s1.length()%2!=0)
		n++;
	if(n/2<=strlen(s2))
		return false;
	for(int i=0;i<strlen(s2);i++)
	{
		if(s1[i] != s2[i])
			return false;
	}
	return true;
}

lantimilan · Post by **lantimilan** » Tue Sep 20, 2005 9:46 am

Since there a a number of peope get less than 0.010s to finish, there must be some better algorithm than bruth force on search exponent by
2n+1, 2n+2, ...

Will anyone please give a hint?

thanks

OJ Board

701 - The Archeologists' Dilemma

Your answer of the last two is wrong

p701, solved but run in 2.531s