10722 - Super Lucky Numbers

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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"

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
New poster
Posts: 2
Joined: Thu Sep 23, 2004 10:11 am

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

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
For a start you could try this:

Code: Select all

10 1
10 100
10 99
10 98
10 10
10 1
4 2
5 3
0 0
The result should be

Code: Select all

9
3290387238734012283765380421046311624106114607409883793453325921158295596577498551598639413302298001
332396611542806667727683812818956679832577554506129568754657173590197799809867766349120125903702001
33578876694054393511457707143255174219660937651411894093245814743682401521179111892561845734722009
8205571449
9
11
91
Good luck!

mohsen
New poster
Posts: 2
Joined: Thu Sep 23, 2004 10:11 am
Hello again
What is the maximum digits needed for output?
Thanks

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
well, an upperbound is 128^100, which has approx. 220 digits or so...

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
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;

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 = b;
l = 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]
@+!
DitriX

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
helo
i hope that this one is correct:

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

csn.

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

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.

thanks in advance .
hey why doing this

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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.