50091. Two-level Table

I'm a slow walker, but I never walk backwards.

Write a function to construct a two-level table.

Task Description

We are given two arrays $A$ with $N$ integers and $B$ with $M$ integers. Each element of $A$ indicates the size of a second level table, and ends with $0$. The array $B$ consists of partitions that end with $0$. For example, if $B = \lbrace 2, 3, 0, 1, 0, 4, 5, 6, 0, 1, 2, 0, 1, 1, 0\rbrace $, then the five partitions are $\lbrace 2, 3, 0\rbrace , \lbrace 1, 0\rbrace , \lbrace 4, 5, 6, 0\rbrace , \lbrace 1, 2, 0\rbrace , \lbrace 1, 1, 0\rbrace $.

Now you need to construct a two-level table and return a pointer to the starting address of the first level table. The first level array has $N - 1$ pointers, and each of them points to a second level array, and it ends with a NULL pointer. As a result there are $N-1$ second level pointer arrays, and the size of each array is indicated by the corresponding element in array $A$. Each element of a second level arrays is a pointer to the starting address of the corresponding partition in $B$. Similar to the first level array, each second level array ends with a NULL pointer. Please refer to the following figure.

p-10179. Table
You need to write a function constructTable, that given array $A$ and $B$, build the first and the second level tables, and return the starting address of the first level table. The prototype of constructTable function is as follows.

1
int ***constructTable(int A[], int B[]);

You may use the following main function to test your function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include "constructTable.h"
 
int main(){
    int N, M;
    int A[100] = {}, B[500] = {};
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; i++)
        scanf("%d", &A[i]);
    for(int i = 0; i < M; i++)
        scanf("%d", &B[i]);
 
    int ***ptr;
    ptr = constructTable(A, B);
    for(int i = 0; *(ptr+i) != NULL; i++)
        for(int j = 0; j < A[i]; j++)
            for(int k = 0; *(*(*(ptr+i)+j)+k) != 0; k++)
                printf("%d ", *(*(*(ptr+i)+j)+k));
    return 0;
}

The constructTable.h is as follow:

1
int ***constructTable(int A[], int B[]);

Note

Feel free to use malloc if you know how to. Otherwise declare the first and the second level tables outside of your function to make them global, so that our main program can access them. Also the second level pointer must point into $B$. You may not declare another integer array to store them.

Subtask

  • 30 points: Every partition has exactly one element, i.e., it has one nonzero element followed by a $0$.
  • 30 points: All partitions have the same number of elements.
  • 40 points: Not all partitions have the same number of elements.

Input Format

The input contains only one test case. The first line contains two integers $N$, $M$, representing the size of array $A$ and $B$. The second line contains $N$ integers, representing the elements of array $A$. The third line contains $M$ integers, representing the elements of array $B$.

  • $1 \lt N \lt 100$
  • $1 \lt M \lt 5000$
  • $0 \lt $ size of each second level table $\lt 100$
  • $0 \lt $ elements of each partition $\lt 100$

Output Format

Print the elements of array $B$ except $0$ in a line.

Sample Input 1

3 10
3 2 0
6 0 5 0 5 0 3 0 5 0

Sample Output 1

6 5 5 3 5

Sample Input 2

6 15
1 1 1 1 1 0
2 1 0 4 7 0 4 8 0 3 6 0 4 7 0

Sample Output 2

2 1 4 7 4 8 3 6 4 7

Sample Input 3

3 15
2 3 0
2 3 0 1 0 4 5 6 0 1 2 0 1 1 0

Sample Output 3

2 3 1 4 5 6 1 2 1 1

Discussion