Rezultati

Up. imeNalogaJezikRezultatČas oddaje
scnm1-2018 Zgoščenke Java 0/100Napaka med izvajanjem / ob izhodu (RTE) 04. okt '18 @ 19:50

Test Točke Porabljen spomin Porabljen čas Status
#1 0/11 158,063 MiB 2,806 s Prekoračen spomin
#2 0/11 159,945 MiB 3,106 s Prekoračen spomin
#3 0/11 159,367 MiB 3,145 s Prekoračen spomin
#4 0/11 159,434 MiB 3,103 s Prekoračen spomin
#5 0/11 157,336 MiB 3,052 s Prekoračen spomin
#6 0/11 159,988 MiB 3,070 s Prekoračen spomin
#7 0/11 68,363 MiB 0,185 s Napačen odgovor
#8 11/11 38,293 MiB 0,000 s OK
#9 12/12 36,777 MiB 0,000 s OK

Ocenjevani program (n1.java):
import java.util.*;
import java.io.*;


class edge {
	int next;
	double p;
	edge(int a, double b) {
		next = a;
		p = b;
	}
}

class graf {
	edge[][] E;
	long c(Integer[]q) {
		long l=0;
		for(int i:q) {
			l*=11;
			l+=i;
		}
		return l;
	}
	graf(int n, double[] p) {
		HashMap<Long, Integer> hm = new HashMap<Long, Integer>();
		ArrayList<Integer[]> per = generate(n);
		E = new edge[per.size()][n];
		for (Integer[] nn : per) {
			//System.out.println(Arrays.toString(nn));
		}
		for (int i = 0; i < per.size(); i++) {
			hm.put(c(per.get(i)), i);
		}
		for (int i = 0; i < per.size(); i++) {
			Integer[][] mods = new Integer[n][n];
			mods = f(per.get(i));
			for (int j = 0; j < n; j++) {
				//System.out.println(hm.containsKey(c(mods[j])));
				E[i][j] = new edge(hm.get(c(mods[j])), p[j]);
			}
		}
		for (edge[] q : E) {
			for (edge e : q) {
				//System.out.println(e.next + " " + e.p);
			}
			//System.out.println();
		}
		double[]p1=new double[per.size()];
		double[]p2=new double[per.size()];
		p1[0]=1;
		double sum=0;
		long len=0;
		for(int q=0;q<10000;q++) {
			Arrays.fill(p2, 0);
			for(int i=0;i<per.size();i++) {
				for(int j=0;j<n;j++) {
					p2[E[i][j].next]+=p1[i]*E[i][j].p;
				}
			}
			p1=p2.clone();
			len++;
			sum+=len*p1[0];
			//System.out.println(len*p1[0]);
			p1[0]=0;
		}
		System.out.println(sum);
	}

	Integer[][] f(Integer[] q) {
		Integer[][] ans = new Integer[q.length][q.length];
		for (int i = 0; i < q.length; i++) {
			Integer[] clone = q.clone();
			int pos = -1;
			for (int j = 0; j < q.length; j++) {
				if (q[j] == i) {
					pos = j;
					break;
				}
			}
			for (int j = pos; j >= 1; j--) {
				clone[j] = clone[j - 1];
			}
			clone[0] = i;
			ans[i] = clone;
		}
		return ans;
	}

	ArrayList<Integer[]> generate(int n) {
		boolean[] used = new boolean[n];
		Integer[] q = new Integer[n];
		int p = 0;
		ArrayList<Integer[]> ans = new ArrayList<Integer[]>();
		dfs(q, p, used, ans);
		return ans;
	}

	void dfs(Integer[] q, int p, boolean[] used, ArrayList<Integer[]> ans) {
		if (p == q.length) {
			ans.add(q.clone());
		} else {
			for (int i = 0; i < q.length; i++) {
				if (!used[i]) {
					q[p] = i;
					used[i] = true;
					dfs(q, p + 1, used, ans);
					used[i] = false;
				}
			}
		}
	}
}

public class n1 {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		double[] q = new double[n];
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i = 0; i < n; i++) {
			q[i] = Double.parseDouble(st.nextToken());
		}
		graf g = new graf(n, q);

	}
}