2442 - I2P(I)2021_Yang_hw10 Scoreboard

Time

2021/12/07 20:30:00 2021/12/14 18:00:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# Problem Pass Rate (passed user / total user)
13022 Message Recover
13366 Honey Game

13022 - Message Recover   

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(xjfor 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.c

Partial Judge Header

13022.h

Tags




Discuss




13366 - Honey Game   

Description

Winnie the Pooh and Piglet are fighting for  jars of honey.

Pooh can carry 1~A  jars of honey at a time, Piglet can carry 1~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:

int Pooh_turn(int n){                 //return Pooh will win or not if N jars of honey left
     ...
    if( !Piglet_turn(n-1) || ...  !Piglet_turn(n-a) ) return true;         
                                                       //If there is a state Piglet will lose, then Pooh should choose it to win
    else return false;
}
 
int Piglet_turn(int n){               //return Piglet will win or not if N jars of honey left
     ...
    if( !Pooh_turn(n-1) || ...  !Pooh_turn(n-b) ) return true;
    else return false;
}

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.

Sample Input  Download

Sample Output  Download

Tags




Discuss