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.
== include(page="template/taskheader" task_id="magician") ==
_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.
h2. 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.
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.
h2. 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.
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.
h2. 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.
h2. Restricții și precizări
2 ≤ n ≤ 500 000,
1 ≤ k ≤ n,
0≤m≤ 10 000
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.
h2. Restricții
* $2 ≤ n ≤ 500 000,$
* $1 ≤ k ≤ n,$
* $0≤ m ≤ 10 000.$
h2. Exemplu
table(example).
|_. magician.in |_. magician.out |_. Explicații |
| 6 4 5
2 5
3 3
4 1
4 6
5 2
| 6
| !>problema/magician?totipasii.png! 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
|
== include(page="template/taskfooter" task_id="magician") ==
