Eeny Meeny (Josephus / Queue)

Problem:
https://open.kattis.com/problems/eenymeeny

This problem simulates choosing kids for two teams using a counting rhyme.
Starting from the front of the line, you count k words and the k-th kid is selected.
The process continues, alternating picks between team 1 and team 2, until no kids remain.

This is a classic queue (Josephus) simulation problem.

💡 Approach

We use:

• A queue (collections.deque) to model the line of kids
• Rotation to simulate counting:
  • For k-1 steps: move the front kid to the back (popleft() then append())
  • The next kid at the front is the k-th → remove them and assign to a team
• Alternate picks:
  1. Rotate and pick for team 1
  2. If anyone remains, rotate and pick for team 2
• Continue until the queue is empty

Time complexity: O(n · k) (each pick may rotate up to k-1 times)

# 1.6 https://open.kattis.com/problems/eenymeeny

import sys
from collections import deque
#sys.stdin = open('test.txt','r')

k = len(sys.stdin.readline().split())
n = int(sys.stdin.readline())
queue = deque()

for _ in range(n):
    queue.append(sys.stdin.readline().strip())

team1, team2 = [], []  # Lists to hold kids in each team

while queue:
    # Simulate counting through the rhyme for team 1
    for _ in range(k - 1):
        # Move the kid from the front to the back of the queue
        queue.append(queue.popleft())

    # Add the k-th kid to team 1
    team1.append(queue.popleft())

    # If kids remain, repeat for team 2
    if queue:
        for _ in range(k - 1):
            queue.append(queue.popleft())
        team2.append(queue.popleft())

# Output the results
print(len(team1))
for name in team1:
    print(name)

print(len(team2))
for name in team2:
    print(name)