Description

Deep beneath the Grand Library of Arcanis, an apprentice mage discovers a sealed vault containing a collection of enchanted scrolls. Each scroll bears a long sequence of characters, but the true message is hidden within.

The text on each scroll is structured as follows: meaningful spell fragments are separated by a recurring magic glyph pattern. To decode the scroll, you must:

1. Split the text at every occurrence of the glyph pattern to extract the individual spell fragments.
2. Sort the characters within each fragment according to the ancient rules of Magical Resonance.

Important: When the glyph pattern appears consecutively (with nothing between two occurrences), or at the very beginning or end of the text, no empty fragment is produced — simply skip over them. Only non-empty fragments are kept.

Sorting Rules (Magical Resonance Order)

Within each spell fragment, rearrange the characters according to the following rules (applied in order of priority):

1. Frequency first: Characters that appear more frequently in the fragment come first.
2. Type priority (same frequency): Uppercase letters (A–Z) come before lowercase letters (a–z), which come before digits (0–9).
3. Within same type and frequency:
   • Letters are sorted in dictionary order (A < B < ... < Z; a < b < ... < z).
   • Digits are sorted in increasing order (0 < 1 < ... < 9).

Example

String: MagicXScrollXAA11bbba Glyph pattern: X

Step 1 — Split: Splitting by X yields: ["Magic", "Scroll", "AA11bbba"]

Step 2 — Sort each fragment:

Hints

• char *strstr(const char *haystack, const char *needle);
  • Description: Finds the first occurrence of the null-terminated string needle in the null-terminated string haystack.
  • Return Value: Returns a pointer to the beginning of the located substring, or NULL if the substring is not found.
• void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
  • Description: Sorts an array with nmemb elements of size size.
  • Parameters:
    • base: Pointer to the first element of the array to be sorted.
    • nmemb: Number of elements in the array.
    • size: Size in bytes of each element in the array.
    • compar: A pointer to a function that compares two elements. It should return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.
• alphabet[] Priority Array
  • Pre-filled in main.c: A-Z (indices 0-25), a-z (indices 26-51), 0-9 (indices 52-61).
  • You can use these indices to determine the relative priority of characters during sorting.
• Reminder: Skip empty fragments. If the delimiter pattern appears consecutively, at the very beginning, or at the very end of the string, no output should be generated for those positions.

function.h:

extern char alphabet[65];

//implement split string function, return 2d char array to store result, set correct number of splitted strings
char **split(char* string, const char* pattern, int* splittedStrings);

//free memory space
void free_(char **result, int splittedStrings);

//sort each splitted string
void sort( char* string);

main.c:

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

#define MAX_S_LEN 505
#define MAX_P_LEN 15

char alphabet[65];

/**
 * Main function for the Enchanted Scroll Decoder.
 * This part of the code is handled by the server and cannot be modified by students.
 */
int main() {
    char s[MAX_S_LEN], p[MAX_P_LEN];

    scanf("%s %s", s, p);

    // Initialize the global alphabet priority array: A-Z, a-z, 0-9
    char *ptr = alphabet;
    for (char c = 'A'; c <= 'Z'; c++) *ptr++ = c;
    for (char c = 'a'; c <= 'z'; c++) *ptr++ = c;
    for (char c = '0'; c <= '9'; c++) *ptr++ = c;
    *ptr = '\0';

    int fragment_count = 0;
    char **fragments = split(s, p, &fragment_count);

    for (int i = 0; i < fragment_count; i++) {
        sort(fragments[i]);
    }

    free_(fragments, fragment_count);

    return 0;
}

Input

• Line 1: A string $S$ consisting of uppercase letters, lowercase letters, and/or digits. ($20 \le |S| \le 499$)
• Line 2: A delimiter pattern $P$ consisting of uppercase letters, lowercase letters, and/or digits. ($1 \le |P| \le 9$)

Test Case Design

• 01-02 (Easy): Basic splitting with no complex sorting (all same char or single-character fragments).
• 03-04 (Intermediate): Standard splitting and sorting.
• 05-08 (Hard): Large fragments, complex frequency ties, and edge cases.

Output

Output each sorted spell fragment on its own line, in the order they appear in $S$. The sort function in your function.c must handle the printing of the sorted fragment followed by a newline.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss