Question

Imi poate rezolva cnv problema asta in c++?

Cerință
Considerăm un șir format din n elemente. Definim următoarele operații astfel:

permutare circulară la stânga: mutarea primului element la sfârșitul șirului 1 2 3 4 -> 2 3 4 1 -> 3 4 1 2
permutare circulară la dreapta: mutarea ultimului element la începutul șirului 1 2 3 4 -> 4 1 2 3 -> 3 4 1 2
Dându-se un șir format din n elemente și două numere k și p, să se permute cu k poziții la dreapta dacă p este -1, respectiv la stânga dacă p este 1.

Date de intrare
Pe prima linie se află 3 numere: n , k și p. Pe următoarea linie se găsesc n numere naturale, reprezentând elementele șirului.

Date de ieșire
Se vor afișa n numere pe o singură linie, separate printr-un spațiu, reprezentând elementele șirului obținut în urma operațiilor de permutare.

Restricții
1 ≤ n ≤ 1 000 000
0 ≤ k ≤ 1 000 000
Elementele șirului sunt numere naturale cuprinse între 1 și 1 000
p poate avea doar valorile 1 și -1
Exemplu
Date de intrare Date de ieșire
4 1 -1
1 2 3 4 4 1 2 3
4 2 1
1 2 3 4 3 4 1 2

Answer 1

► COD C++:

#include <iostream>

using namespace std;

int main() {

int i, n, * v, * x, aux = 0, p, k, j;

//Citire dimensiuni

cin >> n >> k >> p;

k = k % n;

//Alocare vectori

v = new int[n];

x = new int[n];

//Citire vector

for (i = 0; i < n; ++i) {

 cin >> v[i];

}

//Daca avem permutare la dreapta

if (p == -1) {

 for (i = n - 1; i >= 0; --i)

  x[i] = v[(i - k + n) % n];

}

//Daca avem permutare la stanga

if (p == 1) {

 for (i = 0; i < n; ++i)

  x[i] = v[(i + k) % n];

}

//Afisare vector

for (i = 0; i < n; ++i) {

 cout << x[i] << " ";

}

//Dealocare

delete[] v;

delete[] x;

return 0;

}

► Explicatie :

◘ De ce k←k%n ?

Daca avem un vector cu n elemente si se cere sa facem o permutare (la stanga sau la dreapta) cu n elemente atunci ajungem exact in pozitia initiala.

Daca avem n elemente in vector, o permutare circulara (la stanga sau la drapta) cu k elemente este echivalenta cu o permutare cu k%n elemente.

Spre exemplu daca n=5 si k=6 atunci stim ca dupa 5 permutari ajungem fix in pozitia in care suntem. Deci e necesar sa facem doar o singura permutare.

Cu aceasta observatie simplificam extrem de mult problema, in loc sa facem cateva mii de permutari putem face doar cateva zeci.

◘ Ce inseamna new[] si delete[] ?

Sunt operatori de alocare dinamica. Pe scurt, daca nu stim de la inceput dimensiunea exacta a vectorului, in loc sa alocam un vector de 10000 de elemente si sa irosim aiurea spatiul din memorie (noi avand de fapt nevoie de 5 elemente, spre exemplu) alocam dinamic exact atat cat avem nevoie, dupa ce am citit dimeniunea folosind "new". La sfarsit eliberam folosind delete. Iti sugerez sa verifici documentatia online pentru mai multe informatii.

◘ Explicatie rezolvare :

Folosim doi vectori. In v cititm, in x formam sirul. In functie de directia permutarii copiem incepand de la dreapta sau de la stanga (determinam sensul in care parcurgem vectorii v si x). In functie de k determinam de la ce pozitie se incepe copierea elementelor.

O idee buna e sa lucram pe un exemplu pe care incercam sa determinam in ce directie sau de la ce index trebuie sa incepem copierea. Trecem apoi la mai multe exemple, iar apoi venim cu o regula generala.