CSES - Datatähti 2016 alku - Results
Submission details
Task:Bittipeli
Sender:kalh
Submission time:2015-10-03 17:40:26 +0300
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#10.17 s1details
#20.19 s1details
#30.17 s1details
#40.19 s1details
#50.18 s1details
#60.18 s1details
#70.18 s1details
#80.17 s1details
#90.17 s1details
#100.18 s1details
#110.19 s1details
#120.17 s1details
#130.19 s1details
#140.18 s1details
#150.17 s1details
#160.18 s1details
#170.17 s1details
#180.18 s1details
#190.17 s1details
#200.18 s1details
#210.17 s2details
#220.19 s2details
#230.17 s2details
#240.17 s2details
#250.19 s2details
#260.18 s2details
#270.18 s2details
#280.18 s2details
#290.19 s2details
#300.18 s2details
#310.17 s2details
#320.19 s2details
#330.18 s2details
#340.18 s2details
#350.18 s2details
#360.00 s2details
#370.00 s2details
#380.00 s2details
#390.20 s2details
#400.19 s2details
#410.17 s3details
#420.17 s3details
#430.19 s3details
#440.17 s3details
#450.17 s3details
#460.17 s3details
#470.18 s3details
#480.17 s3details
#490.18 s3details
#500.18 s3details
#510.17 s3details
#520.17 s3details
#530.18 s3details
#540.17 s3details
#550.17 s3details
#560.00 s3details
#570.00 s3details
#580.00 s3details
#590.00 s3details
#600.28 s3details
#610.18 s4details
#620.17 s4details
#630.18 s4details
#640.17 s4details
#650.18 s4details
#660.17 s4details
#670.18 s4details
#680.17 s4details
#690.17 s4details
#700.17 s4details
#710.19 s4details
#720.18 s4details
#730.17 s4details
#740.18 s4details
#750.17 s4details
#760.00 s4details
#770.00 s4details
#780.00 s4details
#790.00 s4details
#800.00 s4details

Code

import java.util.*;

public class Tehtava5 {
	
	private static IO io;
	private static HashMap<String, String> arvotaulukko;
	private static HashMap<String, Integer> askelTaulukko;
	private static int yhteensaAskeleita;
	private static long a;

	public static String suorita(String jono) {
		
		String tulos = poistaJonoja(jono, 0, 0);
		
		return tulos;
		
	}
	
	public static String poistaJonoja(String jono, int indeksi, int pituus) {
		int alku = 0;
		
		String jono1 = new StringBuilder().append(jono).delete(indeksi, indeksi+pituus).toString();
		
		System.out.println(jono + " ---> " + jono1);
		//System.out.println("poistot" +": " + poistot);
		
		if (arvotaulukko.containsKey(jono1)) {
			return arvotaulukko.get(jono1);
		}
		
		
		pituus = 1;
		int poistoindeksi = 0;
		boolean mahdollisia = true;
		String uusi;
		for (int i = 0; i < jono1.length() - 1; i++) {

			if (jono1.charAt(i) != jono1.charAt(i + 1)) {
				mahdollisia = false;
				if (pituus > 1) {
					poistoindeksi++;

					uusi = poistaJonoja(jono1, alku, pituus);
				
					if (!uusi.equals("")) {
						//arvotaulukko.put(jono1, Integer.toString(poistoindeksi).concat(" ").concat(uusi));
						return Integer.toString(poistoindeksi).concat(" ").concat(uusi);
					}
	

				} 
				
				pituus = 1;
				alku = i+1;
			}

			else {
				pituus++;
			}

		}
		
		if (mahdollisia && jono1.length() != 1) {
			String s = Integer.toString(1);
			arvotaulukko.put(jono1, s);
			return s;
		}
		
		arvotaulukko.put(jono1, "");
		
		return "";

	}
	
	public static String luoSatunnainen(int pituus) {
		StringBuilder sb = new StringBuilder();
		Random r = new Random();
		for (int i = 0; i<pituus; i++) {
			sb.append(r.nextInt(2));
		}
		
		return sb.toString();
	}
	
	
	public static void main(String[] args) {
		
		io = new IO();
		String arvo;
		arvo = io.next();
		//long t = System.currentTimeMillis();
	//	arvo = "11101";
		//System.out.println(arvo + "|||");
		//askelTaulukko = new HashMap<String, Integer>();
		String tulos;
			
		//arvo = "00110100100101100100101010101010101010101010101001101101100100101011001";
		//arvo = "110100100101100100101010101010101010101010101001101101100100101011001";
		//a = System.currentTimeMillis();
		
		arvotaulukko = new HashMap<String, String>();
		tulos = suorita(arvo);
		
		if (tulos.length() == 0) {
			io.print("QAQ");
		}
		else {
			int askeleita = tulos.split("\\s+").length;
			io.print(askeleita + "\n");
			io.print(tulos);
		}
		
	//	long kesto = System.currentTimeMillis()-a;
		//System.out.println("Kesto: " + kesto);
		
	//	System.out.println(((System.currentTimeMillis()-t) + "ms"));
		io.close();

	}

}

