Državna razina / Primjena algoritama OŠ 2024. / Osnovna škola (6. razred) - 3. zadatak

Autocesta Zagreb-Vodice ima dvije prometne trake u istom smjeru. U lijevoj je traci na početku N, a u desnoj M automobila koji su označeni prirodnim brojevima od 1 do N+M. Zanimljivo, svaki automobil je dug točno 5 metara i razmak između susjednih automobila u svakoj od traka je 5 metara. Također, početak prvog automobila u lijevoj traci je točno 5 metara ispred početka prvog automobila u desnoj traci. Vidi opis rješenja. Tijekom vožnje dogodilo se Q događaja od kojih postoje 4 vrste:

1. Automobil s oznakom X izlazi iz prometa;
2. Automobil s oznakom X se prestrojava tj. prelazi iz trake u kojoj se nalazi u drugu traku;
3. Svi automobili se prebacuju u lijevu ili desnu traku;
4. Automobil s oznakom X pokušava preteći K automobila iz svoje trake. To može napraviti samo ako, kad dođe na željeno mjesto, iza njega neće biti nijedan automobil iz druge trake. Ako ne može izvršiti pretjecanje, ostaje na mjestu na kojem se nalazi.

Nakon što se raspored automobila nakon nekog događaja promijeni, automobili unutar trake se približavaju jedni drugima, tako da razmak između svaka dva automobila u traci ponovno bude 5 metara. Također, poslažu se tako da, ako u obje trake postoje automobili, početak prvog automobila u lijevoj traci ponovno bude 5 metara ispred početka prvog automobila u desnoj traci. Tvoj zadatak je odrediti raspored automobila nakon svih događaja..

Ulazni podaci

U prvom su retku cijeli brojevi N i M (0 ≤ N, M ≤ 100), brojevi iz teksta zadatka.

U drugom retku je N brojeva, redom oznake automobila u lijevoj traci.

U trećem retku je M brojeva, redom oznake automobila u desnoj traci.

U četvrtom retku je prirodan broj Q (1 ≤ Q ≤ 100), broj iz teksta zadatka.

U sljedećih Q redaka su opisi događaja, redom kojim su se događali. U svakom retku prvo dolazi prirodni broj T (1 ≤ T ≤ 4) koji označava tip događaja. Ostatak retka ovisi o T.

1. T=1: u ostatku retka je prirodan broj X, oznaka automobila koji izlazi iz prometa;
2. T=2: u ostatku retka je prirodan broj X, oznaka automobila koji se prestrojava. Ako se nalazi u lijevoj traci prestrojit će se u desnu, a ako se nalazi u desnoj u lijevu traku.
3. T=3: u ostatku retka je znak 'L' i 'D', ovisno o tome hoće li se svi automobili prebaciti u lijevu ili desnu traku.
4. T=4: u ostatku retka su redom oznaka automobila X i broj automobila K koje će automobil s oznakom X pokušati preteći. K neće biti veći od broja automobila koji se u istoj traci nalaze ispred automobila s oznakom X.

Izlazni podaci

U prvom retku ispiši cijele brojeve A i B, završni broj automobila u lijevoj i desnoj traci.

U drugom retku ispiši A prirodnih brojeva, redom završne oznake automobila u lijevoj traci.

U trećem retku ispiši B prirodnih brojeva, redom završne oznake automobila u desnoj traci.

Bodovanje

U primjerima vrijednima 10 bodova svi događaji će biti tipa 1.

U primjerima vrijednima dodatnih 10 bodova svi događaji će biti tipa 2.

U primjerima vrijednima dodatnih 10 bodova bit će samo jedan događaj i taj događaj će biti tipa 3.

U primjerima vrijednima dodatnih 20 bodova svi automobili će na početku biti u lijevoj traci i svi događaji će biti tipa 4.

Primjer zadatka

Ulaz

3 4
1 3 2
5 4 7 6
6
2 3
4 6 4
4 6 3
1 3
3 L
2 7

Izlaz

5 1
1 5 2 6 4
7

Ulaz

3 4
1 3 5
4 2 7 6
6
1 3
4 6 3
1 5
4 6 3
2 7
3 L

Izlaz

5 0
1 6 7 4 2

Ulaz

6 0
1 2 3 4 5 6

5
4 5 2
4 2 1
4 4 4
4 3 2
4 6 4

Izlaz

6 0
4 6 2 3 1 5

Opis prvog probnog primjera: