CSES - Putka Open 2015 – 3/6 - Results
Submission details
Task:Ruudukko
Sender:
Submission time:2015-09-12 01:44:34 +0300
Language:Java
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.20 s1details
#2ACCEPTED0.20 s1details
#3ACCEPTED0.20 s1details
#4ACCEPTED0.21 s1details
#5ACCEPTED0.21 s1details
#6ACCEPTED0.21 s2details
#7ACCEPTED0.22 s2details
#80.22 s2details
#90.21 s2details
#10ACCEPTED0.21 s2details
#110.19 s3details
#120.20 s3details
#130.19 s3details
#140.20 s3details
#150.20 s3details

Code

//package putka3.pkg2;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 *
 * @author Adreno
 */
public class Putka32 {

    public static boolean[][] r;
    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int goal = input.nextInt();
        r = new boolean[20][20];
        for (int x=0; x<20; x++) r[0][x] = true;
        for (int y=0; y<20; y++) r[y][19] = true;
        
        int nextEmptyLine = 1;
        while (calc() < goal) {
            for (int x=10; x<20; x++) {
                r[nextEmptyLine][x] = true;
            }
            nextEmptyLine++;
        }
        
        if (calc() > goal) {
            nextEmptyLine--;
            for (int x=10; x<19; x++) {
                r[nextEmptyLine][x] = false;
            }
        }
        
        for (int x=0; x<20; x++) r[19][x] = true;
        for (int y=0; y<20; y++) r[y][0] = true;
        
        nextEmptyLine += 2;
        if (calc() < goal) {
            for (int x=0; x<19; x++) {
                r[nextEmptyLine][x] = true;
            }
            nextEmptyLine++;
        }
        while (calc() < goal) {
            for (int x=14; x<20; x++) {
                r[nextEmptyLine][x] = true;
            }
            nextEmptyLine++;
        }
        if (calc() > goal) {
            nextEmptyLine--;
            for (int x=14; x<19; x++) {
                r[nextEmptyLine][x] = false;
            }
        }
        
        
        nextEmptyLine += 2;
        if (calc() < goal) {
            for (int x=0; x<19; x++) {
                r[nextEmptyLine][x] = true;
            }
            nextEmptyLine++;
        }
        while (calc() < goal) {
            for (int x=16; x<20; x++) {
                r[nextEmptyLine][x] = true;
            }
            nextEmptyLine++;
        }
        if (calc() > goal) {
            nextEmptyLine--;
            for (int x=16; x<19; x++) {
                r[nextEmptyLine][x] = false;
            }
        }
        
        nextEmptyLine += 2;
        if (calc() < goal) {
            for (int x=0; x<19; x++) {
                r[nextEmptyLine][x] = true;
            }
            nextEmptyLine++;
        }
        while (calc() < goal) {
            for (int x=17; x<20; x++) {
                r[nextEmptyLine][x] = true;
            }
            nextEmptyLine++;
        }
        if (calc() > goal) {
            nextEmptyLine--;
            for (int x=17; x<19; x++) {
                r[nextEmptyLine][x] = false;
            }
        }
        
        for (int x=2; x<19; x+=2) {
            if (calc() == goal) break;
            if (calc() > goal) {
                for (int y=1; y<19; y++) {
                    if (calc() <= goal) break;
                    r[y][x] = false;
                }
            }
            if (calc() < goal) {
                for (int y=1; y<19; y++) {
                    if (calc() >= goal) break;
                    r[y][x] = true;
                }
            }
        }
        

        
        
        //System.out.println("reached k=" + calc());
        
        for (int y=0; y<20; y++) {
            for (int x=0; x<20; x++) {
                System.out.print((r[y][x] ? "." : "#"));
            }
            System.out.println("");
        }
    }
    
    public static int calc() {
        ArrayDeque<Loc> jono = new ArrayDeque<>();
        jono.add(new Loc(0,0));
        boolean[][] kayty = new boolean[20][20];
        int[][] ways = new int[20][20];
        ways[0][0] = 1;
        while (!jono.isEmpty()) {
            Loc nyk = jono.poll();
            if (kayty[nyk.y][nyk.x]) continue;
            kayty[nyk.y][nyk.x] = true;
            //System.out.println("kaytiin y=" + nyk.y + ", x=" + nyk.x);
            if (nyk.y < 19 && r[nyk.y+1][nyk.x]) {
                ways[nyk.y+1][nyk.x] += ways[nyk.y][nyk.x];
                jono.add(new Loc(nyk.y+1, nyk.x));
            }
            if (nyk.x < 19 && r[nyk.y][nyk.x+1]) {
                ways[nyk.y][nyk.x+1] += ways[nyk.y][nyk.x];
                jono.add(new Loc(nyk.y, nyk.x+1));
            }
            
        }
        return ways[19][19];
    }
    
}

class Loc {
    public int x;
    public int y;

    public Loc(int y, int x) {
        this.x = x;
        this.y = y;
    }
    
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2

correct output
....................
.###################
.###################
.###################
.###################
...

user output
....................
.##################.
.##################.
.##################.
.##################.
...

Test 2

Group: 1

Verdict: ACCEPTED

input
5

correct output
....................
.################..#
.#################..
.#################..
.##################.
...

user output
....................
.##################.
.##################.
....................
.##################.
...

Test 3

Group: 1

Verdict: ACCEPTED

input
7

correct output
....................
.################..#
.#################..
.#################..
.##################.
...

user output
....................
.##################.
.##################.
....................
.##################.
...

Test 4

Group: 1

Verdict: ACCEPTED

input
8

correct output
....................
.###################
.###################
.###################
.###################
...

user output
....................
.##################.
.##################.
....................
.#############......
...

Test 5

Group: 1

Verdict: ACCEPTED

input
9

correct output
....................
.###################
.###################
.###################
.###################
...

user output
....................
.##################.
.##################.
....................
.#############......
...

Test 6

Group: 2

Verdict: ACCEPTED

input
19

correct output
....................
.############..#####
.#############..####
.#############...###
.##############...##
...

user output
....................
.#########..........
.##################.
.##################.
....................
...

Test 7

Group: 2

Verdict: ACCEPTED

input
32

correct output
....................
.###################
.###################
.###################
.###################
...

user output
....................
.#########..........
.##################.
.##################.
....................
...

Test 8

Group: 2

Verdict:

input
44

correct output
....................
.################..#
.#################..
.#################..
.##################.
...

user output
....................
.#.#.#.#.#..........
.#.#.#.#.#.#.#.#.#..
.#.#.#.#.#.#.#.#.##.
..................#.
...

Test 9

Group: 2

Verdict:

input
76

correct output
....................
.########..######..#
.#########..######..
.#########...#####..
.##########...#####.
...

user output
....................
.#.#.#.#.#..........
.#.#.#.#.#......#.#.
.#.#.#.#.#.#.#.####.
.#.#.#.#.#.#.#.####.
...

Test 10

Group: 2

Verdict: ACCEPTED

input
93

correct output
....................
.########..##..##..#
.#########..##..##..
.#########...#...#..
.##########...#...#.
...

user output
....................
.#########..........
.#########..........
.##################.
.##################.
...

Test 11

Group: 3

Verdict:

input
141

correct output
....................
.################..#
.#################..
.#################..
.##################.
...

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20
	at Putka32.main(Putka32.java:92)

Test 12

Group: 3

Verdict:

input
422

correct output
....................
.####..##########..#
.#####..##########..
.#####...#########..
.######...#########.
...

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20
	at Putka32.main(Putka32.java:86)

Test 13

Group: 3

Verdict:

input
671

correct output
....................
.#.##########..##..#
....##########..##..
.#...#########...#..
.##...#########...#.
...

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20
	at Putka32.main(Putka32.java:72)

Test 14

Group: 3

Verdict:

input
895

correct output
....................
.#.##..##..##..##..#
....##..##..##..##..
.#...#...#...#...#..
.##...#...#...#...#.
...

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20
	at Putka32.main(Putka32.java:86)

Test 15

Group: 3

Verdict:

input
956

correct output
....................
.#.##..######..##..#
....##..######..##..
.#...#...#####...#..
.##...#...#####...#.
...

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20
	at Putka32.main(Putka32.java:72)