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 34 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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/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(n1,t1)+f(n1,t)+f(n1,t+1)
take advantage of the fact that f(n) needs only f(n1)
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(n1,t1)+f(n1,t)+f(n1,t+1)
take advantage of the fact that f(n) needs only f(n1)
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: 98
 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...