10081 - Tight Words
Moderator: Board moderators
10081 - Tight Words
I have written code for 10081, but the judge doesn't like it.
Any ideas?
Any ideas?
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
-
- Learning poster
- Posts: 82
- Joined: Thu Oct 10, 2002 1:15 pm
- Location: St. Johns, Canada
- Contact:
10081 - What the problem states and how can I solve it?
Would you pls tell me what the problem states and How can I solve it?
If you know then Pls tell me....
Thanks in advance
M H Rasel
Cuet Old Sailor
If you know then Pls tell me....
Thanks in advance
M H Rasel
Cuet Old Sailor
confusing
This problem is hard to understand if you read it only once, but if you read it 3-4 times then you will probably get the hang of it.
consider the second case in the sample:
2 5
here k is 2 and n is 5.
you can form 3^5 numbers.... ( allowed digits are 0,1,2 and of length 5).
Of these 3^5 numbers, the numbers whose adjacent digits do not differ by one are tight words (numbers).
Just output the percentage.
Hint: Use DP as manual genertions will exceed Mem limit && time limit.
Hope it helps.
consider the second case in the sample:
2 5
here k is 2 and n is 5.
you can form 3^5 numbers.... ( allowed digits are 0,1,2 and of length 5).
Of these 3^5 numbers, the numbers whose adjacent digits do not differ by one are tight words (numbers).
Just output the percentage.
Hint: Use DP as manual genertions will exceed Mem limit && time limit.
Hope it helps.
10081 (Tight Words) - Wrong Answer
I'm trying to solve 10081, Tight words, but I'm getting WA all the time.
Can anybody give me the number of tight words for input '9 100' ?
I know that this is not asked, but this is part of the solution.
My program says 1069966138. Is this correct?
Or maybe someone has some input/output for testing?
Thanks.
Can anybody give me the number of tight words for input '9 100' ?
I know that this is not asked, but this is part of the solution.
My program says 1069966138. Is this correct?
Or maybe someone has some input/output for testing?
Thanks.
Here are some tests.
Input
Output
Input
Code: Select all
0 8
5 10
2 20
2 30
2 40
2 50
2 60
2 70
9 13
Code: Select all
100.00000
0.09657
1.56615
0.17839
0.02032
0.00231
0.00026
0.00003
0.00012
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
10081 - Tight Words
How do u acheive precision for this problem ? I used double and got quite different results for the above case :
for 9 100 i get 0.00000 ..
Code: Select all
100.00000
0.09657
1.56615
0.17839
0.02032
0.00231
0.00026
0.00003
0.00003
if u can think of it .. u can do it in software.
Re: How to solve problem 10081?
I was trying to solve this problem but could not figure out how to use DP here. Here is what I observed: For a string of length i ending with digit j, then the second last digit will be j - 1, j or j + 1 if 1 <= j <= k - 2, 0 or 1 if j = 0, and k - 2 or k - 1 if j = k - 1. At first I thought of using memoization(using a lookup table), after trying to work out the recursion tree to calculate the number of tight words for a small example, say the first test data in the sample input: 2 5. The lookup table would become too big because there are too many places in the recursion tree where the same value is calculated more than once.
Can anyone give me a hint how to use DP for this problem? Thanks.
Can anyone give me a hint how to use DP for this problem? Thanks.
Re: How to solve problem 10081?
Got AC despite some lossy precision..
f(n,t) = f(n-1,t-1)+f(n-1,t)+f(n-1,t+1)
take advantage of the fact that f(n) needs only f(n-1)
formally that would look like :chunyi81 wrote: For a string of length i ending with digit j, then the second last digit will be j - 1, j or j + 1 if 1 <= j <= k - 2, 0 or 1 if j = 0, and k - 2 or k - 1 if j = k - 1.
f(n,t) = f(n-1,t-1)+f(n-1,t)+f(n-1,t+1)
take advantage of the fact that f(n) needs only f(n-1)
if u can think of it .. u can do it in software.
Re: 10081 - Tight Words
My program which got AC has the same resultjagadish wrote:How do u acheive precision for this problem ? I used double and got quite different results for the above case :for 9 100 i get 0.00000 ..Code: Select all
100.00000 0.09657 1.56615 0.17839 0.02032 0.00231 0.00026 0.00003 0.00003
Re: 10081 - Tight words
for k=9 and n=100
the number of tight words:
tights = 100512267936480837475180750161082113997249340218
And the number of possible words:
possibles = (k+1)^n = 10^100
Then
% = 100.0*(tights/possibles)
% = 0.00000
the number of tight words:
tights = 100512267936480837475180750161082113997249340218
And the number of possible words:
possibles = (k+1)^n = 10^100
Then
% = 100.0*(tights/possibles)
% = 0.00000
-
- Learning poster
- Posts: 99
- Joined: Fri Aug 17, 2012 9:23 pm
- Location: Dhaka
- Contact:
Re: 10081 - Tight words
Astonished to see, for computing 10^100 pow() can be used !!!! Would anybody please tell me, what is the actual range of returned value of pow() in C++ ??? It'll really help....
Thanks in advance...
Thanks in advance...