Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Lýsing

Þú átt krúttlegan Bangboo sem tekur þátt í „Mikla ævintýri Marcels“.

Þessi Bangboo hreyfist í þrívíðu rúmi. Upphafspunktur hans er $(S_x, S_y, S_z)$ og áfangastaður hans er $(T_x, T_y, T_z)$. Líta má á hann sem einingartening með miðju í $(S_x, S_y, S_z)$. Það eru $n$ hindranir í þrívíða rúminu, og hver þeirra er einingarteningur með miðju í $(x_i, y_i, z_i)$. Tryggt er að hnit upphafspunktsins, áfangastaðarins og allra hindrana séu innbyrðis ólík, og að það verði að vera hindranir í $(S_x, S_y, S_z - 1)$ og $(T_x, T_y, T_z - 1)$.

Bangbooinn getur fjarflutt sig. Í hverju skrefi hefur hann $m$ tiltækar fjarflutningsaðferðir. Gerum ráð fyrir að hann sé núna í $(x, y, z)$. $i$-ta fjarflutningsaðferðin sendir hann í $(x + a_i, y + b_i, z + c_i)$, og eftir það fellur hann í frjálsu falli. Formlega mun hann fjarflytjast í $(x + a_i, y + b_i, d)$, þar sem $d$ er hæsta gildið sem uppfyllir $d \le z + c_i$ þannig að hindrun sé í $(x + a_i, y + b_i, d - 1)$. Ef hindrun er í $(x + a_i, y + b_i, z + c_i)$, eða ef ekkert slíkt $d$ er til, þá er ekki hægt að framkvæma þennan fjarflutning.

Markmið þitt er að láta Bangbooinn komast á áfangastaðinn frá upphafspunktinum í sem fæstum skrefum. Ef ómögulegt er að komast á áfangastaðinn, prentaðu $-1$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 500$), sem táknar fjölda prófunartilfella.

Fyrir hvert prófunartilfelli:

Fyrsta línan inniheldur tvær heiltölur $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), sem tákna fjölda hindrana og fjölda fjarflutningsaðferða sem Bangbooinn hefur, í sömu röð.

Önnur línan inniheldur sex heiltölur $S_x, S_y, S_z, T_x, T_y, T_z$ ($0 \le S_x, S_y, S_z, T_x, T_y, T_z \le 10^9$), sem tákna upphafspunkt og áfangastað Bangbooins.

Næstu $n$ línur innihalda hver um sig þrjár heiltölur $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), sem tákna hnit $i$-tu hindrunarinnar. Tryggt er að það verði að vera hindranir í $(S_x, S_y, S_z - 1)$ og $(T_x, T_y, T_z - 1)$.

Næstu $m$ línur innihalda hver um sig þrjár heiltölur $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), sem tákna $i$-tu fjarflutningsaðferðina.

Fyrir hvert prófunartilfelli er tryggt að öll hnit í inntakinu séu innbyrðis ólík, og að allar fjarflutningsaðferðir séu innbyrðis ólíkar.

Tryggt er að summa $n$ yfir öll prófunartilfelli fari ekki yfir $10^3$, og að summa $m$ yfir öll prófunartilfelli fari ekki yfir $10^3$.

Úttak

Fyrir hvert prófunartilfelli skal prenta eina heiltölu á einni línu, sem táknar lágmarksfjölda skrefa sem þarf til að komast á áfangastaðinn frá upphafspunktinum. Ef ómögulegt er að komast á áfangastaðinn, prentaðu $-1$.

Dæmi

Inntak 1

2
6 4
3 3 3 5 5 5
3 3 2
5 5 4
5 5 7
4 5 5
2 3 2
4 1 1
-1 0 3
2 -2 -1
1 4 9
1 0 0
3 2
0 0 1 1 1 1
0 0 0
1 1 0
1 1 2
1 1 1
1 1 2

Úttak 1

5
-1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.