Prog: HackerRank
Prog: HackerRank

practice HackerRank

Directory

C++

Variable Sized Array

Original

Concidérons un tableau a de n éléments où chaque indexe i contient une référence à un autre tableau de ki entiers (dans lequel la valeur de ki varie d’un tableau à l’autre).

Pour un a donné, nous devons répondre à q requêtes. Les requêtes sont faites dans le format i j, où i désigne un indice dans le tableau a et j désigne un indice dans le tableau situé dans a[i]. Pour chaque requête, trouver et printer la valeur de l’élément j dans le tableau situé à l’indice a[i] sur une nouvelle ligne.

Sur l’énnoncé du problème original (en) ils nous conseillent d’utiliser un vecteur et non pas un tableau basique.

Format de l’input

La première ligne contient deux entiers séparés par un espace désignant respectivement la valeur de n (le nombre de tableaux de taille variable) et q (le nombre de requêtes). Chaque ligne i de la série de lignes n suivantes contient une séquence d’éléments au format $ k, \; a[i]0, \; a[i]_1, \; \ldots, \; a[i]{k-1} séparésparunespaceetdécrivantle k ièmetableausetrouvantàlindice a[i] .Chaquunedes q lignessuivantescontientdesentiersséparésparunespacedécrivantrespectivementlesvaleursde i (unindicedutableau a )et j (unindicedansletableauréférencépar a[i] $) pour une requête.

Contraintes

  • 1n105
  • 1q105
  • 1k3105
  • 1Σk3105
  • 0i <n
  • 0j <k


  • Tous les indices commencent à 0
  • Les valeurs entrées en input appartiennent à l’ensemble N et ne sont pas plus grandes que 106

Exemple d’input

2 2
3 1 5 4
5 1 2 8 9 3
0 1
1 3

Exemple d’output

5
9

Explication

Ce diagramme représente notre exemple d’input:

Nous effectuons les q=2 requêtes suivantes:

  1. Trouver le tableau situé à l’indice i=0 qui correspond à a[0]=[1,5,4] . Nous devons print les valeurs à l’indexe j=1 de ce tableau qui comme nous pouvons le voir est 5.

  2. Trouver le tableau à l’indexe i=1, qui correspond à a[1]=[1,2,8,9,3]. Nous devons print la valeur à l’indexe j=3 de ce tableau qui comme nous pouvons le voir est 9.

Solution

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    int tabs, q;
    int size, val;
    int x,y;

    cin >> tabs >> q;

    vector<vector<int>> tabsVec;

    for (int i = 0; i < tabs; ++i) {
        vector<int> temp;
        cin >> size;
        for (int j = 0; j < size; ++j) {
            cin >> val;
            temp.push_back(val);
        }
        tabsVec.push_back(temp);
    }

    for (int i = 0; i < q; ++i) {
        cin >> x >> y;
        cout << tabsVec[x][y] << "\n";
    }

    return 0;
}

Liens

C++ competitive programming I/O