Existem muitos tipos diferentes de conjuntos de trens, desde trilhos de madeira como o Brio, até controle totalmente digital, perfeitas réplicas metálicas minúsculas de trens reais, mas todos exigem que um trilho seja projetado, idealmente, usando o máximo possível de suas peças.
Portanto, sua tarefa é determinar se, dada a entrada das peças disponíveis, é possível construir um circuito fechado completo usando todos os elementos e, caso contrário, quantas peças serão deixadas no circuito máximo possível.
Como este é um conjunto de trens simplificado, existem apenas 3 elementos: curva grande, pequena curva e reta. Tudo isso é baseado em uma grade quadrada:
- "Big Curve" é um canto de 90 graus, cobrindo 2 unidades em cada dimensão
- "Little Curve" é um canto de 90 graus, cobrindo uma unidade em cada direção
- "Reto" é um elemento reto, com 1 unidade de comprimento
Isso significa que o circuito mínimo possível é formado por 4 pequenas curvas - é um círculo, com raio de 1 unidade. Isso pode ser estendido adicionando pares de elementos retos para formar várias formas ovais. Existem outros circuitos possíveis adicionando mais curvas ou misturando os tipos de curva.
Este conjunto de trens não inclui junções ou métodos para cruzar as faixas, portanto, não é válido que dois elementos se conectem à mesma extremidade de um outro elemento (sem formações Y) ou cruzem entre si (sem formações X) . Além disso, é um conjunto de trens, portanto, qualquer formação que não permita a passagem de um trem não é válida: exemplos incluem retas que se encontram em ângulos de 90 graus (sempre deve haver uma curva entre retas perpendiculares) e curvas que se encontram em ângulos de 90 graus (as curvas devem fluir).
Você também deseja usar o maior número possível de peças, ignorando que tipo elas são, para sempre optar por um circuito com mais bits. Finalmente, você só tem um trem; portanto, qualquer solução que resulte em múltiplos circuitos é inaceitável. .
Entrada
Uma matriz de três números inteiros, todos maiores ou iguais a 0, correspondendo ao número de curvas grandes, pequenas curvas e retas disponíveis ou parâmetros passados para o seu programa, na mesma ordem.
Saída
Um número correspondente ao número de peças restantes quando o circuito máximo possível para os elementos fornecidos é construído.
Dados de teste
Minimal circuit using big curves
Input: [4,0,0]
Output: 0
Slightly more complicated circuit
Input: [3,1,2]
Output: 0
Incomplete circuit - can't join
Input: [3,0,0]
Output: 3
Incomplete circuit - can't join
Input: [3,1,1]
Output: 5
Circuit where big curves share a centre
Input: [2,2,0]
Output: 0
Bigger circuit
Input: [2,6,4]
Output: 0
Circuit where both concave and convex curves required
Input: [8,0,0] or [0,8,0]
Output: 0
Circuit with left over bit
Input: [5,0,0] or [0,5,0]
Output: 1
Notas
- 2 retas e uma pequena curva são equivalentes a uma grande curva, mas usam mais peças, portanto são preferidas - nunca deve ser uma situação em que essa combinação é deixada, se houver grandes curvas no circuito
- Normalmente, 4 pequenas curvas podem ser trocadas por 4 retas, mas não se isso fizer com que o circuito se cruze
- O conjunto de trens também é idealizado - os elementos da pista ocupam as larguras mostradas, portanto, é válido que as curvas passem por um único quadrado da grade sem interseção, em alguns casos. A grade apenas define as dimensões do elemento. Em particular, duas grandes curvas podem ser colocadas de modo que o quadrado da grade no canto superior esquerdo do diagrama de exemplo também seja o quadrado inferior direito de outra grande curva que corre da esquerda para cima (com o diagrama mostrando uma que funciona da direita para a parte inferior)
- Uma pequena curva pode caber no espaço vazio sob uma grande curva (quadrado da grade inferior direito acima). Uma segunda grande curva também poderia usar esse espaço, deslocando uma transversal e outra abaixo da primeira
- Uma curva pequena não pode caber no mesmo espaço da grade do lado de fora de uma grande curva - principalmente porque não há como conectar-se a ela que não se cruze ilegalmente
[5,0,0]
ou[0,5,0]
seria1
. Isso está correto? Você poderia adicionar um caso de teste?[8,0,0]
, com dois elementos 2x2 sobrepostos no centro da grade?