Description

In the ruins of an ancient civilization, archaeologists have uncovered a row of $N$ Crystalline Spires — towering structures of varying heights. Each spire stores a reservoir of energy and, when activated, simultaneously broadcasts its energy value $V_i$ outward in both directions along the line.

However, due to the physical properties of crystalline resonance, the energy broadcast can only be absorbed by the nearest spire taller than itself on each side. If no taller spire exists on a given side, the energy dissipates into the void.

Please calculate which spire receives the most total energy and how much it receives.

Input

The first line contains an integer $N$.

From the 2nd to the $(N+1)$-th line, the $(i+1)$-th line contains two integers $H_i$ and $V_i$, representing the height and broadcast energy value of the $i$-th spire.

All $H_i$ are distinct.

Constraints

• Subtask 1, 2: $1 \le N \le 5000$, $1 \le H_i \le 10^5$, $1 \le V_i \le 10^5$
• Subtask 3, 4: $1 \le N \le 10^5$, $1 \le H_i \le 2\times10^9$, $1 \le V_i \le 10^9$
• Subtask 5, 6: $1 \le N \le 10^6$, $1 \le H_i \le 2\times10^9$, $1 \le V_i \le 10^9$
• Subtask 7, 8: $1 \le N \le 5\times10^6$, $1 \le H_i \le 2\times10^9$, $1 \le V_i \le 10^9$

(For subtasks 7 and 8, the time limit is 2 seconds.)

Output

Output two numbers: the station number that receives the most energy and the total amount of energy received.

If multiple stations receive the same maximum energy, print the one with the smaller index.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

Description

The previous chess challenge was too difficult for Sai.

To build up his confidence and solidify his basic offensive skills, Sai has decided to try simpler challenge. He wants to know if it is possible to break through the enemy lines and capture the opponent's King in 3 moves or fewer.

The chessboard is a standard 8x8 grid, with columns labeled A to H and rows labeled 1 to 8. Sai can use the following pieces, each following standard chess movement rules:

• R (Rook): Moves any number of squares horizontally or vertically.

• N (Knight): Moves in an "L" shape (two squares in one direction, then one square perpendicular). Only Knights can jump over other pieces.

• P (Pawn): Moves straight forward one vacant square, but captures diagonally one square forward. (Note: To keep things simple, pawns cannot make an initial two-square move, and pawn promotion is ignored in this challenge.)

Since Sai is practicing with static puzzles, the rules for this challenge are slightly modified:

1. Static Opponent: The opponent's pieces do not move; they simply act as obstacles.

2. Consecutive Moves: Sai can make up to 3 consecutive moves with his pieces to hunt down the King.

(Note: For simplicity, only the movement of the player's Rooks (R), Knight (N), and Pawn (P) is considered. However, other pieces may still be present on the board and act as obstacles. Furthermore, unlike the previous assignment, the opponent's army consists of more pieces than just the King. You must take into account situations where pieces block your path or can be captured.)

You can use this code as a reference template.

#include <stdio.h>

typedef struct Position {
    int x;
    int y;
} Position;

typedef struct Piece {
    char type;
    Position pos;
} Piece;

typedef struct Move {
    Position start;
    Position end;
} Move;

typedef struct GameState {
    int player_count;
    Piece player[16];
    int opponent_count;
    Piece opponent[16];
    Move moves[3];
} GameState;

typedef struct SearchResult {
    int min_steps_to_checkmate;
    Move moves[3];
} SearchResult;

// If you would like to solve with BFS
// typedef struct QueueNode {
//     GameState state;
//     int step;
// } QueueNode;

const int ROOK_DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int KNIGHT_DIRS[8][2] = {{-1, 2}, {1, 2}, {-1, -2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

void Check_Checkmate(...) {
    ...
}

int main() {
    char type, pos_x, pos_y;
    GameState state;
    SearchResult result;
    result.min_steps_to_checkmate = 4;  // 4 indicates it is impossible to capture the King within three steps

    scanf("%d", &state.player_count);
    for (int i = 0; i < state.player_count; i++) {
        scanf(" %c %c%c", &type, &pos_x, &pos_y);
        state.player[i].type = type;
        state.player[i].pos.x = pos_x - 'A';
        state.player[i].pos.y = pos_y - '1';
    }

    scanf("%d", &state.opponent_count);
    for (int i = 0; i < state.opponent_count; i++) {
        scanf(" %c %c%c", &type, &pos_x, &pos_y);
        state.opponent[i].type = type;
        state.opponent[i].pos.x = pos_x - 'A';
        state.opponent[i].pos.y = pos_y - '1';
    }

    Check_Checkmate(...);

    if (result.min_steps_to_checkmate == 4) {
        printf("None\n");
    }
    else {
        printf("%d\n", result.min_steps_to_checkmate);
        for (int i = 0; i < result.min_steps_to_checkmate; i++) {
            printf("%c%c %c%c\n",
                    result.moves[i].start.x + 'A', result.moves[i].start.y + '1',
                    result.moves[i].end.x + 'A', result.moves[i].end.y + '1');
        }
    }
}

Input

For each test case:

• The first line contains an integer p, representing the number of Sai's (the player's) pieces.

• The next p lines describe Sai's pieces. Each line contains a character representing the piece type (Q, R, N...) and its position (e.g., A1), separated by a space.

• The next line contains an integer o, representing the number of the opponent's pieces.

• The following o lines describe the opponent's pieces in the same format.

Constraints:

• 1 <= p <= 16

• 1 <= o <= 16

Testcase Design:

• Testcase 1: o = 1, Rook

• Testcase 2: o = 1, Knight 

• Testcase 3: o = 1, Pawn

• Testcase 4: o = 1, Rook, Knight, Pawn

• Testcase 5~8: Unlimited

Output

For each test case:

• If the opponent's King can be captured in 3 moves or fewer, print the minimum number of moves n on the first line.

• For the next n lines, print the starting and ending positions of each move, separated by a space (e.g., A1 C3).

• If the King cannot be captured within 3 moves, print None on a single line.

• It is guaranteed that the optimal solution is strictly unique. That is, there is exactly one sequence of moves to achieve checkmate in the minimum number of steps.

Sample Input  Download

Sample Output  Download

Tags

Discuss