CSES - Putka Open 2015 – 6/6 - Results
Submission details
Task:Shakki
Sender:
Submission time:2015-12-06 23:07:47 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#1--1details
#2--1details
#3--1details
#4--1details
#5--1details
#6--1details
#7--1details
#8--1details
#9--1details
#10--1details
#11--2details
#12--2details
#13--2details
#14--2details
#15--2details
#16--2details
#17--2details
#18--2details
#19--2details
#20--2details
#21--3details
#22--3details
#23--3details
#24--3details
#25--3details
#26--3details
#27--3details
#28--3details
#29--3details
#30--3details
#31--4details
#32--4details
#33--4details
#34--4details
#35--4details
#36--4details
#37--4details
#38--4details
#39--4details
#40--4details

Code

//package shakki;

import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;
import java.util.TreeSet;

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

    public static boolean[][] t;
    public static boolean[][] alkup;
    
    public static void main(String[] args) {
        boolean debug = false;
        // debug = true;
        Scanner s = new Scanner(System.in);
        t = new boolean[8][8];
        alkup = new boolean[8][8];
        
        //TreeSet<Ruutu> collisions = new TreeSet<>();
        //int[][] collisions = new int[8][8];
        for (int y=0; y<8; y++) {
            String line = s.next();
            for (int x=0; x<8; x++) {
                if (line.charAt(x) == 'M') {
                    t[y][x] = true;
                    alkup[y][x] = true;
                }
            }
        }
        for (int x=0; x<8; x++) {
            for (int y=1; y<8; y++) {
                if (t[y-1][x] == t[y][x]) {
                    //col.add(new Collision(y-1,x, y,x));
                }
            }
        }
        int score = score();
        
        Random rng = new Random();
        ArrayList<String> parasTunnettu = null;
        ArrayList<String> siirrot = new ArrayList<>();
        long timeAlussa = System.currentTimeMillis();
        while (System.currentTimeMillis() - timeAlussa < 850) {
            if (score == 0) {
                if (debug) System.out.println("done, siirtoja=" + siirrot.size());
                if (parasTunnettu == null || parasTunnettu.size() > siirrot.size()) {
                    parasTunnettu = siirrot;
                }
                for (int y=0; y<8; y++) {
                    for (int x=0; x<8; x++) {
                        t[y][x] = alkup[y][x];
                    }
                }
                score = score();
                siirrot = new ArrayList<>();
            }
            int y = rng.nextInt(7);
            int x = rng.nextInt(7);
            kaanna(y,x);
            int newScore = score();
            if (newScore > score && rng.nextInt(100) >= 1) {
                peruKaanto(y,x);
            }
            else if (newScore == score && rng.nextInt(10) >= 1) {
                peruKaanto(y,x);
            }
            else {
                score = newScore;
                siirrot.add((x+1) + " " + (y+1));
            }
        }
        System.out.println(parasTunnettu.size());
        if (!debug) {
            for (String siirto : parasTunnettu) System.out.println(siirto);
        }
    }
    
    public static void kaanna(int y, int x) {
        boolean vasenYla = t[y][x];
        boolean oikeaYla = t[y][x+1];
        boolean vasenAla = t[y+1][x];
        boolean oikeaAla = t[y+1][x+1];
        t[y][x] = vasenAla;
        t[y][x+1] = vasenYla;
        t[y+1][x+1] = oikeaYla;
        t[y+1][x] = oikeaAla;        
    }
    public static void peruKaanto(int y, int x) {
        boolean vasenYla = t[y][x];
        boolean oikeaYla = t[y][x+1];
        boolean vasenAla = t[y+1][x];
        boolean oikeaAla = t[y+1][x+1];
        t[y][x] = oikeaYla;
        t[y][x+1] = oikeaAla;
        t[y+1][x+1] = vasenAla;
        t[y+1][x] = vasenYla;        
    }
    
    public static int score() {
        int count = 0;
        for (int y=1; y<8; y++) {
            for (int x=1; x<8; x++) {
                if (t[y][x] == t[y-1][x]) count++;
                if (t[y][x] == t[y][x-1]) count++;
            }
        }
        for (int x=1; x<8; x++) {
            if (t[0][x] == t[0][x-1]) count++;
        }
        for (int y=1; y<8; y++) {
            if (t[y][0] == t[y-1][0]) count++;
        }
        return count;
    }
    
    public static int scoreAndSaveCollisionSpots() {
        int count = 0;
        for (int y=1; y<8; y++) {
            for (int x=1; x<8; x++) {
                if (t[y][x] == t[y-1][x]) count++;
                if (t[y][x] == t[y][x-1]) count++;
            }
        }
        for (int x=1; x<8; x++) {
            if (t[0][x] == t[0][x-1]) count++;
        }
        for (int y=1; y<8; y++) {
            if (t[y][0] == t[y-1][0]) count++;
        }
        return count;
    }
    
}

