ICPC 2026 Thailand (Southern Region) Solutions

A

Median Person

// CONDITIONAL_SORT

⏱️ 1.0s 💾 256MB

Problem Statement

Three students each took an exam and received a score. Every score is a different integer, so exactly one student scored higher than exactly one other and lower than the remaining one — that student's score is the median: it is neither the highest nor the lowest of the three.

Given the three students' names and their scores, determine the name of the student who scored the median.

Input Format

Line 1: Three names separated by single spaces (lowercase English letters).
Line 2: Three integers separated by single spaces (scores between 0 and 100, pairwise distinct).

Output Format

Print a single line containing the name of the student whose score is the median of the three.

Sample Testcases

Input 1

ann bob cid
5 2 8

Output 1

ann

Input 2

x y z
8 5 2

Output 2

Note: In sample 1, ann = 5, bob = 2, cid = 8. The median score 5 belongs to ann.

C++ Solution (A.cpp)

#include <iostream>

using namespace std;

int main()
{
    string name[3];
    int score[3];

    cin >> name[0] >> name[1] >> name[2];
    cin >> score[0] >> score[1] >> score[2];

    if((score[1] > score[2] && score[1] < score[0]) || (score[1] < score[2] && score[1] > score[0]))
    {
        cout << name[1] << endl;
    }
    else if((score[0] < score[2] && score[0] > score[1]) || (score[0] > score[2] && score[0] < score[1]))
    {
        cout << name[0] << endl;
    }
    else
    {
        cout << name[2] << endl;
    }
    return 0;
}

Approach Explanation:

We store the 3 names and 3 scores into parallel arrays. We check if score[1] lies strictly between score[0] and score[2]. If so, index 1 is the median. Otherwise, if score[0] lies between score[1] and score[2], index 0 is the median. In all remaining cases, index 2 is the median.

B

Holy Triangle Talisman

// GEOMETRY_INEQUALITY

⏱️ 1.0s 💾 256MB

Problem Statement

Jack bought three holy bamboos. Each bamboo initially had length A units. Since then, the bamboos have experienced 0, 1, and 2 moonrises respectively. Whenever a moonrise occurs, a bamboo grows by B units.

The lengths of the three bamboos are therefore A, A + B, and A + 2B. To fend off an invasion using a Holy Circle Talisman, Jack must arrange the three bamboos so that their tips connect to form a valid non-degenerate triangle. Determine whether the three bamboos can form a triangle.

Input Format

Single line containing two integers A and B (1 ≤ A, B ≤ 500).

Output Format

Print Yes if the three bamboos can form a triangle, or No otherwise.

Sample Testcases

Input 1

3 1

Output 1

Yes

Input 2

1 2

Output 2

No

Note: Three side lengths x, y, z form a valid triangle if and only if the sum of any two lengths is strictly greater than the remaining length. Since side A + 2B is the longest, the condition simplifies to A + (A + B) > A + 2B, which simplifies to 2A + B > A + 2B (or A > B).

C++ Solution (B.cpp)

#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    if(2 * a + b > a + b * 2)
    {
       cout << "Yes";
    }
    else
    {
        cout << "No";
    }
    return 0;
}

Approach Explanation:

The triangle inequality requires the sum of the two shorter sides A and A+B to exceed the longest side A+2B. We evaluate 2*A + B > A + 2*B and output "Yes" or "No" accordingly.

C

Movie Seat

// STRING_TRAVERSAL

⏱️ 1.0s 💾 256MB

Problem Statement

The front row of a movie theater consists of seats arranged in a straight line represented by a string S:

x indicates that the seat is occupied by another guest.
o indicates that the seat is currently empty.

You want to sit in an empty seat (o) without disturbing anyone. You can only pick an empty seat whose adjacent seats (if they exist) are also empty. Determine how many seats in the row you can choose from.

Input Format

Single string S (1 ≤ |S| ≤ 5000), representing the arrangement of seats in the front row.

Output Format

Print a single integer: the number of valid empty seats you can choose to sit on.

Sample Testcases

Input 1

ooxoooooxo

Output 1

Input 2

xoxx

Output 2

Note: In sample 1, seats at index 1, 5, and 6 (1-indexed) are empty and surrounded only by empty seats, yielding 3 valid choices.

C++ Solution (C.cpp)

#include <iostream>

