fork download
copy 
  1. import java.util.Arrays;
  2. import java.util.HashSet;
  3. import java.util.LinkedList;
  4. import java.util.Set;
  5. import java.util.StringTokenizer;
  6.  
  7. /*public*/class BalloonsTest {
  8.  
  9.     //    @Test
  10.     public void test_ordered_5_5() {
  11.         int[] cs = toIntArray( "1 2 3 4 5 1 2 3 4 5" );
  12.         int[] ps = toIntArray( "1 2 3 4 5 6 7 8 9 10" );
  13.         double[] sum = new double[cs.length + 1];
  14.         double[] cnt = new double[cs.length + 1];
  15.         Arrays.fill( sum, 0 );
  16.         Arrays.fill( cnt, 0 );
  17.         for (int mask = 0; mask < 1 << cs.length; mask++) {
  18.             Set<Integer> set = new HashSet<>();
  19.             double tsum = 0;
  20.             for (int bit = 0; bit < cs.length; bit++) {
  21.                 if ( ( mask & ( 1 << bit ) ) > 0 ) {
  22.                     set.add( cs[bit] );
  23.                     tsum += ps[bit];
  24.                 }
  25.             }
  26.             ++cnt[set.size()];
  27.             sum[set.size()] += tsum;
  28.         }
  29.         double[] sums = new double[cs.length + 1];
  30.         double[] cnts = new double[cs.length + 1];
  31.         Arrays.fill( sums, 0 );
  32.         Arrays.fill( cnts, 0 );
  33.         for (int i = 0; i < sums.length; i++) {
  34.             for (int j = i; j < cnts.length; j++) {
  35.                 sums[i] += sum[j];
  36.                 cnts[i] += cnt[j];
  37.             }
  38.         }
  39.         for (int i = 0; i <= 5; i++) {
  40.             //            double act = Balloons.solve( cs.length, i, cs, ps );
  41.             double exp = sums[i] / cnts[i];
  42.             System.out.printf( "M=%d => %f\n", i, exp );
  43.             //            Assert.assertEquals( "i=" + i, exp, act, 1e-6 );
  44.         }
  45.     }
  46.  
  47.     //    @Test
  48.     public void test_ordered_6_123() {
  49.         int[] cs = toIntArray( "1 2 2 3 3 3" );
  50.         int[] ps = toIntArray( "2 3 4 5 6 7" );
  51.         double[] sum = new double[cs.length + 1];
  52.         double[] cnt = new double[cs.length + 1];
  53.         Arrays.fill( sum, 0 );
  54.         Arrays.fill( cnt, 0 );
  55.         for (int mask = 0; mask < 1 << cs.length; mask++) {
  56.             Set<Integer> set = new HashSet<>();
  57.             double tsum = 0;
  58.             for (int bit = 0; bit < cs.length; bit++) {
  59.                 if ( ( mask & ( 1 << bit ) ) > 0 ) {
  60.                     set.add( cs[bit] );
  61.                     tsum += ps[bit];
  62.                 }
  63.             }
  64.             ++cnt[set.size()];
  65.             sum[set.size()] += tsum;
  66.         }
  67.         double[] sums = new double[cs.length + 1];
  68.         double[] cnts = new double[cs.length + 1];
  69.         Arrays.fill( sums, 0 );
  70.         Arrays.fill( cnts, 0 );
  71.         for (int i = 0; i < sums.length; i++) {
  72.             for (int j = i; j < cnts.length; j++) {
  73.                 sums[i] += sum[j];
  74.                 cnts[i] += cnt[j];
  75.             }
  76.         }
  77.         for (int i = 0; i <= 3; i++) {
  78.             //            double act = Balloons.solve( cs.length, i, cs, ps );
  79.             double exp = sums[i] / cnts[i];
  80.             System.out.printf( "M=%d => %f\n", i, exp );
  81.             //            Assert.assertEquals( "i=" + i, exp, act, 1e-6 );
  82.         }
  83.     }
  84.  
  85.     //    @Test
  86.     public void test_ordered_3() {
  87.         int[] cs = toIntArray( "1 2 3" );
  88.         int[] ps = toIntArray( "1 2 3" );
  89.         double[] sum = new double[cs.length + 1];
  90.         double[] cnt = new double[cs.length + 1];
  91.         Arrays.fill( sum, 0 );
  92.         Arrays.fill( cnt, 0 );
  93.         for (int mask = 0; mask < 1 << cs.length; mask++) {
  94.             int idx = Integer.bitCount( mask );
  95.             //            int tsum = 0;
  96.             for (int bit = 0; bit < cs.length; bit++) {
  97.                 if ( ( mask & ( 1 << bit ) ) > 0 ) {
  98.                     sum[idx] += ps[bit];
  99.                 }
  100.             }
  101.             ++cnt[idx];
  102.         }
  103.         double[] sums = new double[cs.length + 1];
  104.         double[] cnts = new double[cs.length + 1];
  105.         Arrays.fill( sums, 0 );
  106.         Arrays.fill( cnts, 0 );
  107.         for (int i = 0; i < sums.length; i++) {
  108.             for (int j = i; j < cnts.length; j++) {
  109.                 sums[i] += sum[j];
  110.                 cnts[i] += cnt[j];
  111.             }
  112.         }
  113.         for (int i = 0; i <= cs.length; i++) {
  114.             //            double act = Balloons.solve( cs.length, i, cs, ps );
  115.             double exp = sums[i] / cnts[i];
  116.             System.out.printf( "M=%d => %f\n", i, exp );
  117.             //            Assert.assertEquals( "i=" + i, exp, act, 1e-6 );
  118.         }
  119.     }
  120.  
  121.     //    @Test
  122.     public void test_ordered_10() {
  123.         int[] cs = toIntArray( "1 2 3 4 5 6 7 8 9 10" );
  124.         int[] ps = toIntArray( "1 2 3 4 5 6 7 8 9 10" );
  125.         double[] sum = new double[cs.length + 1];
  126.         double[] cnt = new double[cs.length + 1];
  127.         Arrays.fill( sum, 0 );
  128.         Arrays.fill( cnt, 0 );
  129.         for (int mask = 0; mask < 1 << cs.length; mask++) {
  130.             int idx = Integer.bitCount( mask );
  131.             //            int tsum = 0;
  132.             for (int bit = 0; bit < cs.length; bit++) {
  133.                 if ( ( mask & ( 1 << bit ) ) > 0 ) {
  134.                     sum[idx] += ps[bit];
  135.                 }
  136.             }
  137.             ++cnt[idx];
  138.         }
  139.         double[] sums = new double[cs.length + 1];
  140.         double[] cnts = new double[cs.length + 1];
  141.         Arrays.fill( sums, 0 );
  142.         Arrays.fill( cnts, 0 );
  143.         for (int i = 0; i < sums.length; i++) {
  144.             for (int j = i; j < cnts.length; j++) {
  145.                 sums[i] += sum[j];
  146.                 cnts[i] += cnt[j];
  147.             }
  148.         }
  149.         for (int i = 0; i <= cs.length; i++) {
  150.             //            double act = Balloons.solve( cs.length, i, cs, ps );
  151.             double exp = sums[i] / cnts[i];
  152.             System.out.printf( "M=%d => %f\n", i, exp );
  153.             //            Assert.assertEquals( "i=" + i, exp, act, 1e-6 );
  154.         }
  155.     }
  156.  
  157.     private int[] toIntArray( String s ) {
  158.         System.out.println( s );
  159.         StringTokenizer tok = new StringTokenizer( s );
  160.         LinkedList<Integer> list = new LinkedList<>();
  161.         while ( tok.hasMoreElements() ) {
  162.             list.add( Integer.parseInt( tok.nextToken() ) );
  163.         }
  164.  
  165.         int[] res = new int[list.size()];
  166.         int i = 0;
  167.         for (int item : list) {
  168.             res[i++] = item;
  169.         }
  170.         return res;
  171.     }
  172.  
  173.     public static void main( String[] args ) {
  174.         new BalloonsTest().test_ordered_3();
  175.         System.out.println( "~~~ ~~~ ~~~" );
  176.         new BalloonsTest().test_ordered_10();
  177.         System.out.println( "~~~ ~~~ ~~~" );
  178.         new BalloonsTest().test_ordered_5_5();
  179.         System.out.println( "~~~ ~~~ ~~~" );
  180.         new BalloonsTest().test_ordered_6_123();
  181.     }
  182.  
  183. }
  184.  
Success #stdin #stdout 0.1s 380352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3
1 2 3
M=0 => 3.000000
M=1 => 3.428571
M=2 => 4.500000
M=3 => 6.000000
~~~ ~~~ ~~~
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
M=0 => 27.500000
M=1 => 27.526882
M=2 => 27.744324
M=3 => 28.522727
M=4 => 30.224057
M=5 => 32.931034
M=6 => 36.476684
M=7 => 40.625000
M=8 => 45.178571
M=9 => 50.000000
M=10 => 55.000000
~~~ ~~~ ~~~
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 6 7 8 9 10
M=0 => 27.500000
M=1 => 27.526882
M=2 => 27.827381
M=3 => 29.117647
M=4 => 32.083333
M=5 => 36.666667
~~~ ~~~ ~~~
1 2 2 3 3 3
2 3 4 5 6 7
M=0 => 13.500000
M=1 => 13.714286
M=2 => 14.923077
M=3 => 16.952381
https://ideone.com/rPnqVX
language:
Java (12.0.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!