Problem 1: Ring Position Simulation

Description:

There are $2n$ people standing in two rings of size $n$ each. They are numbered from $1$ to $2n$, where positions $1$ to $n$ form ring 1 and positions $n+1$ to $2n$ form ring 2.

Both rings start counting from $1$ simultaneously. Ring 1 starts from person $1$, and ring 2 starts from person $n+1$. Counting proceeds cyclically through the initial positions.

Whenever the reported number is a multiple of $m$, the two people at the corresponding positions in both rings swap places.

Given $n$, $m$, and $k$, determine which person stands at each initial position after counting reaches $k$.

Input:

• $n$ ($1 \le n \le 1000$): number of people in each ring
• $m$ ($1 \le m \le 1000$): swap threshold
• $k$ ($1 \le k \le 10^6$): final counted number

Output:

• Print $2n$ integers: the person number at each initial position after counting reaches $k$

Solution Approach:

Use two arrays to represent the two rings. Simulate the counting process directly. When the current number is a multiple of $m$, perform the swap operasion at the corresponding positions. Since positions wrap around cyclically, use modulo arithmetic to determine the correct indices.

Key handling for wraparound:

• When $l \le n$: direct index access
• When $l > n$: use $l % n$ to find the actual position
• Special case when $l % n == 0$: position is $n$

Reference Implementation:

#include <bits/stdc++.h>
using namespace std;

int a[1000010], b[1000010];

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    
    for (int i = 1; i <= n; i++) {
        a[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        b[i] = n + i;
    }
    
    int l = 1;
    while (l <= k) {
        if (l % m == 0) {
            int idx;
            if (l <= n) {
                idx = l;
            } else if (n != 1 && l % n != 0) {
                idx = l % n;
            } else if (n == 1) {
                idx = 1;
            } else {
                idx = n;
            }
            int temp = a[idx];
            a[idx] = b[idx];
            b[idx] = temp;
        }
        l++;
    }
    
    for (int i = 1; i <= n; i++) {
        cout << a[i] << ' ';
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << ' ';
    }
    return 0;
}

Problem 2: Simple Game

Description:

Alice and Bob play a game on a sequence $a_1, a_2, \ldots, a_n$. Players take turns removing integers from the sequence, with Alice moving first. When the sequence is empty, Alice has collected integers summing to $S_1$, and Bob has collected integers summing to $S_2$.

Alice wins if $|S_1 - S_2|$ is odd; otherwise, Bob wins. Both players play optimally.

Input:

• $n$ ($1 \le n \le 10^6$): sequence length
• $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$): sequence elements

Output:

• Print "Alice" if Alice wins, otherwise print "Bob"

Solution Approach:

Analysis of parity properties:

• Even - Even = Even
• Even - Odd = Odd
• Odd - Even = Odd
• Odd - Odd = Even

Key observations:

1. If all numbers are even, the difference is always even regardless of choices → Bob wins.
2. If odd numbers exist, consider two cases:
   • Even number of odds: With optimal play, both players end up with equal numbers of odd values. Since odd + odd = even, Bob can always win by mirroring Alice's choices.
   • Odd number of odds: The final difference will be odd regardless of strategy.

The solution reduces to checking the count of odd numbers in the sequence.

Reference Implementation:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int oddCount = 0;
    
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (x % 2 == 1) {
            oddCount++;
        }
    }
    
    if (oddCount % 2 == 0) {
        cout << "Bob";
    } else {
        cout << "Alice";
    }
    return 0;
}