# | Problem | Pass Rate (passed user / total user) |
---|---|---|
13022 | Message Recover |
|
13366 | Honey Game |
|
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
- Download "13022.c" file, and rename as "main.c"
- Download "13022.h" file, and rename as "function.h"
- Trace the code in "main.c"
- Implement the solver function in "function.c"
- Compile your project in your local IDE
- 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| ≤ 106
- 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.cPartial Judge Header
13022.hTags
Discuss
Description
Winnie the Pooh and Piglet are fighting for N jars of honey.
Pooh can carry 1~A jars of honey at a time, Piglet can carry 1~B jars of honey at a time.
Two players take turns.
Whoever can grab the last jar of honey will win.
Give you N, A, B, Who start first, please answer who will win if Pooh and Piglet play the best.
Example:
N = 6, A = 2, B = 2
The table shows the winner
If Pooh goes first, even Pooh carry 1 or 2 jars of honey(leave 5 or 4 jars of honey to Piglet),
Piglet can leave 3 jars of honey to Pooh.
Now there are 3 jars of honey left, even Pooh carry 1 or 2 jars of honey, Piglet can grab the last jar.
Hint:
Input
The first line you are given an integer T, means there will be T tests.(1 ≤ T ≤ 10)
Each test you are given integers N, A, B, and Who starts first(Pooh or Piglet).
(1 ≤ A, B ≤ 10, 1 ≤ N ≤ 10000)
Limit:
Testcase 1: N ≤ 10, A = B ≤ 10
Testcase 2~3: N ≤ 10, max{A, B} ≤ 10
Testcase 4~5: N ≤ 10000, max{A, B} ≤ 10
Output
Each test output the winner is Pooh or Piglet, and a new line.