| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 46 | 17 | 16 | 36.364% |
You think it would be funny to prank your best friend by placing them on cell $(0, 0)$ of an infinite grid of coloured cells. The friend then moves around the grid indefinitely, one step at a time, always moving to one of the four adjacent cells.
$N$ of the cells on the grid contain a portal. Once your friend steps on a portal, they instantly teleport to a random portal (which might be the one they just stepped on, or might be a different one). If there is a portal at the cell $(0, 0),ドル your friend is also teleported at the start when they get placed on the grid.
As part of the prank, you want to trick your friend into not noticing that there are portals at all. The only thing your friend sees is the colour of the cell they are currently at, so you should make sure that from your friend's perspective the colours of the tiles never change. In particular, if your friend thinks they have entered a cell more than once (for example by moving left and then immediately right), they should see the same color as the first time they think they entered the cell.
Note: when your friend steps on a portal, they will see both the colour of the cell they step on, and the one they are teleported to. You will therefore need to colour all portal cells the same colour to avoid teleportations being immediately obvious.
A simple solution would be to colour all cells the same colour. But colours are nice! So you would like to use as many colours as you can.
Let's consider an example where the portals are placed at cells $(1, 1),ドル $(1, 3)$ and $(3, 2),ドル and your friend makes the following sequence of moves: up, right, down, left.
After the sequence of moves the friend thinks that they're back at the starting cell $(0, 0),ドル but in reality they might also end up in $(0, 2)$ or $(2, 1)$. They already saw the colour of cell $(0, 0)$ at the beginning, so if they see a different colour now, they will realise there must be portals. We don't want that to happen, so we must choose the same colour for these 3ドル$ cells.
There is no sequence of moves where your friend would think that they end up on cell $(0, 0)$ when they actually end up on $(1, 0),ドル so these cells can be safely coloured with different colours.
Below you can see a colouring with 4ドル$ colours for the example above. It is not possible to use more than 4ドル$ colours for this example.
Let's consider a different example with portals at cells $(0, 0),ドル $(0, 1),ドル $(1, 0),ドル $(0,-1)$ and $(-1, 0)$. Say your friend tries to reach cell $(1, 3)$ by going right once and then up 3ドル$ times. One possibility is that they end up at cell $(0, 0)$ if they got teleported there at the start and after each step. If your friend now backtracks to what they think is cell $(0, 0)$ by going down 3ドル$ times and left once, and doesn't get teleported away from their current cell while doing so, they will end up at $(-1,-3)$. Your friend will think that they are at cell $(0, 0)$ for the second time, and will expect to see the same colour. So you need to colour $(-1,-3)$ and $(0, 0)$ with the same colour.
Note that there was nothing special about our initial choice of cell $(1, 3)$. You can similarly show that other cells have to share a colour with $(0, 0)$.
Calculate the maximum number of colours you can use while making sure that your friend won't notice the existence of portals.
The first line contains the integer $N$ – the number of portals.
The next $N$ lines contain two integers each. The $i$-th of these lines contains $x_i$ and $y_i,ドル indicating that there is a portal at cell $(x_i , y_i )$.
Print a single integer – the maximum number of colours that can be used without your friend noticing the portals, or $-1$ if you can use an infinite number of colours.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 1 | $N ≤ 2$. |
| 2 | 10 | $N ≤ 3$. |
| 3 | 10 | For all integers $x_1,ドル $x_2,ドル $y_1,ドル $y_2$ : if there are portals at the locations $(x_1 , y_1 )$ and $(x_2 , y_2 ),ドル then there is also a portal at the location $(x_1 , y_2 )$. |
| 4 | 29 | $N ≤ 100$ and $-100 ≤ x_i , y_i ≤ 100$ for all 1ドル ≤ i ≤ N$. |
| 5 | 15 | $N ≤ 2000$. |
| 6 | 35 | No additional contraints. |
3 1 1 1 3 3 2
4
5 0 0 1 0 -1 0 0 1 0 -1
1
1 1 -1
-1