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=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??
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
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)
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)
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,
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"
-
- 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.
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.
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
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
-
- 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
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
For a start you could try this:
The result should be
Good luck!
Code: Select all
10 1
10 100
10 99
10 98
10 10
10 1
4 2
5 3
0 0
Code: Select all
9
3290387238734012283765380421046311624106114607409883793453325921158295596577498551598639413302298001
332396611542806667727683812818956679832577554506129568754657173590197799809867766349120125903702001
33578876694054393511457707143255174219660937651411894093245814743682401521179111892561845734722009
8205571449
9
11
91
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]
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
DitriX
-
- 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.
thanks in advance .
thanks in advance .
hey why doing this