README
¶
--- Dia 15: Zona de Exclusão de Sinalizadores ---
Você sente o chão tremer novamente enquanto o sinal de socorro o leva a uma grande rede de túneis subterrâneos. Você não tem tempo para revistá-los todos, mas também não precisa: sua mochila contém um conjunto de sensores comandados que você imagina terem sido construídos originalmente para localizar Elfos perdidos.
Os sensores não são muito poderosos, mas tudo bem; seu dispositivo portátil indica que você está perto o suficiente da fonte do sinal de socorro para os usar. Você tira o sistema de sensores de emergência da mochila, aperta o botão grande no topo e os sensores disparam pelos túneis.
Uma vez que um sensor encontra um ponto que acha que lhe dará uma boa leitura, ele se fixa a uma superfície dura e começa a monitorar pelo sinalizador emissor de sinais mais próximo. Os sensores e os sinalizadores sempre estão em coordenadas de inteiros. Cada sensor conhece sua própria posição e pode determinar a posição de um sinalizador com precisão; no entanto, os sensores só conseguem emparelhar com o único sinalizador mais próximo do sensor conforme medido pela distância de Manhattan. (Nunca há um empate onde dois sinalizadores estejam à mesma distância de um sensor.)
Não demora muito para os sensores relatarem suas posições e sinalizadores mais próximos (sua entrada de quebra-cabeça). Por exemplo:
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3
Portanto, considere o sensor em 2,18; o sinalizador mais próximo está em -2,15. Para o sensor em 9,16, o sinalizador mais próximo dele está em 10,16.
Desenhando sensores como S e sinalizadores como B, o arranjo acima de sensores e sinalizadores se parece com isso:
1 1 2 2
0 5 0 5 0 5
0 ....S.......................
1 ......................S.....
2 ...............S............
3 ................SB..........
4 ............................
5 ............................
6 ............................
7 ..........S.......S.........
8 ............................
9 ............................
10 ....B.......................
11 ..S.........................
12 ............................
13 ............................
14 ..............S.......S.....
15 B...........................
16 ...........SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....
No entanto, este não é necessariamente um mapa completo de todos os sinalizadores na área. Como cada sensor identifica apenas seu sinalizador mais próximo, se um sensor detectar um sinalizador, você saberá que não há outros sinalizadores tão ou mais próximos desse sensor. Ainda pode haver sinalizadores que simplesmente não são os sinalizadores mais próximos de qualquer sensor. Considere o sensor em 8,7:
1 1 2 2
0 5 0 5 0 5
-2 ..........#.................
-1 .........###................
0 ....S...#####...............
1 .......#######........S.....
2 ......#########S............
3 .....###########SB..........
4 ....#############...........
5 ...###############..........
6 ..#################.........
7 .#########S#######S#........
8 ..#################.........
9 ...###############..........
10 ....B############...........
11 ..S..###########............
12 ......#########.............
13 .......#######..............
14 ........#####.S.......S.....
15 B........###................
16 ..........#SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....
O sinalizador mais próximo deste sensor está em 2,10, e assim você sabe que não há sinalizadores tão próximos nem mais próximos (em quaisquer posições marcadas com #).
Nenhum dos sinalizadores detectados parece estar produzindo o sinal de socorro, então você precisará calcular onde o sinalizador de socorro está através do cálculo de onde ele não está. Por enquanto, mantenha as coisas simples contando as posições onde um sinalizador não pode estar ao longo de apenas uma única linha.
Então, suponha que você tenha um arranjo de sinalizadores e sensores como no exemplo acima e, apenas na linha onde y=10, você gostaria de contar o número de posições que um sinalizador não pode existir. A cobertura de todos os sensores próximos a essa linha se parece com isso:
1 1 2 2
0 5 0 5 0 5
9 ...#########################...
10 ..####B######################..
11 .###S#############.###########.
Neste exemplo, na linha onde y=10, existem 26 posições onde um sinalizador não pode estar presente.
Consulte o relatório dos sensores que você acabou de lançar. Na linha onde y=2000000, quantas posições não podem conter um sinalizador?
--- Parte Dois ---
Seu dispositivo portátil indica que o sinal de socorro está vindo de um sinalizador próximo. O sinalizador de socorro não é detectado por nenhum sensor, mas o sinalizador deve ter as coordenadas x e y, cada uma não menor que 0 e não maior que 4000000.
Para isolar o sinal do sinalizador de emergência, você precisa determinar sua frequência de sintonia, que pode ser encontrada multiplicando sua coordenada x por 4000000 e adicionando sua coordenada y.
No exemplo acima, o espaço de busca é menor: em vez disso, as coordenadas x e y podem ser cada uma no máximo 20. Com esta área de busca reduzida, há apenas uma única posição que poderia ter um sinalizador: x=14, y=11. A frequência de sintonia para este sinalizador de socorro é 56000011.
Encontre a única posição possível para o sinalizador de socorro. Qual é a frequência de sintonia?
Documentation
Source Files