//class CollisionDB {
//    public TreeSet<Ruutu> db;
//
//    public CollisionDB() {
//        this.db = new TreeSet<>();
//    }
//    
//    public addCollision(int y, int x) {
//        Ruutu r = new Ruutu(y, x);
//        Ruutu
//    }
//    
//}

class Ruutu implements Comparable<Ruutu> {
    public int y;
    public int x;
    public int count;

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

    @Override
    public int compareTo(Ruutu o) {
        if (o.y != this.y) return this.y - o.y;
        return (this.x - o.x);
    }
    
    
}

class Collision {
    public int y1;
    public int x1;
    public int y2;
    public int x2;

    public Collision(int y1, int x1, int y2, int x2) {
        this.y1 = y1;
        this.x1 = x1;
        this.y2 = y2;
        this.x2 = x2;
    }
    
}

Test details

Test 1

Group: 1

Verdict:

input
VMMVVMVV
MMVVMVVV
MMVVMMMM
MVVVMVVM
MVVVVMVM
...

correct output
100000

user output
(empty)

Test 2

Group: 1

Verdict:

input
MVMVVMMV
VVMMVVVV
VMMVMMVM
MVVVVMVM
MVMVMMVM
...

correct output
100000

user output
(empty)

Test 3

Group: 1

Verdict:

input
VMMMVMVV
MMMVMVMV
VMMVMVVM
VVVMVMMV
MVMVMVMV
...

correct output
100000

user output
(empty)

Test 4

Group: 1

Verdict:

input
VVVMVMVV
VMMVMVMM
MVVMMVMV
VMVMMVMM
MMVVMMVM
...

correct output
100000

user output
(empty)

Test 5

Group: 1

Verdict:

input
MVMVVMMM
VVMMVVMV
MVVMVVMM
VMVMVMMV
MMVMVVVM
...

correct output
100000

user output
(empty)

Test 6

Group: 1

Verdict:

input
VMMVMVVM
VVMMVVMM
MMMVMVVM
VMMVMMVM
MVMVMMMV
...

correct output
100000

user output
(empty)

Test 7

Group: 1

Verdict:

input
MVVVVMMM
MMMMMMMM
VVVVVMMV
MMVVMVVM
VMVVVVMV
...

correct output
100000

user output
(empty)

Test 8

Group: 1

Verdict:

input
VMMVMVMM
MMMVVMMM
MVVVVVVV
VVVVMMMV
MVVVMVVM
...

correct output
100000

user output
(empty)

Test 9

Group: 1

Verdict:

input
VVVVVMMM
MMVVVVVV
MVVVMMMM
VVMVVVVM
VMMVMVMM
...

correct output
100000

user output
(empty)

Test 10

Group: 1

Verdict:

input
VMMVMMMM
VVMVVVVV
VMMVMVMV
VMMVMVMM
VVVMMMMM
...

correct output
100000

user output
(empty)

Test 11

Group: 2

Verdict:

input
VMVMVVMM
MMVMVVMM
VMVVVMMV
VVVMVMVM
VVMMVVMM
...

correct output
25000

user output
(empty)

Test 12

Group: 2

Verdict:

input
MVMVVMVV
VMMVVMVM
VMVVVMMM
VMMMMVVM
MMVVVMMM
...

correct output
25000

user output
(empty)

Test 13

Group: 2

Verdict:

input
MVVMMVVV
MMVVMVMM
VVVMVMVV
VMVMMMMM
MVVMMVMV
...

correct output
25000

user output
(empty)

Test 14

Group: 2

Verdict:

input
VVMMMVMV
VMVVVMVV
VVMVVVMM
MVVMVMVM
MMVVMMMM
...

correct output
25000

user output
(empty)

Test 15

Group: 2

Verdict:

input
MVVVMVVV
MMMMVMMM
MVMMMVVM
MMVVVMVM
VMVVVMMV
...

correct output
25000

user output
(empty)

Test 16

Group: 2

Verdict:

input
VMMVMVVM
VMMVVVVV
MVMVMMVM
VMMVVVMV
VVMVMMVM
...

correct output
25000

user output
(empty)

Test 17

Group: 2

Verdict:

input
MVVMMVVM
MVVVMMMV
MVVMMVVM
VMMVMVMV
VMMVMMMM
...

correct output
25000

user output
(empty)

Test 18

Group: 2

Verdict:

