Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Сипаттамасы

Сізде сүйкімді Банбу (Bangboo) бар, ол «Марсельдің үлкен шытырман оқиғасына» қатысып жатыр.

Бұл Банбу үш өлшемді кеңістікте қозғалады. Оның бастапқы нүктесі — $(S_x, S_y, S_z)$, ал соңғы нүктесі — $(T_x, T_y, T_z)$. Оны центрі $(S_x, S_y, S_z)$ нүктесінде орналасқан бірлік куб ретінде қарастыруға болады. Үш өлшемді кеңістікте $n$ кедергі бар, олардың әрқайсысы центрі $(x_i, y_i, z_i)$ нүктесінде орналасқан бірлік куб болып табылады. Бастапқы нүктенің, соңғы нүктенің және барлық кедергілердің координаттары қос-қостан әртүрлі екеніне, сондай-ақ $(S_x, S_y, S_z - 1)$ және $(T_x, T_y, T_z - 1)$ нүктелерінде міндетті түрде кедергілер болатынына кепілдік беріледі.

Банбу телепортация жасай алады. Әр қадамда оның таңдауға болатын $m$ телепортация тәсілі бар. Ол қазір $(x, y, z)$ нүктесінде тұр делік. $i$-ші телепортация тәсілі оны $(x + a_i, y + b_i, z + c_i)$ нүктесіне жібереді, содан кейін ол еркін құлайды. Формальды түрде ол $(x + a_i, y + b_i, d)$ нүктесіне телепортацияланады, мұндағы $d$ — $d \le z + c_i$ шартын қанағаттандыратын және $(x + a_i, y + b_i, d - 1)$ нүктесінде кедергі бар болатын ең үлкен мән. Егер $(x + a_i, y + b_i, z + c_i)$ нүктесінде кедергі болса немесе шартты қанағаттандыратын $d$ табылмаса, бұл телепортацияны орындау мүмкін емес.

Сіздің мақсатыңыз — Банбуды бастапқы нүктеден соңғы нүктеге ең аз қадам санымен жеткізу. Егер соңғы нүктеге жету мүмкін болмаса, $-1$ шығарыңыз.

Кіріс деректер

Бірінші жолда тест жағдайларының санын білдіретін бір бүтін $T$ саны берілген ($1 \le T \le 500$).

Әрбір тест жағдайы үшін:

Бірінші жолда кедергілер санын және Банбуға қолжетімді телепортация тәсілдерінің санын білдіретін екі бүтін сан $n, m$ берілген ($2 \le n \le 10^3$, $1 \le m \le 10^3$).

Екінші жолда Банбудың бастапқы және соңғы нүктелерін білдіретін алты бүтін сан $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$).

Келесі $n$ жолдың әрқайсысында $i$-ші кедергінің координаттарын білдіретін үш бүтін сан $x_i, y_i, z_i$ берілген ($0 \le x_i, y_i, z_i \le 10^9$). $(S_x, S_y, S_z - 1)$ және $(T_x, T_y, T_z - 1)$ нүктелерінде міндетті түрде кедергілер болатынына кепілдік беріледі.

Келесі $m$ жолдың әрқайсысында $i$-ші телепортация тәсілін білдіретін үш бүтін сан $a_i, b_i, c_i$ берілген ($|a_i|, |b_i|, |c_i| \le 10^9$).

Әрбір тест жағдайы үшін барлық кіріс координаттары қос-қостан әртүрлі және барлық телепортация тәсілдері қос-қостан әртүрлі екеніне кепілдік беріледі.

Барлық тест жағдайлары бойынша $n$ қосындысы $10^3$-нен аспайтынына және $m$ қосындысы $10^3$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін бір жолда бастапқы нүктеден соңғы нүктеге жетуге қажетті ең аз қадам санын білдіретін бір бүтін сан шығарыңыз. Егер соңғы нүктеге жету мүмкін болмаса, $-1$ шығарыңыз.

Мысалдар

Кіріс деректер 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

Шығыс деректер 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.