fork(2) download
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <map>
  4. #include <tuple>
  5. #include <iomanip>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <cassert>
  9.  
  10.  
  11. using namespace std;
  12.  
  13. class Hypothesis {
  14. double weight;
  15. map<tuple<int, int>, double> memo;
  16.  
  17. public:
  18. Hypothesis(double weight) :
  19. weight(weight)
  20. {
  21.  
  22. }
  23.  
  24. double open_chance(int opened) {
  25. int closed = 36 - opened;
  26. double result = (double)closed / (weight * opened + closed);
  27. assert(0 <= result && result <= 1);
  28. return result;
  29. }
  30.  
  31. double likelihood(int total, int opened) {
  32. if (total == 0 && opened == 0) return 1;
  33. if (total == 0 || opened == 0) return 0;
  34.  
  35. auto hit = memo.find(make_tuple(total, opened));
  36. if (hit != memo.end()) return hit->second;
  37.  
  38. auto result =
  39. likelihood(total - 1, opened) * (1 - open_chance(opened)) +
  40. likelihood(total - 1, opened - 1) * open_chance(opened - 1);
  41.  
  42. memo[make_tuple(total, opened)] = result;
  43. assert(0 <= result && result <= 1);
  44. return result;
  45. }
  46.  
  47. double log_likelihood(int total, int opened) {
  48. return log(likelihood(total, opened));
  49. }
  50. };
  51.  
  52. int main()
  53. {
  54. struct input_type {
  55. int opened;
  56. int total;
  57. };
  58. input_type inputs[] = {
  59. input_type{ 25, 53 },
  60. input_type{ 28, 72 },
  61. input_type{ 25, 72 },
  62. input_type{ 29, 72 },
  63. input_type{ 27, 69 }
  64. };
  65.  
  66.  
  67. int N = 50;
  68.  
  69. for (int i = -N; i <= N; ++i) {
  70. double wight = pow(10, (double)i / N);
  71. Hypothesis hypothesis(wight);
  72. double sum = 0;
  73. for (auto input : inputs) {
  74. sum += hypothesis.log_likelihood(input.total, input.opened);
  75. }
  76.  
  77. int barlength = (int)round(20 + sum);
  78. if (barlength < 0) barlength = 0;
  79. if (barlength > 20) barlength = 20;
  80.  
  81. string bar = string(barlength, ' ') + string(20 - barlength, '*') + "|";
  82.  
  83. cout << setw(12) << wight << "\t" << setw(12) << sum << "\t# " << bar << endl;
  84. }
  85.  
  86. }
  87.  
  88.  
Success #stdin #stdout 0.03s 4416KB
stdin
Standard input is empty
stdout
         0.1	    -248.307	# ********************|
    0.104713	    -241.167	# ********************|
    0.109648	    -234.108	# ********************|
    0.114815	    -227.131	# ********************|
    0.120226	    -220.239	# ********************|
    0.125893	    -213.433	# ********************|
    0.131826	    -206.714	# ********************|
    0.138038	    -200.086	# ********************|
    0.144544	    -193.549	# ********************|
    0.151356	    -187.107	# ********************|
    0.158489	    -180.759	# ********************|
    0.165959	     -174.51	# ********************|
     0.17378	    -168.359	# ********************|
     0.18197	    -162.309	# ********************|
    0.190546	    -156.362	# ********************|
    0.199526	    -150.518	# ********************|
     0.20893	    -144.781	# ********************|
    0.218776	     -139.15	# ********************|
    0.229087	    -133.628	# ********************|
    0.239883	    -128.217	# ********************|
    0.251189	    -122.916	# ********************|
    0.263027	    -117.728	# ********************|
    0.275423	    -112.654	# ********************|
    0.288403	    -107.696	# ********************|
    0.301995	    -102.853	# ********************|
    0.316228	    -98.1271	# ********************|
    0.331131	    -93.5195	# ********************|
    0.346737	    -89.0309	# ********************|
    0.363078	    -84.6621	# ********************|
    0.380189	    -80.4138	# ********************|
    0.398107	    -76.2867	# ********************|
    0.416869	    -72.2815	# ********************|
    0.436516	    -68.3987	# ********************|
    0.457088	    -64.6388	# ********************|
     0.47863	    -61.0022	# ********************|
    0.501187	    -57.4894	# ********************|
    0.524807	    -54.1005	# ********************|
    0.549541	    -50.8359	# ********************|
     0.57544	    -47.6958	# ********************|
     0.60256	    -44.6803	# ********************|
    0.630957	    -41.7895	# ********************|
    0.660693	    -39.0234	# ********************|
    0.691831	     -36.382	# ********************|
    0.724436	    -33.8652	# ********************|
    0.758578	     -31.473	# ********************|
    0.794328	     -29.205	# ********************|
    0.831764	    -27.0612	# ********************|
    0.870964	    -25.0412	# ********************|
    0.912011	    -23.1448	# ********************|
    0.954993	    -21.3715	# ********************|
           1	    -19.7211	# ********************|
     1.04713	     -18.193	#   ******************|
     1.09648	    -16.7869	#    *****************|
     1.14815	    -15.5021	#     ****************|
     1.20226	    -14.3382	#       **************|
     1.25893	    -13.2945	#        *************|
     1.31826	    -12.3704	#         ************|
     1.38038	    -11.5654	#         ************|
     1.44544	    -10.8786	#          ***********|
     1.51356	    -10.3094	#           **********|
     1.58489	      -9.857	#           **********|
     1.65959	    -9.52063	#           **********|
      1.7378	    -9.29945	#            *********|
      1.8197	    -9.19264	#            *********|
     1.90546	    -9.19931	#            *********|
     1.99526	    -9.31856	#            *********|
      2.0893	    -9.54945	#           **********|
     2.18776	    -9.89103	#           **********|
     2.29087	    -10.3423	#           **********|
     2.39883	    -10.9023	#          ***********|
     2.51189	    -11.5699	#         ************|
     2.63027	    -12.3442	#         ************|
     2.75423	     -13.224	#        *************|
     2.88403	    -14.2082	#       **************|
     3.01995	    -15.2957	#      ***************|
     3.16228	    -16.4854	#     ****************|
     3.31131	    -17.7762	#   ******************|
     3.46737	    -19.1668	#  *******************|
     3.63078	     -20.656	# ********************|
     3.80189	    -22.2427	# ********************|
     3.98107	    -23.9256	# ********************|
     4.16869	    -25.7035	# ********************|
     4.36516	    -27.5752	# ********************|
     4.57088	    -29.5394	# ********************|
      4.7863	    -31.5948	# ********************|
     5.01187	    -33.7401	# ********************|
     5.24807	    -35.9742	# ********************|
     5.49541	    -38.2955	# ********************|
      5.7544	     -40.703	# ********************|
      6.0256	    -43.1952	# ********************|
     6.30957	    -45.7708	# ********************|
     6.60693	    -48.4286	# ********************|
     6.91831	    -51.1672	# ********************|
     7.24436	    -53.9853	# ********************|
     7.58578	    -56.8815	# ********************|
     7.94328	    -59.8546	# ********************|
     8.31764	    -62.9032	# ********************|
     8.70964	    -66.0261	# ********************|
     9.12011	    -69.2218	# ********************|
     9.54993	     -72.489	# ********************|
          10	    -75.8266	# ********************|