Description

One day, Panda gives an unreadable message M and a special number P.
You need to decode the message M by the number P

The message M is composed of several pairs of number and word xi, wi.
Each number xi must be followed by its corresponding word wi which length is greater than 0.
For example: 1A3B2C, 0Hello3World are valid, while 1A2B3, ABC123, ABC are not.

Let re-order function f(x) = x mod P
Then f(xi) represents the word order of wi.
For f(xi) < f(xj), wi appears before wj after decode.
For the words have the same order f(xi) = f(xj), concat these words in the appearing order in M and regard the concated string as a single word.

Given M and P, please decode the message M by the rule above and output the number of words in result.
!! This is a partial judge problem !!

 

Explaintation of Sample I/O

Sample 1:
M =1is5message3this, P = 3
f(xi), wi : (1,is), (2,message), (0,this).
The decoded message is this is message which has 3 words.

Sample 2: with same index
M = 1Hel4lo7World, P = 3
f(xi),wi: (1,Hel), (1,lo), (1,World).
The decoded message is HelloWorld which has 1 words.

 

Partial Code

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "function.h"

#define maxn 1000
#define maxl 1000

int P;
char M[1000010];

int main() {
    int n = 0;
    char Table[maxn][maxl+1]; // +1 for null char
    char *ptr[maxn];

    for (int i = 0; i < maxn; i++) {
        for(int j=0; j < maxl + 1; j++)
            Table[i][j] = '\0';
        ptr[i] = &Table[i][0];
    }

    scanf("%d", &P);
    scanf("%s", M);

    solver(ptr, &n, P, M);
    
    int cnt = 0;
    printf("%d\n", n); // the # of words
    for(int i=0; i<P; i++){
        if( strlen( Table[i] ) != 0 ){
            // if the position is non-empty.
            if( cnt < n-1 )
                printf("%s ", Table[i]);
            else
                printf("%s\n", Table[i]);
            cnt++;
        }
    }
    return 0;
}

function.h

#ifndef FUNCTION_H
#define FUNCTION_H

void solver(char **ptr, int *n, int P, char *M);
#endif

 

What you need to do in this problem

1. Download "13022.c" file, and rename as "main.c"
2. Download "13022.h" file, and rename as "function.h"
3. Trace the code in "main.c"
4. Implement the solver function in "function.c"
5. Compile your project in your local IDE
6. Submit your "function.c" to OJ

 

In your solver function, based on P and *M, you should use **ptr and *n to update the values of Table[][] and n in the main function as required. For example, for Sample 1 above, your Table[][] and n should be:

Hints for testcases

• For the 1~3-th testcases: f(xi) ≠ f(xj) for all i, j
• For the 4~6-th testcases: f(xi) = f(xj) for some i, j

Input

There’re 2 lines for input.
The first lines contains P.
The second lines contains M

It’s guaranteed that:

• 1 ≤ |M| ≤ 10⁶
• 1 ≤ P ≤ 1000
• xi ≥ 0
• The # of (xi,wi) pairs ≤ 1000
• The maximum length of each word after decoding ≤ 1000

Output

Output the number of words in decoded message on the first line.
and print decoded message on the second line, where the words are separated by white space.

Remember ‘\n’ on the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13022.c

Partial Judge Header

13022.h

Discuss