## 10722 - Super Lucky Numbers

Moderator: Board moderators

### 10722 - Super Lucky Numbers

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=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??
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

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

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)
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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,
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

OOPs, I think I am counting things twice. Is it the case? Adrian, I think I missed the case 1313.
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

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.
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 10722 - Super Lucky Numbers

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

abishek
Experienced poster

Posts: 131
Joined: Mon Dec 15, 2003 5:41 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).

little joey
Guru

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

### 10722 Super Lucky Numbers - WA

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
mohsen
New poster

Posts: 2
Joined: Thu Sep 23, 2004 10:11 am

For a start you could try this:

Code: Select all
`10 110 10010 9910 9810 1010 14 25 30 0`

The result should be

Code: Select all
`9329038723873401228376538042104631162410611460740988379345332592115829559657749855159863941330229800133239661154280666772768381281895667983257755450612956875465717359019779980986776634912012590370200133578876694054393511457707143255174219660937651411894093245814743682401521179111892561845734722009820557144991191`

Good luck!
Maniac
Experienced poster

Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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

Posts: 2
Joined: Thu Sep 23, 2004 10:11 am

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

Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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[i] = l[i-1]*B - l[i-2];

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

}

}[/cpp]
@+!
DitriX
ditrix
New poster

Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

helo
i hope that this one is correct:

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

csn.
tat tvam asi
New poster

Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

### how to calculate the values( 10722 )

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.

hey why doing this
kathmolla
New poster

Posts: 6
Joined: Tue Nov 30, 2004 2:27 am

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.

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

Next