10722 - Super Lucky Numbers

anupam · Post by **anupam** » Wed Sep 22, 2004 12:36 am

I have used the formula for each base and n
for n>2 : answer= (base-1)base^(n-1) - base^(n-2) - (n-2)(base-1)base(n-3)
for n=2: answer= base(base-1)-1
for n=1 answer=base (confused: (base-1) ?)
got TLE. Then I used DP to calculate the whole table for each base^n and then used the same formula. but this time got WA at 3.84
Is there any trick in the problem? (how to solve it within 2 s?)
Can anybody post some test cases here??

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Sep 22, 2004 1:36 am

I think your formula is wrong.
I haven't solved the problem so far, but I solved 10712, and I used it to calculate the answer for following test case:
10 4

answer should be:
8721

since there are 279 numbers in the range 1000 - 9999 that contain 13 as subsequence (calculated with my AC program for 10712).

your formula produces 8720 (and for bigger n it will be a bigger difference to correct value)

anupam · Post by **anupam** » Wed Sep 22, 2004 1:44 am

Please help to find what's wrong with my formula:

for n>2, there are n-1 ways to put 13.
there are total combination (base-1)*pow(base,n-1) as leading 0 is not allowed.
again if there are four digits (let
A B C D
we can put 13 in AB, BC, CD positions.
Incase of AB (Only case where 13 is in the first position). So we can have base^(n-2) combinations for the position C and D.
Then we can move it to BC and total number of combination is
(base-1)*base^(n-3) as leading zero is not allowed
There are n-2 positions like BC (13 is not in the leading position).
So, what's wrong eith the formula,
totalcase-leading 13 case-other 13 cases?
Help me please,

anupam · Post by **anupam** » Wed Sep 22, 2004 2:00 am

OOPs, I think I am counting things twice. Is it the case? Adrian, I think I missed the case 1313.

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Sep 22, 2004 2:23 am

You are counting some occurences of 13 more than once
if you say, AB contains 13, and CD are any digit, then CD can also have 13.
Later you calculate again this occurence of 13 at CD !!!

By the way, there is an easy dp recurrence with which you can fill the whole table in O(maxb * maxn * #digits of biggest number)
Hint: you only want to know if at previous position a 1 was used or not. If there was no 1, you can chose any digit at current position.

abishek · Post by **abishek** » Wed Sep 22, 2004 11:26 am

hi,
i got the problem AC. the judge thinks that 0 is not a valid 1-digit number is base b.
i think this is wrong.
bye
abi

little joey · Post by **little joey** » Wed Sep 22, 2004 11:59 am

I think you're right. It's stated that leading zeros are insignifficant, but it's arguable if the number 0 contains a leading zero. For this problem the answer is yes (there are only 9 one digit lucky numbers for base 10).

mohsen · Post by **mohsen** » Thu Sep 23, 2004 10:26 am

Hello

I think (and I hope) that I solved this problem
but when I submit my program , I get WA

Please give me some I/O to test my program

Thank you

Maniac · Post by **Maniac** » Thu Sep 23, 2004 1:25 pm

For a start you could try this:

Code: Select all

The result should be

Code: Select all

9
3290387238734012283765380421046311624106114607409883793453325921158295596577498551598639413302298001
332396611542806667727683812818956679832577554506129568754657173590197799809867766349120125903702001
33578876694054393511457707143255174219660937651411894093245814743682401521179111892561845734722009
8205571449
9
11
91

Good luck!

mohsen · Post by **mohsen** » Thu Sep 23, 2004 2:47 pm

Hello again
What is the maximum digits needed for output?
Thanks

Maniac · Post by **Maniac** » Thu Sep 23, 2004 4:09 pm

well, an upperbound is 128^100, which has approx. 220 digits or so...

ditrix · Post by **ditrix** » Thu Oct 07, 2004 11:07 pm

Are there any sticky inputs?
Because I am tired of Rintime Errors...
I tried all possible inputs (b,n) on my machine : no errors
(4<=b<=128 && 0<=n<=100)

[cpp]
int main(void) {
int b, n;

big_int l[200];

while (1) {
cin >> b >> n;
if (!b && !n) break;
if (n<=0) {
cout << "0" << endl;
continue;
}
if (n==1) {
cout << b-1 << endl;
continue;
}

big_int B = b;
l[1] = b;
l[2] = b*b-1;

for (int i=3; i<=n; i++) l = l[i-1]*B - l[i-2];

cout << l[n] - l[n-1] << endl;

}

}[/cpp]

tat tvam asi · Post by **tat tvam asi** » Fri Oct 08, 2004 5:09 pm

helo
i hope that this one is correct:

http://morse.inf.unideb.hu/~noszaly/xxx ... _10722.tgz

csn.

kathmolla · Post by **kathmolla** » Mon Dec 13, 2004 2:45 pm

I think , I got the right recursive equation. But I dont know how to calculate it . It needs the big int calculation and how can I do this in less time . Please help me if you can.

thanks in advance .

shamim · Post by **shamim** » Mon Dec 13, 2004 3:25 pm

If you have the right recursive equation, why don't you precalculate and store the results in an array, and then output each query in constant time.

OJ Board