Summer FLASG Advanced | ConcursulAdvanced

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 256MB Input: Output:

Kilonova a implementat un nou sistem de rating și fiecare cont are asociat un rating care este un număr întreg (nu neapărat pozitiv!). Cu acest sistem pus în loc, Flaviu s-a decis să se înscrie într-un concurs, pentru a compara rating-ul său cu ceilalți participanți. Virusul de pe telefon l-a afectat și pe Flaviu printr-o breșă de securitate, iar virusul se manifestă prin a infecta conturi de Kilonova.

Contul lui Flaviu este deja infectat și are rating-ul constant xx. Cu excepția contului lui, platforma are nn conturi, numerotate de la 11 la nn, fiecare cu rating-ul rir_i. Orice cont afectat infectează alte conturi dacă au rating egal. Acest lucru se poate întâmpla fie la început (unde nu s-a schimbat rating-ul), fie la sfârșit. Un cont infectat nu mai poate fi recuperat.

Concursurile sunt organizate zilnic pe Kilonova, și oricare dintre cele nn conturi (inclusiv cele infectate) pot să participe. Creatorul platformei a detectat că nu e ceva în regulă cu contul lui Flaviu și în consecință l-a banat de la a mai participa la concursuri. După fiecare concurs se actualizează scorul astfel: ratingul fiecărui participant se schimbă cu un număr întreg aleatoriu, însă suma acestor schimbări trebuie să fie zero, pentru a-i răsplăti pe participanții care au terminat primii și a-i pedepsi pe cei care nu s-au chinuit.

Cerință

Aflați numărul minim de concursuri necesare pentru a infecta toată platforma. Se poate decide ce conturi participă la un concurs anume și cum se va schimba rating-ul fiecărui participant.

Date de intrare

Pe prima linie se găsește un singur număr natural tt, reprezentând numărul de teste.

Pe prima linie a fiecărui teste se află un număr natural nn, numărul de conturi înscrise pe platformă, și xx, scorul lui Flaviu.
Pe a doua linie se află rating-urile fiecărui cont r1r_1, r2r_2, ..., rnr_n.

Date de ieșire

Pe fiecare din cele nn linii se va afișa numărul minim de conturi infectate.

Restricții și precizări

  • 1t1001 \leq t \leq 100;
  • 2n1 0002 \leq n \leq 1\ 000;
  • 1x50001 \leq |x| \leq 5000;
  • 0ri50000 \leq |r_i| \leq 5000;
  • 0rix50000 \leq |r_i - x| \leq 5000 (adică 0ri50000 \leq |r_i| \leq 5000 după fiecare schimbare).

Exemplu

stdin

3
2 2023
1923 2123
6 10
10 10 10 10 10 10
9 38
-21 83 50 -59 -77 15 -71 -78 20

stdout

1
0
2

Explicație

În primul caz, este posibil să faci toate rating-urile să fie egale cu 20232023: scazi rating-ul primului concurent cu 100100 și crești rating-ul ultimului concurent cu 100100, așadar 100+100=0-100 + 100 = 0.

În al doilea caz, din moment ce toate conturile au rating egal, acestea vor fi infectate instant.

Log in or sign up to be able to send submissions!