Musical Bench

Simulate a musical bench game where players move between benches in a circle based on music duration and player speed, eliminating players when benches are removed.

Understand the Problem

Problem Statement

A group of P players are playing a musical bench game with B benches arranged in a circle. Each player has a unique ID, an initial bench position, and a time T(i) to move between adjacent benches. The game runs for M rounds where music is played for varying durations M(i). Players move continuously while music plays. After each round, one bench is removed along with any players on it. Determine which players remain and their final bench positions.

Constraints

2 ≤ B, P ≤ 100 (number of benches and players)
M ≤ B (number of rounds)
Music duration is a common multiple of all player times
Bench positions are numbered 1 to B
Players move at constant speed between benches

Examples

Example 1

Input

10 6
100 200 300 400 500 600
2 3 4 2 5 3
9 8 9 5 2 1
5
60 120 180 60 60
4 5 3 6 7

Output

100:10 200:9 600:1

Explanation

After 5 rounds of movement and bench removals, players 100, 200, and 600 remain on benches 10, 9, and 1 respectively. Player 100 moved from bench 9 to 10, player 200 stayed on bench 9, and player 600 moved from bench 1 through the circle to end on bench 1.

Example 2

Input

6 4
100 200 300 400
2 4 6 2
2 3 5 1
4
48 36 12 24
1 2 3 5

Output

-1

Explanation

All players are eliminated after 4 rounds as benches 1, 2, 3, and 5 are removed, leaving no benches for the players to occupy.

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    int b, p;
    scanf("%d %d", &b, &p);
    
    int id[p];
    for(int i = 0; i < p; ++i) {
        scanf("%d", &id[i]);
    }
    
    int playersTime[p];
    for(int i = 0; i < p; ++i) {
        scanf("%d", &playersTime[i]);
    }
    
    int position[p];
    for(int i = 0; i < p; ++i) {
        scanf("%d", &position[i]);
    }
    
    int rounds;
    scanf("%d", &rounds);
    
    int roundTime[rounds];
    for(int i = 0; i < rounds; ++i) {
        scanf("%d", &roundTime[i]);
    }
    
    int benchRem[rounds];
    for(int i = 0; i < rounds; ++i) {
        scanf("%d", &benchRem[i]);
    }
    
    int isBenchRemoved[101] = {0};
    
    for(int rnd = 0; rnd < rounds; ++rnd) {
        // Move players based on music duration
        for(int i = 0; i < p; ++i) {
            if(isBenchRemoved[position[i]]) continue;
            
            int jumps = roundTime[rnd] / playersTime[i];
            int pos = position[i];
            
            while(jumps > 0) {
                pos++;
                if(pos == b + 1) {
                    pos = 1;
                }
                if(!isBenchRemoved[pos]) jumps--;
            }
            position[i] = pos;
        }
        
        // Remove the specified bench
        isBenchRemoved[benchRem[rnd]] = 1;
    }
    
    // Output remaining players
    int counter = 0;
    for(int i = 0; i < p; ++i) {
        if(!isBenchRemoved[position[i]]) {
            printf("%d:%d ", id[i], position[i]);
            counter = 1;
        }
    }
    
    if(counter == 0) printf("-1");
    
    return 0;
}

Time:O(M × P × B) where M is rounds, P is players, and B is benches. In worst case, each player might need to check all benches to find valid positions.

Space:O(P + B) for storing player data and bench removal status.

Approach:

C Solution Explanation:

Input Reading: Read B, P, player data, rounds, and bench removal sequence
State Tracking: Use arrays to track player positions and which benches are removed
Simulation Loop: For each round:
- Calculate moves per player = music duration ÷ player time
- Move each player around circle, skipping removed benches
- Remove specified bench
Output: Print remaining players with their bench positions, or -1 if none remain

The algorithm efficiently simulates the circular movement while accounting for removed benches.

Visual Explanation

Loading diagram...

All Problems