|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Upiti
|
Dat je niz od n brojeva. Nad nizom se izvršavaju, jedan za drugim, m upita jednog od
sledeća dva tipa:
-
1 i - seče trenutni niz posle i-tog elementa i zatim drugi deo niza (od (i + 1)-vog
elementa do kraja) stavlja na početak, pri čemu se dobija novi niz od n elemenata.
Npr. za niz 5 3 10 8 8, upit '1 2' daje 5 3 | 10 8 8 → 10 8 8 | 5 3 → 10 8 8 5 3.
-
2 j - treba odgovoriti koji se broj nalazi na j-toj poziciji u trenutnom nizu.
Odgovoriti na sve upite tipa 2.
Ulaz:
(Ulazni podaci se nalaze u datoteci upiti.in.)
U prvom redu ulazne datoteke
nalaze se 2 prirodna broja n i m koji predstavljaju, redom, broj elemenata niza i broj upita
(1 ≤ n, m ≤ 105). Sledeći red sadrži n celih brojeva - elemente niza u datom redosledu
(svi elementi su iz [0, 109]). Sledećih m redova sadrže upite već opisanog formata: 'a b'
gde je a ∈ {1, 2} i 1 ≤ b ≤ n. Upiti se izvršavaju u redosledu datim na ulazu.
Izlaz:
(Izlazne podatke upisati u datoteku upiti.out)
Za svaki upit tipa 2 iz ulazne
datoteke ispisati u novi red izlazne datoteke odgovor na taj upit (odgovore ispisivati u
odgovarajućem redosledu). Postojaće bar jedan upit tipa 2.
Primer:
upiti.in
|
|
upiti.out
|
5 4
5 3 10 8 8
2 3
1 2
1 4
2 3
|
|
10
8
|
Objašnjenje.
Na trećoj poziciji u početnom nizu je broj 10. Posle dva sećenja niz postaje
3 10 8 8 5. Na trećoj poziciji u ovom nizu je broj 8.
Napomena.
U 30% test primera biće n, m ≤ 103.
|
|
fajl: upiti.cpp
|
#include <cstdlib>
#include <cstdio>
const int MaxN = 100010;
const int MaxM = 100010;
int n, m, a, b, x[MaxN], sol[MaxM];
int startIndex;
int main() {
FILE* inFile = fopen("upiti.in", "r");
FILE* outFile = fopen("upiti.out", "w");
fscanf(inFile, "%d%d", &n, &m);
// indeksiramo niz od 0 jer je tako lakse
for (int i = 0; i < n; i++)
fscanf(inFile, "%d", &x[i]);
startIndex = 0;
for (int i = 0; i < m; i++) {
fscanf(inFile, "%d%d", &a, &b);
if (a == 1)
startIndex = (startIndex + b) % n;
else
fprintf(outFile, "%d\n", x[(startIndex + b - 1) % n]);
}
fclose(inFile);
fclose(outFile);
}
|
|
fajl: upiti.pas
|
const
MaxN = 100010;
MaxM = 100010;
var
inFile, outFile : text;
n, m, a, b, startIndex, i : longint;
x : array[0..MaxN] of longint;
sol : array[0..MaxM] of longint;
begin
assign(inFile, 'upiti.in');
assign(outFile, 'upiti.out');
reset(inFile); rewrite(outFile);
read(inFile, n, m);
// indeksiramo niz od 0 jer je tako lakse
for i := 0 to n - 1 do
read(inFile, x[i]);
startIndex := 0;
for i := 1 to m do begin
read(inFile, a, b);
if (a = 1) then startIndex := (startIndex + b) mod n
else writeln(outFile, x[(startIndex + b - 1) mod n]);
end;
close(inFile);
close(outFile);
end.
|
|
|