-
Notifications
You must be signed in to change notification settings - Fork 128
/
Main.java
executable file
·130 lines (89 loc) · 3.97 KB
/
Main.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
* Coração das Cartas
*
* Desafio:
* - Marcos decidiu abandonar o bar da faculdade onde jogava truco para dedicar-se ao
* mundo da programação. Para que isso fosse mais fácil, decidiu criar um novo jogo
* de cartas.
*
* - O coração das cartas, como Marcos apelidou o jogo, é individual e jogado com três
* pilhas, inicialmente com o mesmo número de cartas. Cada carta tem um valor numérico
* inteiro de 0 até 9. O jogador pode, a qualquer momento ver o valor de qualquer carta,
* mas só pode jogar com as cartas que estão no topo das pilhas. Em cada rodada, o jogador
* pode remover qualquer combinação de cartas que estejam no topo da pilha (pode escolher 1,
* 2 ou até 3 cartas) cuja soma dos valores seja múltiplo de 3. O jogo é ganho quando todas
* as cartas forem removidas das pilhas. Se alguma carta não puder ser removida, perde-se o
* jogo.
*
* Entrada:
* - A entrada é composta por várias instâncias Cada instância é iniciada por um inteiro N
* (0 ≤ N ≤ 100), que identifica o número de cartas em cada pilha. A entrada termina quando
* N = 0. Cada uma das N linhas seguintes contém três inteiros A, B e C, que descrevem os
* valores numéricos das cartas em um nível da pilha (0 ≤ A, B, C ≤ 9). As pilhas são
* descritas do topo até o fundo.
*
* Saída:
* - Para cada instância, imprima uma linha contendo o número 1 se o jogador pode ganhar a
* instância do jogo ou o número 0 se o jogo for impossível.
*/
import java.util.*;
public class Main {
static Map<String, Integer> m = new HashMap<String, Integer>();
static int n;
static int[][] pilha = new int[3][102];
static public boolean cartas(int a, int b, int c) {
String ss = "" + a + b + c;
if(a == b && b == c && c == n) {
m.putIfAbsent(ss, 1);
return true;
}
int x = m.getOrDefault(ss, 0);
if (x > 0) return (x == 1? true : false);
if(a < n && pilha[0][a]%3 == 0 && cartas(a + 1, b, c)) {
m.putIfAbsent(ss, 1);
return true;
}
if(b < n && pilha[1][b]%3 == 0 && cartas(a, b + 1, c)) {
m.putIfAbsent(ss, 1);
return true;
}
if(c < n && pilha[2][c]%3 == 0 && cartas(a, b, c + 1)) {
m.putIfAbsent(ss, 1);
return true;
}
if(a < n && b < n && (pilha[0][a]+pilha[1][b]) % 3 == 0 && cartas(a + 1, b + 1, c)) {
m.putIfAbsent(ss, 1);
return true;
}
if(a < n && c < n && (pilha[0][a]+pilha[2][c]) % 3 == 0 && cartas(a + 1, b, c + 1)) {
m.putIfAbsent(ss, 1);
return true;
}
if(b < n && c < n && (pilha[1][b]+pilha[2][c])%3 == 0 && cartas(a, b + 1, c + 1)) {
m.putIfAbsent(ss, 1);
return true;
}
if(a < n && b < n && c < n && (pilha[0][a]+pilha[1][b]+pilha[2][c]) % 3 == 0 && cartas(a + 1, b + 1, c + 1)) {
m.putIfAbsent(ss, 1);
return true;
}
m.putIfAbsent(ss, 2);
return false;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(true) {
n = Integer.parseInt(in.nextLine());
if (n == 0) break;
for (int i = 0 ; i < n; i++) {
StringTokenizer st = new StringTokenizer(in.nextLine());
pilha[0][i] = Integer.parseInt(st.nextToken());
pilha[1][i] = Integer.parseInt(st.nextToken());
pilha[2][i] = Integer.parseInt(st.nextToken());
}
if (cartas(0,0,0) == true) System.out.println("1");
else System.out.println("0");
m.clear();
}
}
}