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

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

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

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

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

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

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

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

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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

10722 - Super Lucky Numbers

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

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

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
New poster
Posts: 2
Joined: Thu Sep 23, 2004 10:11 am

10722 Super Lucky Numbers - WA

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
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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

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

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

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

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

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

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]
@+!
DitriX

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

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
New poster
Posts: 6
Joined: Tue Nov 30, 2004 2:27 am

how to calculate the values( 10722 )

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 .
hey why doing this

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

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.

Post Reply

Return to “Volume 107 (10700-10799)”