CSES - Datatähti 2015 loppu

CSES - Datatähti 2015 loppu - Results

Submission details
Task:	Pörssihai
Sender:	Kuha
Submission time:	2015-01-29 14:44:07 +0200
Language:	Java
Status:	READY
Result:	12

Feedback
group	verdict	score
#1	ACCEPTED	12
#2	RUNTIME ERROR	0
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.04 s	1	details
#2	ACCEPTED	0.06 s	1	details
#3	ACCEPTED	0.05 s	1	details
#4	RUNTIME ERROR	0.51 s	2	details
#5	RUNTIME ERROR	0.24 s	2	details
#6	RUNTIME ERROR	0.25 s	2	details
#7	RUNTIME ERROR	0.15 s	3	details
#8	RUNTIME ERROR	0.16 s	3	details
#9	RUNTIME ERROR	0.16 s	3	details
#10	RUNTIME ERROR	0.52 s	3	details
#11	RUNTIME ERROR	0.14 s	3	details
#12	RUNTIME ERROR	0.17 s	3	details
#13	RUNTIME ERROR	0.15 s	3	details
#14	RUNTIME ERROR	0.17 s	3	details
#15	RUNTIME ERROR	0.16 s	3	details
#16	RUNTIME ERROR	0.14 s	3	details
#17	RUNTIME ERROR	0.17 s	3	details
#18	RUNTIME ERROR	0.16 s	3	details
#19	RUNTIME ERROR	0.15 s	3	details
#20	RUNTIME ERROR	0.17 s	3	details

Code

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    
    public static void main(String[] args) {
        IO io = new IO();
        
        int days = io.nextInt();
        
        int[] sums;
        sums = new int[permutations(days)];
        
        int[] ds;
        ds = new int[permutations(days)];
        
        int day = 1;
        
        while (day <= days) {
            int d = io.nextInt();
            
            double h = 0.0;
            int c = 1;
            
            int dPerm = permutations(day - 1);
            //io.println("========");
            for (int i = 0; i < day; i++) {
                
                int t = sums[dPerm - i] + d;
                sums[dPerm + i] = t;
                ds[dPerm + i] = ds[dPerm - i] + 1;
                //io.println("d:"+day+" i:" + i+" t:" + t);
                if (h <= (double)t / (double)(ds[dPerm + i])) {
                    h = (double)t / (double)(ds[dPerm + i]);
                    //io.println("h:" + h);
                    c = ds[dPerm + i];
                }
                //io.println("DAY: " + (ds[dPerm + i]));
                //io.println("VALUE: " + ((double)t / (double)(i + 1)));
            }
            io.print(c + " ");
            day++;
        }
        
        io.close();
    }
    
    private static int permutations (int n) {
        int a = 0;
        for (int i = 1; i <= n; i++) {
            a += i;
        }
        return a;
    }
}

class IO extends PrintWriter {
	private InputStreamReader r;
	private static final int BUFSIZE = 1 << 15;
	private char[] buf;
	private int bufc;
	private int bufi;
	private StringBuilder sb;
	
	public IO() {
		super(new BufferedOutputStream(System.out));
		r = new InputStreamReader(System.in);
		
		buf = new char[BUFSIZE];
		bufc = 0;
		bufi = 0;
		sb = new StringBuilder();
	}
	
	private void fillBuf() throws IOException {
		bufi = 0;
		bufc = 0;
		while(bufc == 0) {
			bufc = r.read(buf, 0, BUFSIZE);
			if(bufc == -1) {
				bufc = 0;
				return;
			}
		}
	}
	
	private boolean pumpBuf() throws IOException {
		if(bufi == bufc) {
			fillBuf();
		}
		return bufc != 0;
	}
	
	private boolean isDelimiter(char c) {
		return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f';
	}
	
	private void eatDelimiters() throws IOException {
		while(true) {
			if(bufi == bufc) {
				fillBuf();
				if(bufc == 0) throw new RuntimeException("IO: Out of input.");
			}
			
			if(!isDelimiter(buf[bufi])) break;
			++bufi;
		}
	}
	
	public String next() {
		try {
			sb.setLength(0);
			
			eatDelimiters();
			int start = bufi;
			
			while(true) {
				if(bufi == bufc) {
					sb.append(buf, start, bufi - start);
					fillBuf();
					start = 0;
					if(bufc == 0) break;
				}
				
				if(isDelimiter(buf[bufi])) break;
				++bufi;
			}
			
			sb.append(buf, start, bufi - start);
			
			return sb.toString();
		} catch(IOException e) {
			throw new RuntimeException("IO.next: Caught IOException.");
		}
	}
	
	public int nextInt() {
		try {
			int ret = 0;
			
			eatDelimiters();
			
			boolean positive = true;
			if(buf[bufi] == '-') {
				++bufi;
				if(!pumpBuf()) throw new RuntimeException("IO.nextInt: Invalid int.");
				positive = false;
			}
			
			boolean first = true;
			while(true) {
				if(!pumpBuf()) break;
				if(isDelimiter(buf[bufi])) {
					if(first) throw new RuntimeException("IO.nextInt: Invalid int.");
					break;
				}
				first = false;
				
				if(buf[bufi] >= '0' && buf[bufi] <= '9') {
					if(ret < -214748364) throw new RuntimeException("IO.nextInt: Invalid int.");
					ret *= 10;
					ret -= (int)(buf[bufi] - '0');
					if(ret > 0) throw new RuntimeException("IO.nextInt: Invalid int.");
				} else {
					throw new RuntimeException("IO.nextInt: Invalid int.");
				}
				
				++bufi;
			}
			
			if(positive) {
				if(ret == -2147483648) throw new RuntimeException("IO.nextInt: Invalid int.");
				ret = -ret;
			}
			
			return ret;
		} catch(IOException e) {
			throw new RuntimeException("IO.nextInt: Caught IOException.");
		}
	}
	
