CSES - Putka Open 2015 – 6/6 - Results
Submission details
Task:Shakki
Sender:
Submission time:2015-12-06 23:08:32 +0200
Language:Java
Status:READY
Result:73
Feedback
groupverdictscore
#1ACCEPTED28
#2ACCEPTED21
#3ACCEPTED24
#40
Test results
testverdicttimegroup
#1ACCEPTED0.76 s1details
#2ACCEPTED0.75 s1details
#3ACCEPTED0.76 s1details
#4ACCEPTED0.75 s1details
#5ACCEPTED0.76 s1details
#6ACCEPTED0.76 s1details
#7ACCEPTED0.76 s1details
#8ACCEPTED0.75 s1details
#9ACCEPTED0.76 s1details
#10ACCEPTED0.75 s1details
#11ACCEPTED0.76 s2details
#12ACCEPTED0.76 s2details
#13ACCEPTED0.81 s2details
#14ACCEPTED0.76 s2details
#15ACCEPTED0.75 s2details
#16ACCEPTED0.73 s2details
#17ACCEPTED0.75 s2details
#18ACCEPTED0.75 s2details
#19ACCEPTED0.76 s2details
#20ACCEPTED0.76 s2details
#21ACCEPTED0.75 s3details
#22ACCEPTED0.76 s3details
#23ACCEPTED0.76 s3details
#24ACCEPTED0.76 s3details
#25ACCEPTED0.76 s3details
#26ACCEPTED0.76 s3details
#27ACCEPTED0.76 s3details
#28ACCEPTED0.76 s3details
#29ACCEPTED0.75 s3details
#30ACCEPTED0.77 s3details
#31ACCEPTED0.76 s4details
#32ACCEPTED0.74 s4details
#330.76 s4details
#34ACCEPTED0.75 s4details
#350.76 s4details
#36ACCEPTED0.75 s4details
#37ACCEPTED0.76 s4details
#38ACCEPTED0.75 s4details
#39ACCEPTED0.77 s4details
#40ACCEPTED0.76 s4details

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 < 550) {
            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: ACCEPTED

input
VMMVVMVV
MMVVMVVV
MMVVMMMM
MVVVMVVM
MVVVVMVM
...

correct output
100000

user output
178
7 6
5 4
2 3
1 7
...

Test 2

Group: 1

Verdict: ACCEPTED

input
MVMVVMMV
VVMMVVVV
VMMVMMVM
MVVVVMVM
MVMVMMVM
...

correct output
100000

user output
60
4 2
1 7
4 6
1 3
...

Test 3

Group: 1

Verdict: ACCEPTED

input
VMMMVMVV
MMMVMVMV
VMMVMVVM
VVVMVMMV
MVMVMVMV
...

correct output
100000

user output
98
3 1
7 5
1 3
2 7
...

Test 4

Group: 1

Verdict: ACCEPTED

input
VVVMVMVV
VMMVMVMM
MVVMMVMV
VMVMMVMM
MMVVMMVM
...

correct output
100000

user output
117
4 3
6 4
4 6
7 6
...

Test 5

Group: 1

Verdict: ACCEPTED

input
MVMVVMMM
VVMMVVMV
MVVMVVMM
VMVMVMMV
MMVMVVVM
...

correct output
100000

user output
239
5 1
4 1
5 7
2 1
...

Test 6

Group: 1

Verdict: ACCEPTED

input
VMMVMVVM
VVMMVVMM
MMMVMVVM
VMMVMMVM
MVMVMMMV
...

correct output
100000

user output
133
5 7
6 6
7 4
7 1
...

Test 7

Group: 1

Verdict: ACCEPTED

input
MVVVVMMM
MMMMMMMM
VVVVVMMV
MMVVMVVM
VMVVVVMV
...

correct output
100000

user output
194
4 1
5 2
1 2
6 6
...

Test 8

Group: 1

Verdict: ACCEPTED

input
VMMVMVMM
MMMVVMMM
MVVVVVVV
VVVVMMMV
MVVVMVVM
...

correct output
100000

user output
95
1 2
3 2
7 7
6 6
...

Test 9

Group: 1

Verdict: ACCEPTED

input
VVVVVMMM
MMVVVVVV
MVVVMMMM
VVMVVVVM
VMMVMVMM
...

correct output
100000

user output
178
5 2
7 4
5 5
1 3
...

Test 10

Group: 1

Verdict: ACCEPTED

input
VMMVMMMM
VVMVVVVV
VMMVMVMV
VMMVMVMM
VVVMMMMM
...

correct output
100000

user output
88
5 1
5 1
6 6
4 6
...

Test 11

Group: 2

Verdict: ACCEPTED

input
VMVMVVMM
MMVMVVMM
VMVVVMMV
VVVMVMVM
VVMMVVMM
...

correct output
25000

user output
174
2 1
4 4
6 5
1 1
...

Test 12

Group: 2

Verdict: ACCEPTED

input
MVMVVMVV
VMMVVMVM
VMVVVMMM
VMMMMVVM
MMVVVMMM
...

correct output
25000

user output
130
2 5
5 2
5 4
7 5
...

Test 13

Group: 2

Verdict: ACCEPTED

input
MVVMMVVV
MMVVMVMM
VVVMVMVV
VMVMMMMM
MVVMMVMV
...

correct output
25000

user output
184
6 3
1 2
3 6
2 7
...

Test 14

Group: 2

Verdict: ACCEPTED

input
VVMMMVMV
VMVVVMVV
VVMVVVMM
MVVMVMVM
MMVVMMMM
...

correct output
25000

user output
158
1 4
6 6
6 6
2 6
...

Test 15

Group: 2

Verdict: ACCEPTED

input
MVVVMVVV
MMMMVMMM
MVMMMVVM
MMVVVMVM
VMVVVMMV
...

correct output
25000

user output
118
7 5
2 5
4 3
7 1
...

Test 16

Group: 2

Verdict: ACCEPTED

input
VMMVMVVM
VMMVVVVV
MVMVMMVM
VMMVVVMV
VVMVMMVM
...

correct output
25000

user output
70
3 3
6 2
4 6
5 3
...

Test 17

Group: 2

Verdict: ACCEPTED

input
MVVMMVVM
MVVVMMMV
MVVMMVVM
VMMVMVMV
VMMVMMMM
...

correct output
25000

user output
72
3 7
4 2
1 4
4 4
...

Test 18

Group: 2

Verdict: ACCEPTED

input
MVMMVVMM
VVMMMMVV
VMVVVVVM
MVMMMVMV
VMVVVMVM
...

correct output
25000

user output
77
4 1
5 6
2 2
5 2
...

Test 19

Group: 2

Verdict: ACCEPTED

input
MVVVVVVV
VMMVMVVM
VMVMMMMV
MVMVMMMM
MMVVVMMM
...

correct output
25000

user output
101
3 6
7 2
7 5
1 1
...

Test 20

Group: 2

Verdict: ACCEPTED

input
MVVVMMMM
MMVMMVMV
MVVVVVMM
VVMMMVVM
VVVMVMVV
...

correct output
25000

user output
96
4 1
3 3
2 6
2 6
...

Test 21

Group: 3

Verdict: ACCEPTED

input
VMVVMVMM
MMMMVMMV
VVVMVVVV
MVMVMVVM
VMMVMMMM
...

correct output
5000

user output
100
4 7
5 2
2 1
1 2
...

Test 22

Group: 3

Verdict: ACCEPTED

input
VVVVVVMM
MMMVMMVV
VVVVVVMV
MMMVMVVV
MVVMMMMV
...

correct output
5000

user output
337
5 4
4 3
6 1
2 6
...

Test 23

Group: 3

Verdict: ACCEPTED

input
MMVMVMVV
MMVVMVVM
VMMVVMVM
MMMMMMVV
MVVVVMVM
...

correct output
5000

user output
292
7 7
2 4
3 2
5 7
...

Test 24

Group: 3

Verdict: ACCEPTED

input
MVMVVMVM
VVMVVMVM
MMMMVMVV
MVVMMVVV
MMMMMVVV
...

correct output
5000

user output
257
7 2
1 6
2 2
2 7
...

Test 25

Group: 3

Verdict: ACCEPTED

input
MVVVMVVM
MMMMVVMV
VMMVMMVV
VVMVMVMV
MVMMMVMM
...

correct output
5000

user output
87
1 3
3 2
3 1
1 6
...

Test 26

Group: 3

Verdict: ACCEPTED

input
VMVMVVVM
MMMVVVMM
MMVVVVVM
VVVVMMVV
VMMVVMMV
...

correct output
5000

user output
206
4 3
2 2
7 1
7 1
...

Test 27

Group: 3

Verdict: ACCEPTED

input
MMVMMVVM
MVVVMVMV
MVVVMVVM
VMVMMMVV
VMMVVVVV
...

correct output
5000

user output
126
3 4
3 7
1 5
4 1
...

Test 28

Group: 3

Verdict: ACCEPTED

input
MVMMVMMV
VMVMMMVV
MMMMVVMV
VVVVMMMM
MMMVMMVV
...

correct output
5000

user output
96
7 4
7 6
1 5
6 1
...

Test 29

Group: 3

Verdict: ACCEPTED

input
VVVVMVMV
MMMVVMVM
MVVVMVMV
VVVMVVMM
VMMMMMVV
...

correct output
5000

user output
147
3 4
1 2
6 7
7 6
...

Test 30

Group: 3

Verdict: ACCEPTED

input
MVVVMVVV
MMVVMMMM
MVVVVVVV
MVMVMMMV
VMMMVMMM
...

correct output
5000

user output
137
5 1
6 3
7 3
7 7
...

Test 31

Group: 4

Verdict: ACCEPTED

input
MVMMVMMV
VVVMMVVV
VMMVVMMV
VVMMMVVM
VVVMMMVV
...

correct output
250

user output
196
2 4
6 6
4 5
1 7
...

Test 32

Group: 4

Verdict: ACCEPTED

input
VVMMVVVM
VMVVMMVV
VMMMMMMV
VVMVMVVV
VMMVMVMM
...

correct output
250

user output
73
2 1
7 3
1 5
6 3
...

Test 33

Group: 4

Verdict:

input
MMVVMVMV
VVVMVMMM
VVVVMVMM
MVVMVVMV
VMMVMVVM
...

correct output
250

user output
261
5 6
2 1
6 5
5 6
...

Test 34

Group: 4

Verdict: ACCEPTED

input
VMVMVVMV
MVVMMMMM
MMVVMMMM
VMVMVVVM
VMMMVVVM
...

correct output
250

user output
150
5 4
3 1
1 4
7 7
...

Test 35

Group: 4

Verdict:

input
VMVMVMMM
VMMVVVMM
MMVMVMMM
MVMMVVVV
VMMVMMMV
...

correct output
250

user output
457
4 7
6 4
4 4
6 3
...

Test 36

Group: 4

Verdict: ACCEPTED

input
MVMVMVMM
MVMVMMMV
MMVVVVMM
MVMVVVVV
VMMMVVMM
...

correct output
250

user output
83
3 5
3 4
6 6
6 3
...

Test 37

Group: 4

Verdict: ACCEPTED

input
VMMMMVMM
VVMMMVMV
VMVVVVVV
MVMMMVVM
VMVMMVVM
...

correct output
250

user output
201
1 6
4 2
5 3
4 3
...

Test 38

Group: 4

Verdict: ACCEPTED

input
VMMVMVMV
VVMVMVMM
MMMVMVMM
MVVVVMMM
MMVVVMVV
...

correct output
250

user output
188
2 5
1 4
4 4
7 1
...

Test 39

Group: 4

Verdict: ACCEPTED

input
MMMMMVMV
MVVMMMMV
VMVVVVMM
VMVVVMMV
MVMMMVMM
...

correct output
250

user output
176
4 7
7 3
7 2
1 7
...

Test 40

Group: 4

Verdict: ACCEPTED

input
VMMMMMMV
VMMVVVVV
MVMMVMMV
MVVVVMMV
MVVVVMMM
...

correct output
250

user output
51
7 2
7 5
3 1
6 7
...