Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class ChipRace {
- int[] chips;
- double[] ans;
- boolean[] v;
- double p[][][];
- void solve(int player, int numCard, int total, double p){
- if(numCard==0 || player == v.length) return;
- solve(player+1, numCard, total, p);
- if(!v[player]){
- v[player]=true;
- ans[player] += p*chips[player]/total;
- solve(0, numCard-1, total-chips[player], p*chips[player]/total);
- v[player]=false;
- }
- }
- public double[] chances(int[] chips) {
- int n = chips.length;
- double[] ret = new double[n];
- int total = 0;
- for(int i=0; i<n; i++) total += chips[i];
- int m = total/5;
- if(total%5 >= 3) m++;
- if(m==0) return ret;
- p = new double[m][n][total+1];
- for(int i=0; i<n; i++) p[0][i][total] = chips[i]*1.0/total;
- for(int k=1; k<m; k++){
- for(int i=0; i<n; i++){
- if(chips[i]==0) continue;
- for(int j=0; j<n; j++){
- if(i==j) continue;
- for(int t=chips[j]+chips[i]; t<=total; t++){
- p[k][i][t-chips[j]] += p[k-1][j][t] * chips[i]*1.0/(t-chips[j]);
- }
- }
- }
- }
- for(int i=0; i<m; i++) for(int j=0; j<n; j++) for(int k=0; k<=total; k++) ret[j] += p[i][j][k];
- return ret;
- // this.chips = chips;
- // ans = new double[n];
- // v = new boolean[n];
- // solve(0, m, total, 1);
- // return ans;
- }
- public static void main(String[] args) {
- ChipRace c = new ChipRace();
- // int[] input = new int[]{0, 1, 2, 3, 4};
- int[] input = new int[]{4, 4, 4, 4, 4, 4, 4, 4, 4, 3};
- // int[] input = new int[]{3, 4, 4, 4, 4, 4, 4, 4, 4, 4};
- // int[] input = new int[]{2, 0, 1, 4, 3, 2, 3, 4, 1, 2};
- // int[] input = new int[]{4, 4, 4, 4, 4};
- double[] ret = c.chances(input);
- for(int i=0; i<ret.length; i++) System.out.print(ret[i] + ", ");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement