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

Sinulle annetaan kokonaisluvut $N, K$ ja pituutta $N$ oleva kokonaislukujono $X = (X_0, X_1, \dots, X_{N-1})$.

Kokonaislukukolmikkoa $(M, A, B)$ kutsutaan hyväksi kolmikoksi, jos se täyttää kaikki seuraavat ehdot:

  • $1 \le M < 2^{30}$
  • Kaikilla $k = 0, 1, \dots, N-1$ pätee $X_k = \lfloor \frac{Ak + B}{M} \rfloor$.

Voidaan todistaa, että annettujen rajoitusten puitteissa hyvien kolmikoiden lukumäärä on äärellinen. Olkoon tämä lukumäärä $C$.

Määritä, päteekö $K \le C$. Jos pätee, etsi aakkosjärjestyksessä (leksikografisessa järjestyksessä) $K$:nneksi pienin hyvä kolmikko.

Sinulle annetaan $T$ testitapausta. Ratkaise jokainen testitapaus toisistaan riippumatta.

Syöte

Syöte annetaan seuraavassa muodossa:

T
case1
case2
:
caseT

Jokainen testitapaus $\text{case}_i$ annetaan seuraavassa muodossa:

N K
X0 X1 ... XN-1

Rajoitukset

  • Kaikki syötteen arvot ovat kokonaislukuja.
  • $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}$
  • Lukujen $N$ summa yli kaikkien testitapausten ei ylitä $2 \times 10^5$.

Tuloste

Tulosta $T$ riviä.

Jos $i$:nnessä testitapauksessa pätee $K \le C$, tulosta $i$:nnelle riville leksikografisessa järjestyksessä $K$:nneksi pienin hyvä kolmikko tulostamalla $M, A, B$ tässä järjestyksessä välilyönnein eroteltuina. Muussa tapauksessa tulosta -1.

Esimerkki

Syöte 1

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

Tuloste 1

2 1 1
-1
11 -19 107

Huomautus

Ensimmäisessä esimerkissä hyvät kolmikot leksikografisessa järjestyksessä ovat $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$.

Toisessa esimerkissä ei ole yhtään hyvää kolmikkoa.

Kolmannessa esimerkissä hyvät kolmikot leksikografisessa järjestyksessä ovat $(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.