Description

Given two positive integers a and b, compute the greatest common divisor (GCD) of a and b. The GCD of a and b is the biggest integer that can divide a and b with no reminder.

Input

First line contains a positive integer t (t<=1000), which indicates the number of test cases in the input. In the next t lines, each line contains two positive integers a, b, which are smaller than or equal to 10⁶.

Case 1: t<=100, a, b<=100
Case 2: t<=10000, a, b<=10000
Case 3: t<=20000, a, b<=100000
Case 4: t<=25000, a, b<=1000000

Output

 For each case, output the GCD of a and b in a line.

Sample Input  Download

Sample Output  Download

Discuss

Description

Hodilo is a well-known hot pot restaurant, and it's extremely challenging to have a table during peak dining hours in Hodilo. Even though, the restaurant does not accept reservations in advance, requiring every guest to visit the restaurant, take a number, and wait for their turn. Hodilo is opening a new branch in Hsinchu, and you have been invited to design a queuing system, which helps assign a table to each guest. 

This is a partial judge problem, please trace the code and check the following description.

main.c

In the main function, we start by reading the input, creating the table and guest struct, and simulating the flow of time: 11:00 (OPEN_TIME) ~ 15:00 (CLOSE_TIME).

At certain time points, we check if there are guests leaving at that moment and output the log of a guest leaving the restaurant. Then, we check the frontmost guest who has not yet entered the restaurant and output the log of a guest entering the restaurant if a table is available. Also, we output the status of all the tables every hour.

(If the frontmost guest is not entering the restaurant, the following guests are blocked by that frontmost guest and have to wait in queue. Guests are allowed to enter the restaurant at closing time and complete their entire dining time)

The output part is already implemented, and you can trace the code and refer to the output format description for more details.

#include <stdio.h>
#include "function.h"
#define TABLE_COUNT 50
#define GUEST_COUNT 50
#define OPEN_TIME 660
#define CLOSE_TIME 900

Table *table[TABLE_COUNT];
Guest *guest[GUEST_COUNT];
int tableCount, guestCount;
int currentGuest = 0;

void tableStatus(int time) {
    printf("%02d:%02d (%d) -> table: |", time/60, time%60, time);
    for (int i=0; i<tableCount; i++) {
        if (table[i]->guest) printf("%s(%dmin)", table[i]->guest->guestName, table[i]->leaveTime-time);
        printf("|");
    }
    printf("\n");
}

int main() {
    scanf("%d", &tableCount);
    for (int i=0; i<tableCount; i++) table[i] = createTable();
    scanf("%d", &guestCount);
    for (int i=0; i<guestCount; i++) guest[i] = createGuest();
    for (int i=OPEN_TIME; i<=CLOSE_TIME; i++) {
        while (1) {
            Guest *leave = checkLeave(table, tableCount, i);
            if (!leave) break;
            printf("%02d:%02d (%d) -> %s: leave\n", i/60, i%60, i, leave->guestName);
        }
        while (currentGuest < guestCount && guest[currentGuest]->arriveTime <= i) {
            int success = assignTable(table, tableCount, i, guest[currentGuest]);
            if (!success) break;
            printf("%02d:%02d (%d) -> %s: enter\n", i/60, i%60, i, guest[currentGuest]->guestName);
            currentGuest++;
        }
        if (i % 60 == 0) tableStatus(i);
    }
}

function.h

• Table* createTable() 
  • A function that reads the input, allocates memory for the table struct, and returns it.
• Guest* createGuest() 
  • A function that reads the input, allocates memory for the guest struct, and returns it.
  • Remember to also allocate memory for the guest name string.
• Guest* checkLeave(Table **table, int tableCount, int currentTime) 
  • Given the table array and its size, along with the current time.
  • Find the first table in the array at which the occupied guest is about to leave, return the pointer to that guest, and update the table status (guest = NULL).
    • Check through the array and find the first table where leaveTime == currentTime.
• int assignTable(Table **table, int tableCount, Guest *guest)  
  • Given the table array and its size, along with the guest pointer.
  • Find the first table that is available and large enough for the guest.
    • Check through the array and assign the first available table where table->tableSize >= guest->groupSize.
  • If the table is successfully assigned to the guest, update the table's status (leaveTime, guest) and return 1; otherwise, return 0.

#ifndef __FUNCTION_H__
#define __FUNCTION_H__

typedef struct {
    char *guestName;
    int groupSize;
    int arriveTime;
    int diningTime;
} Guest;

