Winning the Lottery
Write a C assignment where the state of Florida has come up with a new way to determine lottery winners. The system is outlined as follows:
Phase 1
Each person eligible to win is placed in one of the G groups. For each group, a process is used to narrow down the possible number of winners. The process is as follows:
Let a group initially start with p people. We can number the people within a group from 1 to p and assume they are arranged in a circle, with 1, then 2, …, then p, followed by 1. Each group has its own skip number, s, and its own threshold number, t, where t < p. To eliminate some people in a group from the possibility of winning the lottery, start at the person labeled 1 and skip overs people in line. Then, remove the following person. (Thus the first person removed is always person number s+1.) Then repeat the process. Since the line is circular, once you pass the highest-numbered person left in line, you'll continue to the lowest numbered person left in line. Continue eliminating people in this fashion until there are precisely t people left.
Phase 2
Of all of the people left, the winner of the lottery will be the lowest-numbered person from any group. If there are multiple people from different groups with the same lowest number, then the person from the lowest group number is chosen as the lottery winner.
The state started forcing people to come out and form lines doing the process as described, but this was extremely time-consuming and they got many complaints from the losers who were forced to stand out in a big hot field for many hours before they got eliminated (some of those officials in Tallahassee aren't fast counting around circles…)
Now, the state has decided to hire you to simulate the process and determine who the winner will be without actually forcing all participants from standing around in circles! Don't let the state officials down!
The Problem
Given a list of the number of groups, the initial sizes of each group, the skip value for each group, and the threshold value for each group, determine the winner of the lottery (group number and person number).
Sample Input
1
5
10 2 2
8 1 1
7 2 3
5 1 3
9 1 4
Sample Output
Group #1:
3
6
9
2
7
1
8
5
Group #2:
2
4
6
8
3
7
5
Group #3:
3
6
2
7
Group# 4:
2
4
Group #5:
2
4
6
8
1
The lottery winner is person 1 from group 2
Solution:
#include < stdio.h>
#include < stdlib.h>
/* A node that is used to build a linked list */
typedef struct node_s
{
int value;
struct node_s *next;
struct node_s *previous;
} node_t;
/* Structure to hold a circular linked list */
typedef struct list_s
{
node_t *current;
int size;
} list_t;
/* Print the content of the linked list for debugging purposes only */
void print_list(list_t *list)
{
int i;
for (i = 0; i < list->size; i++)
{
printf("%d ", list->current->value);
list->current = list->current->next;
}
}
/* Initialize a new list with a given size, the elements are numbered from 1 to size */
void initialize_list(list_t *list, int size)
{
node_t *node;
int i;
list->current = NULL;
list->size = 0;
for (i = 1; i <= size; i++)
{
/* Create the node */
node = (node_t *) malloc(sizeof(node_t));
node->value = i;
node->next = NULL;
node->previous = NULL;
if (list->size == 0)
{
/* Case for an empty list */
list->current = node;
list->current->next = list->current;
list->current->previous = list->current;
}
else
{
/* Case for non-empty list, put new node at the tail */
node->next = list->current;
node->previous = list->current->previous;
list->current->previous->next = node;
list->current->previous = node;
}
list->size++;
}
}
/* Deallocate the list */
void free_list(list_t *list)
{
int i;
node_t *next;
for (i = 0; i < list->size; i++)
{
next = list->current->next;
free(list->current);
list->current = next;
}
list->current = NULL;
list->size = 0;
}
/* Find the smallest value in the list */
int find_min_value(list_t *list)
{
int i;
int min_value;
min_value = -1;
for (i = 0; i < list->size; i++)
{
if (i == 0 || list->current->value < min_value)
min_value = list->current->value;
list->current = list->current->next;
}
return min_value;
}
/* Process the group's linked list */
int process_group()
{
int i, winner;
int size, skips, limit;
list_t list;
node_t *current;
/* Load the configuration of the list */
scanf("%d %d %d", &size, &skips, &limit);
initialize_list(&list, size);
/* Keep eliminating nodes until the limit has been reached */
do
{
/* Do some skips */
for (i = 0; i < skips; i++)
list.current = list.current->next;
/* Eliminate the current node */
current = list.current;
current->previous->next = current->next;
current->next->previous = current->previous;
list.current = current->next;
list.size--;
printf("%d\n", current->value);
free(current);
} while (list.size > limit);
/* The winner in the group is the person who holds the smallest value */
winner = find_min_value(&list);
free_list(&list);
return winner;
}
/* Answer the next case */
void process_next_case()
{
int group_number_winner;
int person_number_winner;
int temp_person_number_winner;
int num_groups;
int i;
group_number_winner = -1;
person_number_winner = -1;
/* Process each group */
scanf("%d", &num_groups);
for (i = 1; i <= num_groups; i++)
{
printf("Group #%d:\n", i);
temp_person_number_winner = process_group();
/* For each group, the winner is the person who has the smallest number */
if (i == 1 || temp_person_number_winner < person_number_winner)
{
person_number_winner = temp_person_number_winner;
group_number_winner = i;
}
}
/* Display the final winner for this case */
printf("Lottery winner is person %d from group %d.\n",
person_number_winner,
group_number_winner);
}
/* Entry point of the program */
int main(int argc, char *argv[])
{
int num_cases;
int i;
/* Process each case */
scanf("%d", &num_cases);
for (i = 0; i < num_cases; i++)
process_next_case();
return 0;
}