	public long nextLong() {
		try {
			long ret = 0;
			
			eatDelimiters();
			
			boolean positive = true;
			if(buf[bufi] == '-') {
				++bufi;
				if(!pumpBuf()) throw new RuntimeException("IO.nextLong: Invalid long.");
				positive = false;
			}
			
			boolean first = true;
			while(true) {
				if(!pumpBuf()) break;
				if(isDelimiter(buf[bufi])) {
					if(first) throw new RuntimeException("IO.nextLong: Invalid long.");
					break;
				}
				first = false;
				
				if(buf[bufi] >= '0' && buf[bufi] <= '9') {
					if(ret < -922337203685477580L) throw new RuntimeException("IO.nextLong: Invalid long.");
					ret *= 10;
					ret -= (long)(buf[bufi] - '0');
					if(ret > 0) throw new RuntimeException("IO.nextLong: Invalid long.");
				} else {
					throw new RuntimeException("IO.nextLong: Invalid long.");
				}
				
				++bufi;
			}
			
			if(positive) {
				if(ret == -9223372036854775808L) throw new RuntimeException("IO.nextLong: Invalid long.");
				ret = -ret;
			}
			
			return ret;
		} catch(IOException e) {
			throw new RuntimeException("IO.nextLong: Caught IOException.");
		}
	}
	
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
`200 5986 845897 759781 171305 7836...` view save

correct output
`1 1 2 3 4 1 1 2 4 1 2 1 2 5 6 ...` view save

user output
`1 1 2 3 4 1 1 2 4 1 2 1 2 5 6 ...` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`200 607815 909742 130099 813674 34...` view save

correct output
`1 1 3 1 5 1 1 3 4 5 1 1 1 4 10...` view save

user output
`1 1 3 1 5 1 1 3 4 5 1 1 1 4 10...` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`200 921591 381013 930275 151815 69...` view save

correct output
`1 2 1 4 5 1 2 3 4 1 2 7 1 2 3 ...` view save

user output
`1 2 1 4 5 1 2 3 4 1 2 7 1 2 3 ...` view save

Test 4

Group: 2

Verdict: RUNTIME ERROR

input
`5000 952303 272950 268680 897180 13...` view save

correct output
`1 2 3 1 2 1 4 8 9 10 1 2 13 14...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:17)

Test 5

Group: 2

Verdict: RUNTIME ERROR

input
`5000 815856 460818 496023 308974 33...` view save

correct output
`1 2 3 4 5 1 1 2 9 1 11 12 13 1...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:17)

Test 6

Group: 2

Verdict: RUNTIME ERROR

input
`5000 4889 373080 366119 72135 10214...` view save

correct output
`1 1 2 3 4 1 1 2 3 4 5 1 2 3 1 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:17)

Test 7

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 444890 370930 385763 316218 44...` view save

correct output
`1 2 3 4 1 2 3 4 9 1 2 1 4 5 6 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 8

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 202077 270536 246808 189471 19...` view save

correct output
`1 1 2 3 4 1 1 3 4 5 1 2 8 9 10...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 9

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 736301 784710 628727 708231 64...` view save

correct output
`1 1 3 4 5 6 7 1 2 1 4 1 1 7 1 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 10

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 242104 238293 242641 242281 24...` view save

correct output
`1 2 1 2 3 1 2 3 1 2 1 4 11 12 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 11

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 252952 189698 245317 275463 24...` view save

correct output
`1 2 1 1 2 4 7 1 2 3 1 2 3 1 1 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 12

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 214451 357457 213436 351167 21...` view save

correct output
`1 1 2 1 4 5 6 7 8 9 1 1 3 4 5 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 13

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 363703 361248 358992 356404 35...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 14

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 718920 716974 715476 714540 71...` view save

correct output
`1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 15

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 614078 647174 701983 580935 58...` view save

correct output
`1 1 1 3 4 1 6 8 9 1 1 3 4 14 1...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 16

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 788376 788632 788880 789118 78...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 17

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 711774 711541 711305 711627 71...` view save

correct output
`1 2 3 1 2 6 1 2 1 2 3 6 7 1 2 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 18

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 685798 944128 587123 653271 65...` view save

correct output
`1 1 2 3 4 1 2 7 8 10 11 1 1 3 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 19

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 734074 734109 733868 733873 73...` view save

correct output
`1 1 3 4 5 1 1 1 1 1 1 1 3 5 6 ...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Test 20

Group: 3

Verdict: RUNTIME ERROR

input
`1000000 143117 1 267468 262833 141471 ...` view save

correct output
`1 2 1 2 3 1 1 2 4 1 2 10 11 12...` view save

user output
(empty)

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Main.main(Main.java:14)

Datatähti 2015 loppu

Pörssihai

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Tasks

Submissions (Kuha)