input
MVMMVVMM
VVMMMMVV
VMVVVVVM
MVMMMVMV
VMVVVMVM
...

correct output
25000

user output
(empty)

Test 19

Group: 2

Verdict:

input
MVVVVVVV
VMMVMVVM
VMVMMMMV
MVMVMMMM
MMVVVMMM
...

correct output
25000

user output
(empty)

Test 20

Group: 2

Verdict:

input
MVVVMMMM
MMVMMVMV
MVVVVVMM
VVMMMVVM
VVVMVMVV
...

correct output
25000

user output
(empty)

Test 21

Group: 3

Verdict:

input
VMVVMVMM
MMMMVMMV
VVVMVVVV
MVMVMVVM
VMMVMMMM
...

correct output
5000

user output
(empty)

Test 22

Group: 3

Verdict:

input
VVVVVVMM
MMMVMMVV
VVVVVVMV
MMMVMVVV
MVVMMMMV
...

correct output
5000

user output
(empty)

Test 23

Group: 3

Verdict:

input
MMVMVMVV
MMVVMVVM
VMMVVMVM
MMMMMMVV
MVVVVMVM
...

correct output
5000

user output
(empty)

Test 24

Group: 3

Verdict:

input
MVMVVMVM
VVMVVMVM
MMMMVMVV
MVVMMVVV
MMMMMVVV
...

correct output
5000

user output
(empty)

Test 25

Group: 3

Verdict:

input
MVVVMVVM
MMMMVVMV
VMMVMMVV
VVMVMVMV
MVMMMVMM
...

correct output
5000

user output
(empty)

Test 26

Group: 3

Verdict:

input
VMVMVVVM
MMMVVVMM
MMVVVVVM
VVVVMMVV
VMMVVMMV
...

correct output
5000

user output
(empty)

Test 27

Group: 3

Verdict:

input
MMVMMVVM
MVVVMVMV
MVVVMVVM
VMVMMMVV
VMMVVVVV
...

correct output
5000

user output
(empty)

Test 28

Group: 3

Verdict:

input
MVMMVMMV
VMVMMMVV
MMMMVVMV
VVVVMMMM
MMMVMMVV
...

correct output
5000

user output
(empty)

Test 29

Group: 3

Verdict:

input
VVVVMVMV
MMMVVMVM
MVVVMVMV
VVVMVVMM
VMMMMMVV
...

correct output
5000

user output
(empty)

Test 30

Group: 3

Verdict:

input
MVVVMVVV
MMVVMMMM
MVVVVVVV
MVMVMMMV
VMMMVMMM
...

correct output
5000

user output
(empty)

Test 31

Group: 4

Verdict:

input
MVMMVMMV
VVVMMVVV
VMMVVMMV
VVMMMVVM
VVVMMMVV
...

correct output
250

user output
(empty)

Test 32

Group: 4

Verdict:

input
VVMMVVVM
VMVVMMVV
VMMMMMMV
VVMVMVVV
VMMVMVMM
...

correct output
250

user output
(empty)

Test 33

Group: 4

Verdict:

input
MMVVMVMV
VVVMVMMM
VVVVMVMM
MVVMVVMV
VMMVMVVM
...

correct output
250

user output
(empty)

Test 34

Group: 4

Verdict:

input
VMVMVVMV
MVVMMMMM
MMVVMMMM
VMVMVVVM
VMMMVVVM
...

correct output
250

user output
(empty)

Test 35

Group: 4

Verdict:

input
VMVMVMMM
VMMVVVMM
MMVMVMMM
MVMMVVVV
VMMVMMMV
...

correct output
250

user output
(empty)

Test 36

Group: 4

Verdict:

input
MVMVMVMM
MVMVMMMV
MMVVVVMM
MVMVVVVV
VMMMVVMM
...

correct output
250

user output
(empty)

Test 37

Group: 4

Verdict:

input
VMMMMVMM
VVMMMVMV
VMVVVVVV
MVMMMVVM
VMVMMVVM
...

correct output
250

user output
(empty)

Test 38

Group: 4

Verdict:

input
VMMVMVMV
VVMVMVMM
MMMVMVMM
MVVVVMMM
MMVVVMVV
...

correct output
250

user output
(empty)

Test 39

Group: 4

Verdict:

input
MMMMMVMV
MVVMMMMV
VMVVVVMM
VMVVVMMV
MVMMMVMM
...

correct output
250

user output
(empty)

Test 40

Group: 4

Verdict:

input
VMMMMMMV
VMMVVVVV
MVMMVMMV
MVVVVMMV
MVVVVMMM
...

correct output
250

user output
(empty)