29927번 - Värvide segamine 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.2 초 | 1024 MB | 9 | 1 | 1 | 25.000% |
문제
Ehituspoes on masin, mis oskab punasest, rohelisest ja sinisest värvist (nimetame neid edaspidi põhivärvideks) segada kokku erinevaid värvitoone. Iga värvitoon, mida masin oskab kokku segada, on antud RGB-koodiga, mis näitab, kui palju mingit põhivärvi kulub. Kood on esitatud kolme 16-bitise arvuga. Ostjad soovivad saada mingeid spetsiifilisi värvitoone, mis on samuti antud oma RGB-koodidega. Masin aga ei pruugi osata teha täpselt nõutud tooni ning valib seetõttu lähima võimaliku vaste. "Lähedust" mõõdetakse 3D Manhattani kaugusega värviruumis. Näiteks värvitoonide "100 50 0" ja "20 25 10" vaheline kaugus on vastavate põhivärvide omavaheliste kauguste summa ehk $|100-20|+|50-25|+|0-10|=115$. Mõnel päeval on aga masinal mõni põhivärvidest (punane, roheline või sinine) hoopiski otsas. Sellisel juhul esitavad ostjad ka vaid selliseid soove, kus seda põhivärvi vaja ei ole. Masina konstrueerimisel on arvestatud, et võimalikud toonid oleksid värviruumis võimalikult ühtlaselt esindatud --- seetõttu võib eeldada, et võimalikud toonid on enam-vähem juhuslikud ja esindatud võrdse tõenäosusega. Kõik toonid, mida masin oskab teha, on omavahel erinevad, aga klientide soovid võivad kattuda.
입력
Tekstifaili esimesel real on värvitoonide arv $1 \le N \le 100\,000$, mida masin oskab teha, ning soovide arv $1 \le Q \le 100\,000$, mida masinalt küsitakse. Järgmisel $N + Q$ real on igaühel 3 täisarvu lõigust $0 \ldots 65535$ ehk värvide RGB-koodid. Neist esimesel $N$ real on masinas segatavate värvitoonide koodid ja viimasel $Q$ real on ostjate soovitud värvide RGB-koodid.
출력
Tekstifaili väljastada $Q$ rida, igale reale üks täisarv: iga ostja soovitud värvi kohta sellele lähima värvi number, mida masin segada oskab. Masina segatavad värvid on nummerdatud $0 \ldots N-1$ sisendis toodud järjekorras. Kui kaks värvi on samal kaugusel, väljastada väiksema numbriga värv.
예제 입력 1
3 3 200 0 0 8 0 0 100 0 0 8 0 0 300 0 0 150 0 0
예제 출력 1
1 0 0
Masinas on ainult punast värvi ja küsitakse ka ainult erineva tumedusega punaseid. Esimesele soovile vastavat värvi oskab masin teha, kaugus on 0 ja vastava värvi number 1. Teisele soovile vastavat värvi ei ole, kuid kõige lähemal on masina värv numbriga 0 ("200 0 0"). Kolmandast soovist sama kaugel (50) on nii värv numbriga 0 kui ka värv numbriga 2. Kuna esimene neist on väiksema numbriga, segab masin selle värvi.
예제 입력 2
3 3 75 25 0 100 100 0 150 50 0 100 50 0 50 100 0 200 30 0
예제 출력 2
0 1 2
Masinas on ainult punast ja rohelist värvi. Esimesest soovist samal kaugusel (50) on kõik kolm masina poolt segatavat värvi. Masina värvide kaugused teisest soovist on vastavalt 100, 50 ja 150. Masina värvide kaugused kolmandast soovist on vastavalt 130, 170 ja 120.
예제 입력 3
4 3 5 5 5 200 200 200 150 10 10 0 0 255 0 0 0 10 10 200 175 105 105
예제 출력 3
0 3 1
Masinas on kõiki põhivärve.
출처
Olympiad > Estonian Informatics Olympiad > 2019-20 > Final Round 5번