typedef struct {
    int tableSize;
    int leaveTime;
    Guest *guest;
} Table;

Table* createTable();
Guest* createGuest();
Guest* checkLeave(Table **table, int tableCount, int currentTime);
int assignTable(Table **table, int tableCount, int currentTime, Guest *guest);

#endif

Input

• The first line contains an integer N (1 ≤ N ≤ 50), representing the number of tables in the restaurant.
• The second line contains N integers x₁, x₂, ..., x_n (1 ≤ x_i ≤ 4) , each representing the size of a table in the restaurant.
• The third line contains an integer M (1 ≤ M ≤ 50), representing the number of incoming guests.
• Each of the following M lines represents the information of each guest, containing a string and three integers.
  These represent the guest name, the size of the guest group, the arrival time, and the dining time.
  • The guest name is a string consisting only of the English alphabet a-z/A-Z, and its size does not exceed 10 characters.
  • 1 ≤ size of the guest group ≤ 4
  • 660 ≤ arrival time ≤ 900
    • The time is represented in the format of the number of minutes after 00:00.
    • The arrival times are guaranteed to be in non-decreasing order.
  • 1 ≤ dining time ≤ 300 (mins)

Output

(This part is already implemented in main.c)
A program that outputs the log for each guest entering and leaving the restaurant.

For every moment a table is ready to be assigned to an arriving guest or when a guest is about to leave, output
hh:rr(minsAfter00:00) -> guestName: enter/leave

Additionally, every hour, output the status of the N tables,
including the names of the occupied guests and their remaining dining time:
hh:rr(minsAfter00:00) -> |guestName(remainingTime)|...|guestName(remainingTime)|

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

In the development of "Neural Link" human-computer interface technology, the synchronization signals between the human brain and the computer are encoded as 32-bit unsigned integers (uint32_t). Each bit represents the active state of a micro-neural node, where 1 indicates an active state and 0 indicates a dormant state.

However, due to rejection reactions, the raw received signal $S$ occasionally malfunctions. As a neural engineer, you must write a C firmware program to automatically perform "safety checks" and "neural bridging repair" on the input signal $S$, and calculate the final "checksum signal".

The processing flow must strictly adhere to the following three rules:

Rule 1: Overload Detection

The neural network is extremely fragile, and under no circumstances can two or more "adjacent" neural nodes be active simultaneously (i.e., consecutive 1s).

If the input signal $S$ contains any adjacent 1s (e.g., ...00110... in binary), it must be immediately classified as an overload.

When an overload is detected, your program must output 0xFFFFFFFF directly and ignore all subsequent rules.

Rule 2: Neural Bridging

If the signal passes Rule 1 (no adjacent 1s), you need to stabilize the signal transmission. Energy flows between the "highest active node" and the "lowest active node."

1. Find the Most Significant 1 (MSB) and the Least Significant 1 (LSB) in the signal.
2. To establish a stable neural bridge, you must invert the states (NOT operation) of ALL neural nodes strictly between these two nodes. Bits that were 0 become 1, and bits that were 1 become 0. The MSB and LSB themselves must remain unchanged (1).

Note: If the signal contains only one active node, or no active nodes at all, no inversion is required, and the signal remains unchanged.

The modified signal after this step is referred to as $S_{\text{bridge}}$.

Rule 3: Checksum Integration

To ensure the signal is not tampered with when written back to the brain, $S_{\text{bridge}}$ must undergo a final processing step:

1. Split $S_{\text{bridge}}$ into 4 distinct bytes.
2. Perform a Bitwise XOR operation across these 4 bytes to calculate an 8-bit Checksum.
3. Finally, forcefully replace the lowest byte (Bits 0~7) of $S_{\text{bridge}}$ with this Checksum, while keeping the upper 24 bits unchanged. This represents the final output signal.

Input

The first line contains a positive integer $T$ ($1 \le T \le 4 \times 10^6$), representing the number of test cases.

The following $T$ lines each contain a 32-bit unsigned integer $S$ represented in hexadecimal, prefixed with 0x.

Constraints

• $1 \le T \le 4 \times 10^6$
• $0 \le S \le$ 0xFFFFFFFF
• Please use <stdint.h> and uint32_t to ensure consistent bit-width across different platforms.

Output

For each signal, output the processed 32-bit unsigned integer.

The output must be in hexadecimal format, prefixed with 0x, using uppercase letters, and zero-padded to exactly 8 digits (e.g., 0x0A2B4C6D).