Test details

Test 1

Group: 1

Verdict:

input
1011001010

correct output
QAQ

user output
1011001010 ---> 1011001010
1011001010 ---> 10001010
10001010 ---> 11010
11010 ---> 010
1011001010 ---> 10111010
...

Test 2

Group: 1

Verdict:

input
0000001001

correct output
3
1 1 1 

user output
0000001001 ---> 0000001001
0000001001 ---> 1001
1001 ---> 11
3
1 1 1

Test 3

Group: 1

Verdict:

input
0111011100

correct output
3
2 1 1 

user output
0111011100 ---> 0111011100
0111011100 ---> 0011100
0011100 ---> 11100
11100 ---> 00
4
...

Test 4

Group: 1

Verdict:

input
0100100100

correct output
4
2 1 1 1 

user output
0100100100 ---> 0100100100
0100100100 ---> 01100100
01100100 ---> 000100
000100 ---> 100
01100100 ---> 011100
...

Test 5

Group: 1

Verdict:

input
1110010110

correct output
4
2 1 1 1 

user output
1110010110 ---> 1110010110
1110010110 ---> 0010110
0010110 ---> 10110
10110 ---> 100
0010110 ---> 00100
...

Test 6

Group: 1

Verdict:

input
1111110110

correct output
3
1 1 1 

user output
1111110110 ---> 1111110110
1111110110 ---> 0110
0110 ---> 00
3
1 1 1

Test 7

Group: 1

Verdict:

input
0011110001

correct output
3
1 2 1 

user output
0011110001 ---> 0011110001
0011110001 ---> 11110001
11110001 ---> 0001
0001 ---> 1
11110001 ---> 11111
...

Test 8

Group: 1

Verdict:

input
0111111000

correct output
2
1 1 

user output
0111111000 ---> 0111111000
0111111000 ---> 0000
2
1 1

Test 9

Group: 1

Verdict:

input
1111111100

correct output
2
1 1 

user output
1111111100 ---> 1111111100
1111111100 ---> 00
2
1 1

Test 10

Group: 1

Verdict:

input
1000010011

correct output
3
2 1 1 

user output
1000010011 ---> 1000010011
1000010011 ---> 110011
110011 ---> 0011
0011 ---> 11
4
...

Test 11

Group: 1

Verdict:

input
1101110000

correct output
3
1 1 1 

user output
1101110000 ---> 1101110000
1101110000 ---> 01110000
01110000 ---> 00000
3
1 1 1

Test 12

Group: 1

Verdict:

input
1101101100

correct output
4
1 2 1 1 

user output
1101101100 ---> 1101101100
1101101100 ---> 01101100
01101100 ---> 001100
001100 ---> 1100
1100 ---> 00
...

Test 13

Group: 1

Verdict:

input
0100111110

correct output
3
1 1 1 

user output
0100111110 ---> 0100111110
0100111110 ---> 01111110
01111110 ---> 00
3
1 1 1

Test 14

Group: 1

Verdict:

input
1101001011

correct output
4
2 2 2 1 

user output
1101001011 ---> 1101001011
1101001011 ---> 01001011
01001011 ---> 011011
011011 ---> 0011
0011 ---> 11
...

Test 15

Group: 1

Verdict:

input
1110110010

correct output
4
1 2 1 1 

user output
1110110010 ---> 1110110010
1110110010 ---> 0110010
0110010 ---> 00010
00010 ---> 10
0110010 ---> 01110
...

Test 16

Group: 1

Verdict:

input
0011011100

correct output
3
3 2 1 

user output
0011011100 ---> 0011011100
0011011100 ---> 11011100
11011100 ---> 011100
011100 ---> 000
4
...

Test 17

Group: 1

Verdict:

input
1100101011

correct output
QAQ

user output
1100101011 ---> 1100101011
1100101011 ---> 00101011
00101011 ---> 101011
1100101011 ---> 11101011
11101011 ---> 01011
...

