Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Du får gitt heltallene $N, K$ og en heltallsfølge $X = (X_0, X_1, \dots, X_{N-1})$ med lengde $N$.

En heltallstrippel $(M, A, B)$ kalles en god trippel hvis den oppfyller alle følgende betingelser:

  • $1 \le M < 2^{30}$
  • For alle $k = 0, 1, \dots, N-1$ gjelder $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.

Det kan bevises at antallet gode tripler er endelig under de gitte begrensningene. La dette antallet være $C$.

Avgjør om $K \le C$ gjelder. Hvis det gjør det, finn den $K$-te minste gode trippelen i leksikografisk rekkefølge.

Du får gitt $T$ testtilfeller. Løs hvert testtilfelle uavhengig.

Inndata

Inndataene gis på følgende format:

T
case1
case2
:
caseT

Hvert testtilfelle $\text{case}_i$ gis på følgende format:

N K
X0 X1 ... XN-1

Begrensninger

  • Alle inndataverdier er heltall.
  • $1 \le T \le 1000$
  • $2 \le N \le 2 \times 10^5$
  • $1 \le K \le 10^9$
  • $0 \le X_i < 2^{30}$
  • Summen av $N$ over alle testtilfeller overstiger ikke $2 \times 10^5$.

Utdata

Skriv ut $T$ linjer.

For den $i$-te linjen, hvis $K \le C$ gjelder for det $i$-te testtilfellet, skriv ut den $K$-te minste gode trippelen i leksikografisk rekkefølge ved å skrive ut $M, A, B$ i denne rekkefølgen adskilt med mellomrom. Ellers, skriv ut -1.

Eksempel

Inndata 1

3
4 1
0 1 1 2
3 1
2 0 1
6 7
9 8 6 4 2 1

Utdata 1

2 1 1
-1
11 -19 107

Merk

I det første eksempelet er de gode triplene i leksikografisk rekkefølge $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.

I det andre eksempelet finnes det ingen god trippel.

I det tredje eksempelet er de gode triplene i leksikografisk rekkefølge $(M, A, B) = (4, -7, 39), (7, -12, 68), (8, -14, 78), (8, -14, 79), (9, -16, 89), (10, -17, 97), (11, -19, 107), \dots$.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1416EditorialOpen题解jianglyView

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.