Sample Explanation

• Case 1: 0x00000003 — Binary ends in ...0011. There are adjacent 1s, triggering Rule 1. Output is directly 0xFFFFFFFF.
• Case 2: 0x00000000 — No adjacent 1s. No highest or lowest 1, so Rule 2 does not change the signal ($S_{\text{bridge}} = 0$). For Rule 3, the checksum is 0x00 ^ 0x00 ^ 0x00 ^ 0x00 = 0x00. Replacing the lowest byte yields 0x00000000.
• Case 3: 0x00000008 — Binary is ...1000. No adjacent 1s. Only one 1 (at Bit 3), so no "bits in between". Rule 2 does not change the signal ($S_{\text{bridge}} = \text{0x00000008}$). Checksum is 0x00 ^ 0x00 ^ 0x00 ^ 0x08 = 0x08. Replacing the lowest byte yields 0x00000008.
• Case 4: 0x08000002
  • Rule 1: No adjacent 1s. Passes.
  • Rule 2:
    1. Convert to binary (32 bits): 0000 1000 0000 0000 0000 0000 0000 0010
    2. Find MSB (Most Significant 1): Bit 27; Find LSB (Least Significant 1): Bit 1
    3. Identify the intermediate bits strictly between MSB and LSB: Bit 2 ~ Bit 26 (all currently 0)
    4. Invert all intermediate bits (0 → 1): 0000 1111 1111 1111 1111 1111 1111 1110
    5. Convert back to hex: $S_{\text{bridge}} = \text{0x0FFFFFFE}$
  • Rule 3: Split into bytes: 0x0F, 0xFF, 0xFF, 0xFE. XOR Checksum: 0x0F ^ 0xFF ^ 0xFF ^ 0xFE = 0xF1. Replace lowest byte (0xFE) with 0xF1. Final output: 0x0FFFFFF1.

Sample Input  Download

Sample Output  Download

Discuss

Description

It's a very simple problem.

You are given an initial mysterious string and q queries.

The mysterious string is given in the format d₁|d₂|...|d_m, where each d_i is a decimal integer.

Initialization:

1. Convert each decimal integer d_i into its exact hexadecimal string representation.   (e.g., 20065|16019311|33981975|40140414 -> 4E61|F46F6F|2068617|2647E7E)

2. Concatenate them sequentially to form a single continuous hexadecimal character string S.   (e.g., 4E61|F46F6F|2068617|2647E7E -> 4E61F46F6F20686172647E7E)

Queries:

Each query will be one of the following two operations, operating strictly on the hexadecimal characters (every idx is 0-based):

• Insert idx str:

  First, decode the str (given in the same d_i format) into a hexadecimal string S_Insert using the Initialization rules. Then, insert S_Insert into S at idx.

• Remove idx len:

  Delete exactly len characters from S, starting from idx. (remove characters from idx to idx + len - 1).

Input

The first line contains a single string, representing the initial mysterious string in the format d₁|d₂|...|d_m.

The second line contains an integer q, representing the number of queries.

The following lines describe the q queries.

Constraints:

• 1 <= q <= 100

• d_i is an integer.

• 0 <= idx <= idx + len - 1 <= len(S)

• The length of string S and any mysterious string is guaranteed to never exceed 10000 characters at any given time.

Output

Output the final decoded ASCII string on a single line after processing all queries.

(Note: Every consecutive pair of hexadecimal digits maps to exactly one ASCII character. For example, 4E6F decodes to No.)

Remember to add '\n' at the end of a line.

Sample Input  Download

Sample Output  Download

Discuss

Description

After generating electricity in Japan, you board a plane to Singapore - this time stepping on an aircraft rather than a piezoelectric tile. It is raining outside, so you look outside the Window and see a large billboard running on Linux that says:

Singapore is turning rain into drinking water! Through the NEWater system, rainwater and used water are purified using advanced filtration and UV treatment. This ultra-clean water is then reused for industries and even drinking, helping Singapore reduce dependence on imported water. A smart solution for a water-scarce nation • turning rain into a reliable resource.

You are fascinated by the billboard’s ability to display and manage large amounts of text, so you decide to investigate how its underlying software works.

The system uses a very simple design for storing and editing text:

• A one-dimensional array of strings (effectively a 2D array of characters)

• A separate one-dimensional array len[], where each element stores the length of the corresponding string

