Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1342
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1342
Dice
By Ricardo Anido e Rodrigo Schmidt 
Brazil
Timelimit: 1
A simple boardgame that generations of children have played consists of a board containing a trail of squares and a set of colored pieces. At the beginning of the game each player is assigned a piece; all pieces are initially positioned right before the first square of the trail.
The game proceeds in rounds. At each round, players rolls a pair of dice, and move their pieces forward a number of squares equal to the rolled result. Players roll the dice always in the same order (player A, then player B, etc.) in the rounds.
Most of the squares on the board are plain squares, but some are “traps”. If a player’s piece falls on a trap square at the end of the player’s move, the player misses the next round. That is, he/she does not roll the dice, and his/her piece stays one round without moving.
There will be exactly three traps on the trail.
The winner of the game is the player whose piece reaches the end of the trail first. The end of the trail is after the last square of the board. Consider, for example, the board in the figure above, which has squares numbered from 1 to 48. At the start, the pieces are positioned at the place marked ‘Begin’ in the figure, that is, before the square number 1. Therefore, if a player rolls a 7 (dice showing 2 and 5 for example), his/her piece is positioned at square number 7 at the end of the first round of the game. Furthermore, if a player’s piece is positioned at square 41, the player needs a roll result of at least 8 to reach the end of the trail and win the game. Notice also that there will be no draw in the game.
It will be given to you the number of players, the number of squares in the trail, the location of the traps and a list of dice rolls results. You must write a program that determines the winner.
Input
Your program should process several test cases. The first line of a test case contains two integers P and S representing respectively the number of players and the number of squares in the trail (1 <= P <= 10 e 3 <= S <= 10000). The second line describes the traps, represented by three distinct integers T1, T2 and T3, denoting their positions in the trail (1 <= T1, T2, T3 <= S). The third line contains a single integer N indicating the number of dice rolls in the test. Each of the following N lines contain two integers D1 and D2 (1 <= D1, D2, <= 6), representing the results of the dice rolls. The end of input is indicated by P = S = 0. The set of dice roll results in a test will be always the exact number necessary for a player to win the game.
A player is identified by a number from 1 to P. Players play in a round in sequential order from 1 to P.
The input must be read from standard input.
Output
For each test case in the input, your program should output a single integer: the number representing the winner.
The output must be written to standard output.
| Sample Input | Sample Output |
|
2 10 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
int squares[10100], visited[10100], v = 1;
const int INF = INT_MAX;
int main()
{
ios::sync_with_stdio(false);
int p, s, n; //number of players, squares, dices
int t[3], d[2];
while (cin >> p >> s && p + s) {
memset(squares, 0, sizeof squares);
int player = 1;
for (int i = 0; i < 3; i++) {
cin >> t[i];
}
cin >> n;
int winner = 0;
for (int k = 0; k < n; k++) {
if (visited[player] == v) {
visited[player] = 0;
player = (player % p) + 1;
k--;
continue;
}
for (int i = 0; i < 2; i++)
cin >> d[i];
if (winner)
continue;
squares[player] += d[0] + d[1];
if (squares[player] == t[0] || squares[player] == t[1] || squares[player] == t[2])
visited[player] = v;
else if (squares[player] > s)
winner = player;
//after a turn
player = (player % p) + 1;
}
v++;
cout << winner << "\n";
}
return 0;
}
Input
2 4 8
4
1 1 3 4
1 2
6 5
3 7
4 5 7
7
1 2
2 2
2 1
1 1
1 2
1 1
1 1
0 0
Output
3