Test 18

Group: 1

Verdict:

input
1101100111

correct output
3
2 2 1 

user output
1101100111 ---> 1101100111
1101100111 ---> 01100111
01100111 ---> 000111
000111 ---> 111
4
...

Test 19

Group: 1

Verdict:

input
0110000100

correct output
3
2 1 1 

user output
0110000100 ---> 0110000100
0110000100 ---> 00000100
00000100 ---> 100
0110000100 ---> 011100
011100 ---> 000
...

Test 20

Group: 1

Verdict:

input
0000101000

correct output
QAQ

user output
0000101000 ---> 0000101000
0000101000 ---> 101000
QAQ

Test 21

Group: 2

Verdict:

input
1110010100

correct output
QAQ

user output
1110010100 ---> 1110010100
1110010100 ---> 0010100
0010100 ---> 10100
1110010100 ---> 11110100
11110100 ---> 0100
...

Test 22

Group: 2

Verdict:

input
1110010000

correct output
3
2 1 1 

user output
1110010000 ---> 1110010000
1110010000 ---> 0010000
0010000 ---> 10000
1110010000 ---> 11110000
11110000 ---> 0000
...

Test 23

Group: 2

Verdict:

input
1001101100

correct output
4
1 1 1 1 

user output
1001101100 ---> 1001101100
1001101100 ---> 11101100
11101100 ---> 01100
01100 ---> 000
4
...

Test 24

Group: 2

Verdict:

input
0000000111

correct output
2
1 1 

user output
0000000111 ---> 0000000111
0000000111 ---> 111
2
1 1

Test 25

Group: 2

Verdict:

input
0011111110

correct output
2
2 1 

user output
0011111110 ---> 0011111110
0011111110 ---> 11111110
11111110 ---> 0
0011111110 ---> 000
2
...

Test 26

Group: 2

Verdict:

input
1100101100

correct output
4
2 1 1 1 

user output
1100101100 ---> 1100101100
1100101100 ---> 00101100
00101100 ---> 101100
101100 ---> 1000
00101100 ---> 001000
...

Test 27

Group: 2

Verdict:

input
0111101110

correct output
3
2 1 1 

user output
0111101110 ---> 0111101110
0111101110 ---> 001110
001110 ---> 1110
1110 ---> 0
001110 ---> 000
...

Test 28

Group: 2

Verdict:

input
0000011011

correct output
3
2 1 1 

user output
0000011011 ---> 0000011011
0000011011 ---> 11011
11011 ---> 011
0000011011 ---> 00000011
00000011 ---> 11
...

Test 29

Group: 2

Verdict:

input
1110011101

correct output
3
3 2 1 

user output
1110011101 ---> 1110011101
1110011101 ---> 0011101
0011101 ---> 11101
11101 ---> 01
0011101 ---> 0001
...

Test 30

Group: 2

Verdict:

input
0001011011

correct output
4
1 1 1 1 

user output
0001011011 ---> 0001011011
0001011011 ---> 1011011
1011011 ---> 10011
10011 ---> 111
4
...

Test 31

Group: 2

Verdict:

input
0010110011

correct output
4
1 1 1 1 

user output
0010110011 ---> 0010110011
0010110011 ---> 10110011
10110011 ---> 100011
100011 ---> 111
4
...

Test 32

Group: 2

Verdict:

input
0011100000

correct output
2
2 1 

user output
0011100000 ---> 0011100000
0011100000 ---> 11100000
11100000 ---> 00000
3
1 1 1

Test 33

Group: 2

Verdict:

input
1110100110

correct output
4
1 1 1 1 

user output
1110100110 ---> 1110100110
1110100110 ---> 0100110
0100110 ---> 01110
01110 ---> 00
4
...

Test 34

Group: 2

Verdict:

input
0110110111

correct output
4
2 1 1 1 

user output
0110110111 ---> 0110110111
0110110111 ---> 00110111
00110111 ---> 110111
110111 ---> 0111
00110111 ---> 000111
...

Test 35

Group: 2

Verdict:

input
1110110010

correct output
4
1 2 1 1 

user output
1110110010 ---> 1110110010
1110110010 ---> 0110010
0110010 ---> 00010
00010 ---> 10
0110010 ---> 01110
...

Test 36

Group: 2

Verdict:

input
110011001100110011001010101010...

correct output
QAQ

user output
(empty)

Test 37

Group: 2

Verdict:

input
110011001100110011001100101010...

correct output
QAQ

user output
(empty)

Test 38

Group: 2

Verdict:

input
110011001100110011001100110011...

correct output
31
1 20 20 20 20 20 20 20 20 20 2...

user output
(empty)

Test 39

Group: 2

Verdict:

input
010101010101010101010101010101...

correct output
48
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
010101010101010101010101010101...

Test 40

Group: 2

Verdict:

input
011010000011111011110000110011...

correct output
23
13 13 12 11 11 11 11 10 9 9 9 ...

user output
011010000011111011110000110011...

Test 41

Group: 3

Verdict:

input
0010101000

correct output
QAQ

user output
0010101000 ---> 0010101000
0010101000 ---> 10101000
QAQ

Test 42

Group: 3

Verdict:

input
0100010110

correct output
4
2 1 1 1 

user output
0100010110 ---> 0100010110
0100010110 ---> 0110110
0110110 ---> 00110
00110 ---> 110
110 ---> 0
...

Test 43

Group: 3

Verdict:

input
0100110110

correct output
4
2 1 1 1 

user output
0100110110 ---> 0100110110
0100110110 ---> 01110110
01110110 ---> 00110
00110 ---> 110
110 ---> 0
...

Test 44

Group: 3

Verdict:

input
1110000001

correct output
2
2 1 

user output
1110000001 ---> 1110000001
1110000001 ---> 0000001
0000001 ---> 1
1110000001 ---> 1111
2
...

Test 45

Group: 3

Verdict:

input
0001001110

correct output
3
2 2 1 

user output
0001001110 ---> 0001001110
0001001110 ---> 1001110
1001110 ---> 11110
11110 ---> 0
1001110 ---> 1000
...

Test 46

Group: 3

Verdict:

input
0011100011

correct output
3
1 2 1 

user output
0011100011 ---> 0011100011
0011100011 ---> 11100011
11100011 ---> 00011
00011 ---> 11
4
...

Test 47

Group: 3

Verdict:

input
0100111100

correct output
3
1 1 1 

user output
0100111100 ---> 0100111100
0100111100 ---> 01111100
01111100 ---> 000
3
1 1 1

Test 48

Group: 3

Verdict:

input
0001001000

correct output
3
2 2 1 

user output
0001001000 ---> 0001001000
0001001000 ---> 1001000
1001000 ---> 11000
11000 ---> 000
4
...

Test 49

Group: 3

Verdict:

input
0100100010

correct output
4
2 1 1 1 

user output
0100100010 ---> 0100100010
0100100010 ---> 01100010
01100010 ---> 000010
000010 ---> 10
01100010 ---> 01110
...

Test 50

Group: 3

Verdict:

input
1100101110

correct output
4
2 1 1 1 

user output
1100101110 ---> 1100101110
1100101110 ---> 00101110
00101110 ---> 101110
101110 ---> 100
00101110 ---> 00100
...

Test 51

Group: 3

Verdict:

input
1000111011

correct output
3
2 1 1 

user output
1000111011 ---> 1000111011
1000111011 ---> 1111011
1111011 ---> 011
1000111011 ---> 1000011
1000011 ---> 111
...

Test 52

Group: 3

Verdict:

input
1000111111

correct output
2
1 1 

user output
1000111111 ---> 1000111111
1000111111 ---> 1111111
2
1 1

Test 53

Group: 3

Verdict:

input
0110011100

correct output
3
2 1 1 

user output
0110011100 ---> 0110011100
0110011100 ---> 00011100
00011100 ---> 11100
11100 ---> 00
4
...

Test 54

Group: 3

Verdict:

input
0001000110

correct output
3
2 2 1 

user output
0001000110 ---> 0001000110
0001000110 ---> 1000110
1000110 ---> 1110
1110 ---> 0
1000110 ---> 10000
...

Test 55

Group: 3

Verdict:

input
1110110010

correct output
4
1 2 1 1 

user output
1110110010 ---> 1110110010
1110110010 ---> 0110010
0110010 ---> 00010
00010 ---> 10
0110010 ---> 01110
...

Test 56

Group: 3

Verdict:

input
110011001100110011001100110011...

correct output
QAQ

user output
(empty)

Test 57

Group: 3

Verdict:

input
110011001100110011001100110011...

correct output
QAQ

user output
(empty)

Test 58

Group: 3

Verdict:

input
110011001100110011001100110011...

correct output
1501
1 1000 1000 1000 1000 1000 100...

user output
(empty)

Test 59

Group: 3

Verdict:

input
010101010101010101010101010101...

correct output
2498
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
(empty)

Test 60

Group: 3

Verdict:

input
011100011001011111111000010110...

correct output
1272
1 1 648 647 646 646 645 645 64...

user output
011100011001011111111000010110...

Test 61

Group: 4

Verdict:

input
1110101110

correct output
QAQ

user output
1110101110 ---> 1110101110
1110101110 ---> 0101110
0101110 ---> 0100
1110101110 ---> 1110100
1110100 ---> 0100
...

Test 62

Group: 4

Verdict:

input
0111001011

correct output
4
2 1 1 1 

user output
0111001011 ---> 0111001011
0111001011 ---> 0001011
0001011 ---> 1011
0111001011 ---> 01111011
01111011 ---> 0011
...

Test 63

Group: 4

Verdict:

input
1101111101

correct output
3
2 2 1 

user output
1101111101 ---> 1101111101
1101111101 ---> 01111101
01111101 ---> 001
001 ---> 1
1101111101 ---> 11001
...

Test 64

Group: 4

Verdict:

input
1001110001

correct output
3
2 1 1 

user output
1001110001 ---> 1001110001
1001110001 ---> 11110001
11110001 ---> 0001
0001 ---> 1
11110001 ---> 11111
...

Test 65

Group: 4

Verdict:

input
1000000011

correct output
2
1 1 

user output
1000000011 ---> 1000000011
1000000011 ---> 111
2
1 1

Test 66

Group: 4

Verdict:

input
0100010111

correct output
4
1 1 1 1 

user output
0100010111 ---> 0100010111
0100010111 ---> 0110111
0110111 ---> 00111
00111 ---> 111
4
...

Test 67

Group: 4

Verdict:

input
0100111010

correct output
4
2 1 1 1 

user output
0100111010 ---> 0100111010
0100111010 ---> 01111010
01111010 ---> 0010
0010 ---> 10
0100111010 ---> 0100010
...

Test 68

Group: 4

Verdict:

input
0010111101

correct output
4
1 1 1 1 

user output
0010111101 ---> 0010111101
0010111101 ---> 10111101
10111101 ---> 1001
1001 ---> 11
4
...

Test 69

Group: 4

Verdict:

input
0011111000

correct output
2
2 1 

user output
0011111000 ---> 0011111000
0011111000 ---> 11111000
11111000 ---> 000
3
1 1 1

Test 70

Group: 4

Verdict:

input
1101001101

correct output
4
2 2 2 1 

user output
1101001101 ---> 1101001101
1101001101 ---> 01001101
01001101 ---> 011101
011101 ---> 001
001 ---> 1
...

Test 71

Group: 4

Verdict:

input
0110111000

correct output
3
2 1 1 

user output
0110111000 ---> 0110111000
0110111000 ---> 00111000
00111000 ---> 111000
111000 ---> 000
4
...

Test 72

Group: 4

Verdict:

input
1100110111

correct output
3
3 2 1 

user output
1100110111 ---> 1100110111
1100110111 ---> 00110111
00110111 ---> 110111
110111 ---> 0111
00110111 ---> 000111
...

Test 73

Group: 4

Verdict:

input
1110011111

correct output
2
2 1 

user output
1110011111 ---> 1110011111
1110011111 ---> 0011111
0011111 ---> 11111
3
1 1 1

Test 74

Group: 4

Verdict:

input
1011000101

correct output
4
2 1 1 1 

user output
1011000101 ---> 1011000101
1011000101 ---> 10000101
10000101 ---> 1101
1101 ---> 01
1011000101 ---> 1011101
...

Test 75

Group: 4

Verdict:

input
1110110010

correct output
4
1 2 1 1 

user output
1110110010 ---> 1110110010
1110110010 ---> 0110010
0110010 ---> 00010
00010 ---> 10
0110010 ---> 01110
...

Test 76

Group: 4

Verdict:

input
110011001100110011001100110011...

correct output
QAQ

user output
(empty)

Test 77

Group: 4

Verdict:

input
110011001100110011001100110011...

correct output
QAQ

user output
(empty)

Test 78

Group: 4

Verdict:

input
110011001100110011001100110011...

correct output
30001
1 20000 20000 20000 20000 2000...

user output
(empty)

Test 79

Group: 4

Verdict:

input
010101010101010101010101010101...

correct output
49998
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
(empty)

Test 80

Group: 4

Verdict:

input
111000110000011000001101010010...

correct output
25011
1 12471 12470 12469 12468 1246...

user output
(empty)