using namespace std;

int main()
{
    string seat;
    int sum = 0, len;
    cin >> seat;
    len = seat.size();
    int lenindex = len - 1;

    if(len == 1)
    {
        if(seat[0] == 'O' || seat[0] == 'o')
        {
            cout << 1;
        }
        else
        {
            cout << 0;
        }
        return 0;
    }

    // Check first seat
    if((seat[0] == 'O' || seat[0] == 'o') && (seat[1] == 'O' || seat[1] == 'o'))
    {
        sum++;
    }
    // Check last seat
    if((seat[lenindex-1] == 'O' || seat[lenindex-1] == 'o') && (seat[lenindex] == 'O' || seat[lenindex] == 'o'))
    {
        sum++;
    }

    // Check middle seats
    if(len > 2)
    {
        for(int i = 1; i < lenindex; i++)
        {
            if((seat[i] == 'O' || seat[i] == 'o') && 
               (seat[i-1] == 'O' || seat[i-1] == 'o') && 
               (seat[i+1] == 'O' || seat[i+1] == 'o'))
            {
                sum++;
            }
        }
    }
    cout << sum;
    return 0;
}

Approach Explanation:

We inspect boundary cases separately: index 0 requires index 1 to be empty; the last index requires the second-to-last index to be empty. For middle indices 1..len-2, a seat is valid if it and both its left and right neighbors are empty.

D

Leftover

// GREEDY_OPTIMIZATION

⏱️ 1.0s 💾 256MB

Problem Statement

Captain Tsubasa and his pirate crew discovered N treasure chests containing A₁, A₂, ..., A_N gold coins.

However, they are short by exactly one crew member! Each pirate can carry at most 1 chest, so exactly 1 chest must be left behind. Gold coins cannot be split between chests. Calculate the maximum total number of gold coins the crew can carry back to the ship.

Input Format

Line 1: Integer N (2 ≤ N ≤ 100).
Line 2: N integers A₁, A₂, ..., A_N (1 ≤ A_i ≤ 1000).

Output Format

Print a single integer: the maximum total gold coins carried by the N - 1 crew members.

Sample Testcases

Input 1

5
3 6 7 4 6

Output 1

Note: Leaving behind the smallest chest (3 gold coins) yields 6 + 7 + 4 + 6 = 23 coins, which maximizes the sum.

C++ Solution (E.cpp)

#include <iostream>

using namespace std;

int main()
{
    int n, sum, mi, tmp;
    cin >> n;
    cin >> mi;
    sum = mi;
    for(int i = 1; i < n; i++)
    {
        cin >> tmp;
        sum += tmp;
        if(tmp < mi)
        {
            mi = tmp;
        }
    }
    cout << sum - mi;
    return 0;
}

Approach Explanation:

To maximize the total gold coins carried by selecting N-1 chests, we greedily discard the chest with the minimum number of gold coins. We track the running total sum and minimum chest mi, then print sum - mi.

E

No lemon, no melon

// PALINDROME_CONSTRUCTION

⏱️ 1.0s 💾 256MB

Problem Statement

Hannah is a math professor obsessed with palindromes. Your friend has prepared A lemons. You want to buy B melons such that the total number of fruits A + B is a numeric palindrome.

Given A (1 ≤ A ≤ 10¹²), find a valid B (1 ≤ B ≤ 10¹²) such that A + B reads the same forwards and backwards.

Input Format

Single line containing an integer A (1 ≤ A ≤ 10¹²).

Output Format

Print a single integer B (1 ≤ B ≤ 10¹²). If multiple valid answers exist, print any.

Sample Testcases

Input 1

Output 1

Input 2

998244353

Output 2

Note: For 67, 67 + 10 = 77 (palindrome). For 998244353, 998244353 + 1755646 = 999999999 (palindrome).

(Unsolved)C++ Solution (E_Palindrome.cpp)

#include <iostream>
#include <string>

using namespace std;

int main()
{
    long long A;
    if (!(cin >> A)) return 0;

    // Construct a target palindrome P > A made of all 9s
    string s = to_string(A);
    long long target = 0;
    for (size_t i = 0; i < s.length(); ++i) {
        target = target * 10 + 9;
    }

    // If A is already all 9s, pick the next repdigit 99...9 with 1 extra digit
    if (target <= A) {
        target = target * 10 + 9;
    }

    long long B = target - A;
    cout << B << endl;
    return 0;
}

(Unsolved)Approach Explanation:

(No one is able to solve this question)Any repdigit number consisting of all 9s (e.g. 99, 999, 9999) is guaranteed to be a palindrome. For any number A, we construct a number target = 99...9 with length equal to A (or one greater if A is already 99...9). Then B = target - A satisfies 1 ≤ B ≤ 10¹² and A + B = 99...9 (a palindrome).

F

Upscaling

// GRID_TRANSFORMATION

⏱️ 1.0s 💾 256MB

Problem Statement

An original image of resolution N × M pixels is upscaled by an integer factor K. Each original pixel expands into a K × K block, producing an upscaled grid of size (N · K) × (M · K).

You crop the upscaled image from row r1 to r2 and column c1 to c2. Compute the number of distinct pixels from the original image that overlap with the cropped area.

Input Format

Line 1: T (1 ≤ T ≤ 10⁴) testcases.
Each testcase contains 7 integers: N M K r1 c1 r2 c2.

Output Format

For each testcase, print the number of distinct original pixels in the crop region.

Sample Testcases

Input 1

1
3 3 3 2 4 5 7

Output 1

C++ Solution (F.cpp)

#include <iostream>

using namespace std;

int main()
{
    int t;
    int n, m, k, r1, c1, r2, c2;
    int r11, c11, r22, c22;
    cin >> t;
    int result[t];
    for(int i = 0; i < t; i++)
    {
        cin >> n >> m >> k >> r1 >> c1 >> r2 >> c2;

        r11 = (r1 - ((r1 - 1) % k) - 1) / k;
        c11 = (c1 - ((c1 - 1) % k) - 1) / k;
        r22 = (r2 + ((k - (r2 % k)) % k)) / k;
        c22 = (c2 + ((k - (c2 % k)) % k)) / k;

        result[i] = (c22 - c11) * (r22 - r11);
    }
    cout << result[0];
    for(int i = 1; i < t; i++)
    {
        cout << endl << result[i];
    }
    return 0;
}

Approach Explanation:

Each original pixel spans K rows and K columns in the upscaled grid. The 1-indexed row r belongs to original row index (r - 1) / K. By mapping r1, r2 and c1, c2 to original block boundaries, the number of distinct original rows is (r22 - r11) and columns is (c22 - c11). The answer is their product.

G

EV Charging

// TWO_POINTERS_GREEDY

⏱️ 2.0s 💾 256MB

Problem Statement

An EV charging station has N reservation requests. The i-th request asks to charge starting at time t_i.

Due to hardware limitations, a single charging head cannot be used for two requests if their start times are separated by D hours or less (i.e. if b > a, then b - a > D is required). Determine the minimum number of charging heads required to satisfy all requests.

Input Format

Line 1: Integers N and D (1 ≤ N ≤ 2·10⁵, 0 ≤ D ≤ 10⁹).
Line 2: N integers t₁, t₂, ..., t_N (0 ≤ t_i ≤ 10⁹).

Output Format

Print a single integer: the minimum number of charging heads required.

Sample Testcases

Input 1

6 2
3 1 2 8 7 3

Output 1

Input 2

4 5
100 1 50 3

Output 2

Note: In sample 1, sorted times are 1, 2, 3, 3, 7, 8 with D = 2. Head 1 takes {1, 7}; Head 2 takes {2, 8}; the two requests at 3 require their own heads, making 4 heads total.

C++ Solution (G.cpp)

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, d;
    cin >> n >> d;
    int car[n];

    for(int i = 0; i < n; i++)
    {
        cin >> car[i];
    }

    sort(car, car + n);

    int starttime, endtime, maxuse = 1, hit = 1;
    for(int i = 0; i < n; i += hit)
    {
        hit = 1;
        endtime = car[i] + 1 + d;
        for(int j = i + 1; j < n && car[j] < endtime; j++)
        {
            hit++;
        }
        if(maxuse < hit)
        {
            maxuse = hit;
        }
    }
    cout << maxuse;
    return 0;
}

Approach Explanation:

We first sort all start times. Any two requests whose start times differ by ≤ D cannot share a charging head. Thus, the minimum number of heads needed equals the maximum number of requests that fall within a window of length D. We scan the sorted list to find the maximum count of overlapping requests.