## 11029 - Leading and Trailing

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
All I did was something like (within the pow function):

Code: Select all

``if(d > 1000000000) d /= 1000000000``
where d is a double.

And in the end print the first three digits (it's easy in Java, at least it's good for something).

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
Darko wrote:All I did was something like (within the pow function):

Code: Select all

``if(d > 1000000000) d /= 1000000000``
where d is a double.
I m getting TLE when using the fast exponentiation method for Leading part also If I will myself do hashing, then who will do coding !!!

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
I lied, this is what I did:

Code: Select all

``````while (n > Integer.MAX_VALUE)
n /= 1000000000;
``````
And - how do you get TLE if you do logk operations?

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
Darko wrote:I lied, this is what I did:

Code: Select all

``````while (n > Integer.MAX_VALUE)
n /= 1000000000;
``````
And - how do you get TLE if you do logk operations?
No I do fast exponentiation now and geting WA If I will myself do hashing, then who will do coding !!!

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### WA Help

I got WA
Can anyone give a case where it fails down #include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
double bigMod1(double b,double p)
{
if (p==0)return 1.0;
long pp=(long)p;
if (pp % 2 == 0)
{
double r=bigMod1(b,p/2);
double j=(r*r);
if(j> 1000000000) j /= 1000000000;
return j;
}
else
{
double j=(b*bigMod1(b,p-1));
if(j> 1000000000) j /= 1000000000;
return j;
}
}
long bigMod(long b,long p,long m)
{
if (p==0)return 1;
if (p % 2 == 0)
{
long r=bigMod(b,p/2,m);
return (r*r)%m;
}
else
{
return ((b%m)*bigMod(b,p-1,m))%m;
}
}
int main(){
int n,m,k;
cin>>n;
while(n--){
cin>>m>>k;
long ttt;
ttt=bigMod(m,k,1000);
double mm=m,kk=k;
double lll=bigMod1(mm,kk);
while(lll<100){
lll*=10;
}
char buf1;

sprintf(buf1, "%.0Lf", lll);
cout<<buf1<<buf1<<buf1;

cout<<"...";
if(ttt<10){
cout<<"00"<<ttt<<endl;
}
else if(ttt<100){
cout<<"0"<<ttt<<endl;
}
else{
cout<<ttt<<endl;
}
}
return 0;
}
If I will myself do hashing, then who will do coding !!!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### Re: some doubts

Cho wrote:
little joey wrote:I also calculated the first three digits using <math.h> and got accepted, but I still have some doubts about precision.
How can we be sure that a 100-million digit number that starts off "123999999999999999999999999..." is not printed as "124..." without doing bigint calculus?
I think the 4th to 15th digit can be considered as some sort of pseudo-random number, then the probability that all these digits being 9 is exponentially small.
Hmm, within the set of (2^32 - 1)*10^7 (approx. 4*10^16) possible input combinations, there will be an expected 40000 such cases, and an equal number of cases that get erroniously rounded down. I know of problems that test special cases with slimmer chances...

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
vinay pointed to me that my AC solution failed on cases with n = 10 and k = 100000 - it would give 999...000. Well, it was broken (at least in my and vinay's environment) for all k > 7 (I got either 10E...000 or 999...000).

I fixed it now, but the point is - I don't think they looked for nasty test cases. Or they omitted them on purpose - this problem ended up being the easiest problem in the set (judging by the number of AC during the contest).

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### I am getting T.L.E. !!!

Hi, I have submitted this problem several times but only managed to get T.L.E. I find the trailing digits by bigmod function and leading digits by fast exponentiation. Followings are the part of my code:

Code: Select all

``````FUNCTION USED TO FIND b^p mod m:
=========================
long long bigmod (long long b, long long p, long long m)
{
if (p == 0)
return 1;

else if (p % 2 == 0)
return (bigmod (b, p / 2, m) * bigmod (b, p / 2, m)) % m;

else
return ((b % m) * bigmod(b, p - 1, m)) % m;
}
``````
and

Code: Select all

``````FUNCTION USED TO FIND base^power:
==========================
long long square (long long n)
{
return n * n;
}

long long fastexp (long long base, int power)
{
long long r;
char digits;

if (power == 0)
return 1;

else if (power % 2 == 0)
{
r = (square (fastexp (base, power / 2)));

if (r > BIG)
{
sprintf(digits, "%lld", r);

digits = NULL;

r = atol(digits);
}

return r;
}

else
{
r = (base * ( fastexp (base, power - 1)));

if (r > BIG)
{
sprintf(digits, "%lld", r);

digits = NULL;

r = atol(digits);
}

return r;
}
}
BIG is defined as #define BIG	10000l
Everytime the resulting number gets bigger than BIG, I try to truncate the following digits[taking only the higher ones]. [IS THIS METHOD OKAY TO GET LEADING DIGITS ???]
``````
Any help is appreciated...

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
It worked for me, why don't you just make BIG a power of ten and then divide by it, instead of converting it back and forth?

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### It is not working...TLE again and again :(

BIG is actually power of 10 here, as you 've mentioned; 10^4 to be precise.10000l ... here. l is the suffix to denote long . Anyway, it is not working for me, I again got TLE after changing the code to divide by BIG.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Sorry, I should pay more attention - I used doubles for the base. And BIG 10^9.

But I am not sure why you are getting TLE. If you are dividing by BIG. If you are converting, what happens if you sprintf an 18-digit number into char? I really don't know.

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

### Re: I am getting T.L.E. !!!

nymo wrote:Hi, I have submitted this problem several times but only managed to get T.L.E. I find the trailing digits by bigmod function and leading digits by fast exponentiation. Followings are the part of my code:

Code: Select all

``````FUNCTION USED TO FIND b^p mod m:
=========================
long long bigmod (long long b, long long p, long long m)
{
if (p == 0)
return 1;

else if (p % 2 == 0)
return (bigmod (b, p / 2, m) * bigmod (b, p / 2, m)) % m;

else
return ((b % m) * bigmod(b, p - 1, m)) % m;
}
``````
if p is even you are computing bigmod b, p/2 twice instead of once in each debth of recursion. write something like
long long tmp = bigmod( b, p/2, m ) % m; tmp *= tmp; tmp %= m;
return tmp;

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11029 - Leading and Trailing

Hi!!!
I think there is a bug in this problem!
Here such input:
1
2 3

I think that answer should be : 008...008, but my accepted programm return 800...008
What do you think about it?

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 11029 - Leading and Trailing

The statement says n^k will contain at least 6 digits, so don't worry.
Life shouldn't be null.