Because the developer has not yet implemented null-terminated strings, the system does not rely on any special end-of-string character. Instead, the value in len[i] specifies exactly how many characters is in the i-th string. Any characters beyond this length should be ignored.

As new messages are displayed, the system processes a sequence of queries that modify the stored text.

However, the original source code has been lost. Your task is to reconstruct the missing program and accurately simulate the behavior of this system.

Constraints

• 1 <= n <= 100
• 1 <= q <= 1000
• All strings are initially empty

Input

The first line contains two integers:

N Q

• N — the number of strings

• Q — the number of queries

Each of the next Q lines describes one query in one of the following formats:

0 i c

Append the character c to the end of the i-th string.

1 i s

Append the string s to the end of the i-th string.

2

Print all strings in order from 0 to N-1.

Strings should be separated by newline characters when printed.

Line indices are 0-based.

Output

For every query of type 2, print all N strings.

Each string should appear on its own line.

Ignore the string if it is empty.

Each line should end with a newline.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

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

Discuss

Description

Seeking a new challenge beyond Go, Fujiwara no Sai has recently discovered Chess.

He believes that the fastest way to master any board game is to grasp its ultimate goal—which, in Chess, is the "Checkmate." To sharpen his offensive skills, Sai is analyzing various historical chess puzzles. He wants to know if it is possible to break through the enemy lines and capture the opponent's King in 2 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:

• Q (Queen): Moves any number of vacant squares horizontally, vertically, or diagonally.

• R (Rook): Moves any number of vacant 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.

• B (Bishop): Moves any number of vacant squares diagonally.​

​​

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 2 consecutive moves with his pieces to hunt down the King.

(Note: For simplicity, the movement of the player's Pawns (P) and King (K) is not considered. However, they may still be present on the board and act as obstacles. Furthermore, it is guaranteed that the opponent has exactly one piece: the King.)

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[2];
} GameState;

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

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

const int QUEEN_DIRS[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
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}};
const int BISHOP_DIRS[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

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

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char type, pos_x, pos_y;
        GameState state;
        SearchResult result;
        result.min_steps_to_checkmate = 3;  // 3 indicates it is impossible to capture the King within two 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 == 3) {
            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

The first line contains an integer t, representing the number of test cases. 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 <= t <= 1000000

• 1 <= p <= 16

• o = 1

Testcase Design:

• Testcase 1: Queen

• Testcase 2: Rook

• Testcase 3: Knight

• Testcase 4: Bishop

• Testcase 5~8: Unlimited

Output

For each test case:

• If the opponent's King can be captured in 2 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 2 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

Discuss

Description

In the Continental Magic Association, n mages are undergoing the First-Class Mage Exam. Each mage has a mana value represented by an integer ranging from -99 to 99. The Great Mage Serie, intending to prevent Frieren from passing easily, wants to evaluate the mages from multiple complex perspectives and will issue q queries. Each query specifies a different sorting rule.

Your task is to sort the mages based on the rule specified in the query. If a tie occurs under any rule, you should resolve it by sorting the mages' names in ascending lexicographical (alphabetical) order.

The q queries will be represented by an integer rule (from 0 to 4), corresponding to the following sorting rules:

• Rule 0 (Ascending): Sort mages by their power value in ascending order.

• Rule 1 (Square Ascending): Sort mages by the square of their power value in ascending order.

• Rule 2 (Digit Sum Ascending): Sort mages by the sum of their power value's digits in ascending order (ignoring the negative sign). For example, the digit sum of -85 is 8 + 5 = 13.

• Rule 3 (Swapped Digit Ascending): Swap the tens digit and the units digit of the power value, and sort in ascending order. For example, 78 becomes 87, -6 becomes -60.

• Rule 4 (Prime First Ascending): Take the absolute value of each mage's power value. If this absolute value is a prime number (e.g., 2, 3, 5...), the mage must be placed at the front. The remaining mages are placed behind. Within the prime and non-prime groups, sort them by their original power value in ascending order.

Input

The first line contains two integers n and q, representing the number of mages and the number of queries.

The next n lines each contain a string name and their value.

The next q lines each contain a single integer rule, representing the sorting rule for that query.

Constraints:

• 1 <= n, q <= 100

• len(name) < 30

• -99 <= value <= 99

Testcase Design:

• Testcase 1~2: Rule 0, 1

• Testcase 3~4: Rule 0, 1, 2

• Testcase 5~8: Rule 0, 1, 2, 3, 4

Output

For each query, output the sorted names of the mages.

Remember to add '\n' at the end of every line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss