Submission #122647

---

Source Code Expand

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	Scanner sc = new Scanner(System.in);
	public void run() {
		int n = sc.nextInt();
		int k = sc.nextInt();
		calc(n, k);
			
	}
	public void calc(int n, int k){
		int[] rates = new int[n];
		for(int i = 0; i < n; i++){
			rates[i] = sc.nextInt(); 
		}


		double rate = 0;
		ArrayList<Double> now = new ArrayList<Double>();
		ArrayList<Integer> frag = new ArrayList<Integer>();
		ArrayList<Integer> count = new ArrayList<Integer>();
		now.add(0.0);
		frag.add(0);
		count.add(0);
		double ans = 0;

		while(now.size() != 0){
			double nowrate = now.get(0);
			int nowfrag = frag.get(0);
			int nowcount = count.get(0);
			now.remove(0);
			frag.remove(0);
			count.remove(0);

			if(nowcount < k){
				//System.out.printf("%3s%n", Integer.toBinaryString(nowfrag));
				for(int i = 0; i < n; i++){
					int memo = nowfrag >> i;
					int a = memo % 2;
					if(a == 0){
						double nextrate = (nowrate + rates[i]) / 2;
						now.add(nextrate);
						int nextfrag = nowfrag + (1 << i);
						frag.add(nextfrag);
						count.add(nowcount + 1);
						if(ans < nextrate){
							ans = nextrate;
						}
					}
				}
			}
		}
		System.out.printf("%-8f", ans);
	}

	
	public static void main(String[] args) {
		new Main().run();
	}
}

Submission Info

Judge Result