11190 - Series of Powers

[mf]

I m currently getting WA. Can anyone verify the I/O sets?

I get the same outputs, except that for the last test case (0 0 1), the exponent in the output should be 1 -- that's specifically mentioned in the problem statement.

[Jan]

Thanks mf. Got Accepted. Overlooked that part.

[jah]

I'm always getting TLE. Is there a better method than O(nlogk).

My code is the following (I will remove it after AC if I'm able to do that).
I have tried all the dirty tricks I could imagine without success:

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <cmath>

using namespace std;

typedef long double ld;
typedef long long ll;

class num {
public:
ld man;
ll exp;

num() {
exp = 0;
man = 0.0;
}
num(const num &cp) {
man = cp.man;
exp = cp.exp;
}
num(int n) {
man = (ld)n;
exp = 0.0;

norm();
}
inline void prod(const num &b) {
man *= b.man;
exp += b.exp;

//norm();
}
inline void norm()
{
if (man == 0.0) return;
register ld tmp = log10(man) + 1.0+1e-9;
//if (floor(tmp) == tmp)
tmp = floor(tmp);
//else tmp = ceil(tmp);
exp += (ll) tmp;
man /= pow(10,tmp);
}

inline void add(const num &b) {
ll diff = exp - b.exp;
if (diff == 0) {
man+=b.man;
//norm();
} else if (diff < 0) {
man /= pow((ld)10.0,(ld)-diff);
exp -= diff;

man += b.man;

//norm();
} else {
man *= pow((ld)10.0,(ld)diff);
exp -= diff;

man += b.man;

//norm();
}
norm();
}
void print() {
norm();
printf("%.6llfe%.10lld\n", man, exp);
}
};

num elv(num &v, int k)
{
if (k <= 0) return num(0);
if (k == 1) return v;

num res = elv(v,k>>1);
//if (k == 1000) res.norm();

res.prod(res);
if (k&1) res.prod(v);

if (k>=2500)
res.norm();

return res;
}

inline ll a(ll v)
{
if (v< 0.0) return -v;
return v;
}

int main()
{
int l,h,k;
int tst = 1;

while (scanf("%d %d %d", &l,&h,&k) != EOF) {
if (l < 0 || h < 0 || k < 0) break;
//cout << k << endl;
num res(0);
num par(0);
if (!l) l++;
bool f = true;
//res.print();
for (register int i=h; i>=l; i--) {
par.man = (ld)i;
par.exp = 0.0;
par.norm();
//par.elv(k);
par = elv(par,k);
par.norm();
/* remove if precision is needed */
if (f) f = false;
else if (res.exp-par.exp > 4) break;
/**/
res.add(par);
}
res.norm();
if (res.man == 0.0) res.exp = 1;
printf("Case %04d: ", tst++);
res.print();
}



return 0;
}

[Piklu_sust]

It should be accepted within time limit with complexity O(n lg k) if the n = |h - l| that you mean.
BCOZ there are almost 1500 test cases and the worst case for each case : 1000*24.
Hence, it always pass the time limit successfully.

The complexity of my solution is O(n) where n = |h - l| which always less the or equal to 1000.
And use the function pow, log10 from math.h.