Fişierul intrare/ieşire:aiacubile.in, aiacubile.outSursăGrigore Moisil 2017, 10
AutorMircea Popoveniuc, Razvan SalajanAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aiacubile

Cangurul Bulănel trebuie să aibă grijă de N copii. Pentru a nu se plictisi, acesta s-a gândit la un joc să se joace împreună cu ei.
Cangurul Bulănel aşează copiii într-un cerc şi le atribuie câte un număr de la 1 la N. Poziţiile pe care sunt aşezaţi copiii sunt de asemenea numerotate de la 1 la N. Fiind în cerc, fiecare poziţie are o poziţie succesoare: după 1 urmează 2, după 2 urmează 3, ... după N-1 urmează N, după N urmează 1. Iniţial, fiecare copil se aşează pe poziţia egală cu indicele său: copilul 1 se aşează pe poziţia 1, copilul 2 se aşează pe poziţia 2, ... copilul N se aşează pe poziţia N.
Jocul se desfăşoară pe parcursul mai multor ture. O tură a jocului se desfăşoară astfel: cangurul Bulănel porneşte de pe poziţia 1 şi sare din K în K poziţii până când ajunge pe o poziţie pe care a mai fost în tura respectivă. Copiii aşezaţi pe poziţiile vizitate de Bulănel primesc de la acesta câte o bilă. La finalul turei, copiii îşi schimbă ordinea în felul următor: un copil aflat pe poziţia i se mută pe poziţia P[i]. După ce toţi copiii îşi schimbă ordinea, începe o nouă tură a jocului după cum a fost descrisă anterior.
De exemplu, dacă considerăm că jocul se joacă cu N = 6 copii, iar cangurul Bulănel sare K = 2 poziţii, atunci:

Copiii sunt aşezaţi în cerc iniţial. Bulănel începe de pe poziţia 1 şi îi lasă copilului 1 o bilă.Bulănel sare 2 poziţii, ajunge pe poziţia 3 şi îi lasă copilului 3 o bilă.Bulănel sare 2 poziţii, ajunge pe poziţia 5 şi îi lasă copilului 5 o bilă.Bulănel sare 2 poziţii, ajunge pe poziţia 1. Deoarece a mai vizitat poziţia 1 în tura curentă, se opreşte.

La finalul turei, copiii 1, 3 şi 5 au primit câte o bilă. Înainte de începerea turei următoare, copiii îşi schimbă poziţiile altfel: dacă pentru jocul acesta considerăm şirul P ca fiind 5 3 1 6 2 4, atunci copilul de pe poziţia 1 (copilul 1) se va muta pe poziţia 5, copilul de pe poziţia 2 (copilul 2) se va muta pe poziţia 3, copilul de pe poziţia 3 (copilul 3) se va muta pe poziţia 1, copilul de pe poziţia 4 (copilul 4) se va muta pe poziţia 6, copilul de pe poziţia 5 (copilul 5) se va muta pe poziţia 2, iar copilul de pe poziţia 6 (copilul 6) se va muta pe poziţia 4. Aşadar, pe fiecare poziţie de la 1 la 6 o să se afle, în ordine, copiii 3 5 2 6 1 4. Cangurul Bulănel va sări pe poziţiile 1, 3 şi 5 şi va lăsa câte o bilă copiilor 3, 2 şi 1.
Jocul se termină când copiii ajung la ordinea de la care au pornit iniţial.

Cerinţă

Cangurul Bulănel doreşte să joace mai multe astfel de jocuri. Pentru fiecare joc, cunoscându-se numărul N de copii, lungimea K reprezentând numărul de poziţii pe care cangurului Bulănel le poate sări şi şirul P care descrie felul în care copiii îşi schimbă poziţiile la fiecare tură, să se afle câţi copii primesc cel puţin o bilă pe parcursul întregului joc.

Date de intrare

Fişierul de intrare aiacubile.in conţine pe prima linie numărul natural T, reprezentând numărul de jocuri la care cangurul Bulănel participă. Următoarele 2*T linii descriu cele T jocuri în felul următor: pe linia 2*i se află numerele naturale N şi K, cu semnificaţia din enunţ, iar pe linia 2*i+1 se află N numere naturale ce formează şirul P, ce descrie cum îşi schimbă copiii ordinea la fiecare tură, pentru al i-lea joc.

Date de ieşire

Fişierul de ieşire aiacubile.out va conţine T linii. Fiecare linie conţine câte un număr natural care reprezintă numărul de copii ce au primit măcar o bilă pe parcursul celui de-al i-lea joc.

Restricţii

  • Pentru toate testele, 1 ≤ T ≤ 10.
  • Pentru toate testele, 1 ≤ P[i] ≤ N, iar şirul P conţine doar numere distincte.
  • Se garantează că, la orice moment al oricărui joc, va fi exact un copil pe fiecare poziţie.
  • Se garantează că fiecare joc are un număr finit de ture.
  • Pentru teste în valoare de 20 de puncte, 1 ≤ N ≤ 1 000, iar numărul de ture pe care le are fiecare joc se garantează că este ≤ 1 000.
  • Pentru teste în valoare de 90 de puncte, 1 ≤ N ≤ 100 000.
  • Pentru toate testele, 1 <= K <= N.
  • Problema va fi evaluată pe teste în valoare de 90 de puncte.
  • Exemplele vor reprezenta teste în valoare de 10 ("puncte din oficiu") şi vor fi cu feedback.

Exemplu

aiacubile.inaiacubile.out
2
6 2
5 3 1 6 2 4
12 9
1 6 7 4 9 8 3 12 10 11 5 2
4
8

Explicaţie

Explicaţie pentru primul joc:
În prima tură de joc, copiii sunt în ordinea 1 2 3 4 5 6. Copiii 1, 3 şi 5 primesc câte o bilă (ca în enunţ).
În a doua tură de joc, copiii sunt în ordinea 3 5 2 6 1 4. Copiii 3, 2 şi 1 primesc câte o bilă (ca în enunţ).
În a treia tură de joc, copiii sunt în ordinea 2 1 5 4 3 6. Copiii 2, 5 şi 3 primesc câte o bilă.
În a patra tură de joc, copiii sunt în ordinea. 5 3 1 6 2 4. Copiii 5, 1 şi 2 primesc câte o bilă.
În a cincea tură de joc, copiii sunt în ordinea 1 2 3 4 5 6. Fiind ordinea iniţială, jocul se opreşte. Copiii 1, 2, 3 şi 5 au primit măcar câte o bilă pe parcursul jocului, aşa că răspunsul pentru primul joc este 4.

Pentru al doilea joc, copiii 1, 3, 4, 5, 7, 9, 10, 11 sunt cei care primesc bile, deci răspunsul este 8.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?