Advertisement
Guest User

Untitled

a guest
May 3rd, 2015
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.92 KB | None | 0 0
  1. /**
  2. * Tittle: 10081 - Tight Words
  3. * Author: Cheng-Shih, Wong
  4. * Date: 2015/03/18
  5. */
  6.  
  7. // include files
  8. #include <iostream>
  9. #include <cstdio>
  10. #include <cstring>
  11.  
  12. using namespace std;
  13.  
  14. // definitions
  15. #define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
  16. #define clr(x,v) memset( x, v, sizeof(x) )
  17. #define cur(x) ((x)&1)
  18. #define pre(x) (((x)-1)&1)
  19.  
  20. // declarations
  21. double dp[2][10];
  22.  
  23. // functions
  24. int k, n;
  25. double ans;
  26.  
  27. // main function
  28. int main( void )
  29. {
  30. double d;
  31.  
  32. // input
  33. while( scanf( "%d%d", &k, &n )==2 ) {
  34. // solve
  35. clr( dp, 0 );
  36. d = k+1.0;
  37. FOR( i, 0, k ) dp[0][i] = 1/d;
  38.  
  39. FOR( i, 1, n-1 ) {
  40. clr( dp[cur(i)], 0 );
  41. FOR( j, 0, k ) {
  42. if( j > 0 ) dp[cur(i)][j] += dp[pre(i)][j-1];
  43. dp[cur(i)][j] += dp[pre(i)][j];
  44. if( j < k ) dp[cur(i)][j] += dp[pre(i)][j+1];
  45.  
  46. dp[cur(i)][j] *= 1/d;
  47. }
  48. }
  49.  
  50. ans = 0;
  51. FOR( i, 0, k ) ans += dp[cur(n-1)][i];
  52.  
  53. // output
  54. printf( "%.5lf\n", ans*100 );
  55. }
  56.  
  57. return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement