Find the Parts

시간 제한4초메모리 제한2048 MB

요약

무작위 잡음으로 이루어진 r x c 흑백 이미지를 400 KiB 메모리만 남기고 지운 뒤에도, 작은 사각형 조각의 위치를 정확히 답하는 방법을 설계한다.

난이도: 보통10점 중 6점
유형: 해시맵, 구현, 확률, 수학
정답자: 아직 제출이 없습니다

문제

Two robots, Carl and Clara, are a part of a secret network designed to pass messages.

Robot Clara has got a secret message. The message has a form of a black-and-white rectangle of $r$ rows and $c$ columns which contains $r \times c$ pixels. Each pixel is characterized by brightness: an integer from $0$ to $255$ (a byte) where $0$ is black, $255$ is white, and the numbers in between correspond to different shades of gray.

Clara does not know whether the message has some hidden meaning, but it definitely looks like "white noise": each pixel can be considered to have a random value which is independent from other pixels and uniformly distributed among the $256$ possible colors.

Clara's job is to answer questions by robot Carl. Each question is formulated as a small black-and-white rectangle. The answer is the coordinates of that rectangle in the original message.

However, before answering questions, Clara has to delete the message. Unfortunately, her memory is limited to a mere $400$ kibibytes, so the message may not fit there...

How should Clara act to nevertheless answer all the questions correctly?

예제2

예제 1

입력

message
20 24
33 39 73 4A 5A AA E0 86 96 4B 0B 83 A0 FA 82 9B B0 6E DC 03 1C B9 5B 81
86 3E 23 7B C9 38 77 82 7D 62 EA CE A8 DE 85 6C 36 B3 10 EE 85 6A D5 92
14 BD 58 74 20 7B 36 E1 89 B8 6F 4A F4 8F 17 2E 2F 0F 79 DD AA 9F 6F AD
85 21 B6 2F 58 37 87 7B 3F EE D9 7D 9A E6 AA 12 E0 B6 BB 3D 72 BD 34 A5
E5 8A 73 EE 69 BF E0 0D 5C 57 EF 42 7B 91 07 B8 7D A9 40 0D 4B 52 2D BC
25 F7 4F A7 18 4D 76 EB EB 3E AA 3D C2 19 D3 EE 77 BF C1 38 FF C4 07 C0
CD 2B 79 C3 27 A6 C6 DB D3 17 EA CD 74 BC E5 42 36 F8 D2 86 F9 E9 86 AA
F8 37 39 BF 0C B6 2C 9A F5 04 40 BB D8 FD B4 97 2A 9A A6 D1 9E 2A 60 23
F7 CF 3F 25 CB C1 25 08 0F 1F D2 34 C4 61 27 2E 7B E9 00 FD 86 77 E9 AF
7B 44 57 2E 47 F9 CC A0 03 E3 60 C2 DF C1 F5 6C 59 0E 99 64 3D 7D E7 75
EC C9 BE 91 3B DF 1C DC 61 5C 66 1C B3 26 1C 2E 11 0D 19 BD DC 08 1A 90
BF 93 A0 B9 CD 02 DD E6 49 6F 53 E2 2C 34 10 EA 1A 44 B4 49 7E D5 B6 CB
4A E9 C7 3F F1 FF 24 33 5D 8F D4 26 2E C4 FD 81 FB 96 36 51 F1 38 BE 1E
5A C9 B2 3D 06 99 4F 99 3F 45 DB DA 14 BE 53 D7 B2 2D 64 7B 10 74 0E 70
B6 07 1A B4 F3 25 4D EB 3F 68 72 10 3B 56 F2 A7 C4 A4 28 AE 16 D0 13 CC
91 C4 4D 51 04 39 A8 13 3C 1F 00 57 24 2A FD EA FC EB 77 B8 E1 7D DF 0D
92 51 DA 2A CD A1 F3 97 1A 7A EF 41 DF BD 16 4D 05 4B 78 20 B7 68 38 1C
10 D5 DE 39 58 8F F6 22 8B E8 E8 D0 FB 37 31 33 9E C8 FC 79 62 4F BB 96
5F 04 CB 93 16 9F 15 07 96 27 35 09 AB 79 92 37 44 15 14 A1 4E 04 67 5D
C1 C4 8B 1A 77 E1 D2 4D 06 42 07 A3 1A 67 EC F1 B2 08 96 F6 C3 4E 79 E9

예상 출력

484
14 00 18 00 33 39 73 4A 5A AA E0 86 96 4B 0B 83 A0 FA 82 9B B0 6E DC 03 1C B9 5B 81 86 3E 23 7B C9 38 77 82 7D 62 EA CE A8 DE 85 6C 36 B3 10 EE 85 6A D5 92 14 BD 58 74 20 7B 36 E1 89 B8 6F 4A F4 8F 17 2E 2F 0F 79 DD AA 9F 6F AD 85 21 B6 2F 58 37 87 7B 3F EE D9 7D 9A E6 AA 12 E0 B6 BB 3D 72 BD 34 A5 E5 8A 73 EE 69 BF E0 0D 5C 57 EF 42 7B 91 07 B8 7D A9 40 0D 4B 52 2D BC 25 F7 4F A7 18 4D 76 EB EB 3E AA 3D C2 19 D3 EE 77 BF C1 38 FF C4 07 C0 CD 2B 79 C3 27 A6 C6 DB D3 17 EA CD 74 BC E5 42 36 F8 D2 86 F9 E9 86 AA F8 37 39 BF 0C B6 2C 9A F5 04 40 BB D8 FD B4 97 2A 9A A6 D1 9E 2A 60 23 F7 CF 3F 25 CB C1 25 08 0F 1F D2 34 C4 61 27 2E 7B E9 00 FD 86 77 E9 AF 7B 44 57 2E 47 F9 CC A0 03 E3 60 C2 DF C1 F5 6C 59 0E 99 64 3D 7D E7 75 EC C9 BE 91 3B DF 1C DC 61 5C 66 1C B3 26 1C 2E 11 0D 19 BD DC 08 1A 90 BF 93 A0 B9 CD 02 DD E6 49 6F 53 E2 2C 34 10 EA 1A 44 B4 49 7E D5 B6 CB 4A E9 C7 3F F1 FF 24 33 5D 8F D4 26 2E C4 FD 81 FB 96 36 51 F1 38 BE 1E 5A C9 B2 3D 06 99 4F 99 3F 45 DB DA 14 BE 53 D7 B2 2D 64 7B 10 74 0E 70 B6 07 1A B4 F3 25 4D EB 3F 68 72 10 3B 56 F2 A7 C4 A4 28 AE 16 D0 13 CC 91 C4 4D 51 04 39 A8 13 3C 1F 00 57 24 2A FD EA FC EB 77 B8 E1 7D DF 0D 92 51 DA 2A CD A1 F3 97 1A 7A EF 41 DF BD 16 4D 05 4B 78 20 B7 68 38 1C 10 D5 DE 39 58 8F F6 22 8B E8 E8 D0 FB 37 31 33 9E C8 FC 79 62 4F BB 96 5F 04 CB 93 16 9F 15 07 96 27 35 09 AB 79 92 37 44 15 14 A1 4E 04 67 5D C1 C4 8B 1A 77 E1 D2 4D 06 42 07 A3 1A 67 EC F1 B2 08 96 F6 C3 4E 79 E9

예제 2

입력

parts
484
14 00 18 00 33 39 73 4A 5A AA E0 86 96 4B 0B 83 A0 FA 82 9B B0 6E DC 03 1C B9 5B 81 86 3E 23 7B C9 38 77 82 7D 62 EA CE A8 DE 85 6C 36 B3 10 EE 85 6A D5 92 14 BD 58 74 20 7B 36 E1 89 B8 6F 4A F4 8F 17 2E 2F 0F 79 DD AA 9F 6F AD 85 21 B6 2F 58 37 87 7B 3F EE D9 7D 9A E6 AA 12 E0 B6 BB 3D 72 BD 34 A5 E5 8A 73 EE 69 BF E0 0D 5C 57 EF 42 7B 91 07 B8 7D A9 40 0D 4B 52 2D BC 25 F7 4F A7 18 4D 76 EB EB 3E AA 3D C2 19 D3 EE 77 BF C1 38 FF C4 07 C0 CD 2B 79 C3 27 A6 C6 DB D3 17 EA CD 74 BC E5 42 36 F8 D2 86 F9 E9 86 AA F8 37 39 BF 0C B6 2C 9A F5 04 40 BB D8 FD B4 97 2A 9A A6 D1 9E 2A 60 23 F7 CF 3F 25 CB C1 25 08 0F 1F D2 34 C4 61 27 2E 7B E9 00 FD 86 77 E9 AF 7B 44 57 2E 47 F9 CC A0 03 E3 60 C2 DF C1 F5 6C 59 0E 99 64 3D 7D E7 75 EC C9 BE 91 3B DF 1C DC 61 5C 66 1C B3 26 1C 2E 11 0D 19 BD DC 08 1A 90 BF 93 A0 B9 CD 02 DD E6 49 6F 53 E2 2C 34 10 EA 1A 44 B4 49 7E D5 B6 CB 4A E9 C7 3F F1 FF 24 33 5D 8F D4 26 2E C4 FD 81 FB 96 36 51 F1 38 BE 1E 5A C9 B2 3D 06 99 4F 99 3F 45 DB DA 14 BE 53 D7 B2 2D 64 7B 10 74 0E 70 B6 07 1A B4 F3 25 4D EB 3F 68 72 10 3B 56 F2 A7 C4 A4 28 AE 16 D0 13 CC 91 C4 4D 51 04 39 A8 13 3C 1F 00 57 24 2A FD EA FC EB 77 B8 E1 7D DF 0D 92 51 DA 2A CD A1 F3 97 1A 7A EF 41 DF BD 16 4D 05 4B 78 20 B7 68 38 1C 10 D5 DE 39 58 8F F6 22 8B E8 E8 D0 FB 37 31 33 9E C8 FC 79 62 4F BB 96 5F 04 CB 93 16 9F 15 07 96 27 35 09 AB 79 92 37 44 15 14 A1 4E 04 67 5D C1 C4 8B 1A 77 E1 D2 4D 06 42 07 A3 1A 67 EC F1 B2 08 96 F6 C3 4E 79 E9
2
10 10
39 73 4A 5A AA E0 86 96 4B 0B
3E 23 7B C9 38 77 82 7D 62 EA
BD 58 74 20 7B 36 E1 89 B8 6F
21 B6 2F 58 37 87 7B 3F EE D9
8A 73 EE 69 BF E0 0D 5C 57 EF
F7 4F A7 18 4D 76 EB EB 3E AA
2B 79 C3 27 A6 C6 DB D3 17 EA
37 39 BF 0C B6 2C 9A F5 04 40
CF 3F 25 CB C1 25 08 0F 1F D2
44 57 2E 47 F9 CC A0 03 E3 60
11 20
18 4D 76 EB EB 3E AA 3D C2 19 D3 EE 77 BF C1 38 FF C4 07 C0
27 A6 C6 DB D3 17 EA CD 74 BC E5 42 36 F8 D2 86 F9 E9 86 AA
0C B6 2C 9A F5 04 40 BB D8 FD B4 97 2A 9A A6 D1 9E 2A 60 23
CB C1 25 08 0F 1F D2 34 C4 61 27 2E 7B E9 00 FD 86 77 E9 AF
47 F9 CC A0 03 E3 60 C2 DF C1 F5 6C 59 0E 99 64 3D 7D E7 75
3B DF 1C DC 61 5C 66 1C B3 26 1C 2E 11 0D 19 BD DC 08 1A 90
CD 02 DD E6 49 6F 53 E2 2C 34 10 EA 1A 44 B4 49 7E D5 B6 CB
F1 FF 24 33 5D 8F D4 26 2E C4 FD 81 FB 96 36 51 F1 38 BE 1E
06 99 4F 99 3F 45 DB DA 14 BE 53 D7 B2 2D 64 7B 10 74 0E 70
F3 25 4D EB 3F 68 72 10 3B 56 F2 A7 C4 A4 28 AE 16 D0 13 CC
04 39 A8 13 3C 1F 00 57 24 2A FD EA FC EB 77 B8 E1 7D DF 0D

예상 출력

1 2
6 5