Fişierul intrare/ieşire:magician.in, magician.outSursăOlimpiada locala 2017 clasa a 6-a
AutorAutor NecunoscutAdăugată deabserbanBogdan abserban
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Magician (clasa a 6-a)

Notă: Problema nu conţine testele oficiale, suntem în curs de a le primi.

Matei, prietenul tău cel mai bun, te-a invitat împreună cu mai mulţi colegi de clasă, săptămâna trecută, la ziua lui de naştere. Pentru că a vrut să vă impresioneze, a avut şi câţiva animatori, printre care un magician. Toate trucurile magicianului v-au încântat. Unul dintre ele era interactiv şi chiar foarte simplu, deşi nu v-aţi descurcat foarte bine. La acest truc, el a aşezat pe o masă, în linie, mai multe pahare cu gura în jos. A ales apoi unul dintre pahare, sub care a băgat o bilă. A început să mute paharele, păstrând aranjarea lor liniară pe masă. De exemplu, dacă sunt 6 pahare pe masă în ordinea 1 2 3 4 5 6, la mutarea paharului 2 după paharul 5, ordinea paharelor devine 1 3 4 5 2 6. După ce făcea o serie de mutări cu o viteză uluitoare, vă întreba care este paharul ce conţine bila. Nici măcar o dată n-aţi nimerit paharul cu bila înăuntru. Matei este convins că, folosind calculatorul, poate să găsească rapid paharul ce conţine bila. Ştiind că îţi place foarte mult să programezi, te roagă pe tine să-i scrii un program care să determine locul final al paharului în care se găseşte bila.

Cerinţă

Dându-se un număr natural n, reprezentând numărul de pahare aşezate în linie pe masă, un număr natural k, reprezentând poziţia iniţială a paharului sub care se găseşte bila, un număr natural m, ce reprezintă numărul de mutări făcute şi m perechi de numere naturale, p1 şi p2, unde p1 înseamnă poziţia din care este luat un pahar, iar p2 este poziţia în care va fi mutat acel pahar, se cere să se determine care este poziţia finală a paharului ce conţine bila.

Date de intrare

Fişierul magician.in conţine m+1 linii. Pe prima linie sunt scrise trei numere naturale n, k şi m cu semnificaţia din cerinţă iar pe următoarele m linii, câte două numere naturale p1 şi p2, separate printr-un spaţiu, cu semnificaţiile din cerinţă. Pe linia i+1 este descrisă mutarea i.

Date de ieşire

Fişierul de ieşire magician.out va conţine pe prima linie, un număr natural ce reprezintă poziţia finală a paharului ce conţine bila.

Restricţii

  • 2 ≤ n ≤ 500 000,
  • 1 ≤ k ≤ n,
  • 0≤ m ≤ 10 000.

Exemplu

magician.inmagician.outExplicaţii
6 4 5
2 5
3 3
4 1
4 6
5 2
6
Iniţial paharele sunt aranjate astfel:
Mutarea 1 (din poziţia2 se ajunge în poz. 5):
Mutarea 2 (nu se face nicio mutare):
Mutarea 3 (din poziţia 4 se ajunge în poziţia 1):
Mutarea 4 (din poziţia 4 se ajunge în poziţia 6):
Mutarea 5 (din poziţia 5 se ajunge în poziţia 2):
Configuraţia finală este :
Se observă că paharul ce conţine bila a ajuns în final pe poziţia 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici