******MUST BE IN STDIO STDLIB MATH.H********* Risk1000000: In the board game Ris
ID: 3674203 • Letter: #
Question
******MUST BE IN STDIO STDLIB MATH.H*********
Risk1000000: In the board game Risk, a group of armies will attack from one country to another. To simulate the battle, both teams roll dice. The number of dice vary from attack to attack. To "score" the battle, you match the highest roll of the attacker with the highest roll of the defender. If the attacker's roll is greater than the defender's roll, then the defender loses an army. Otherwise, the attacker loses an army. The comparisons continue, between the attacker's second highest roll and the defender's second highest roll. Recently, a new game, Risk1000000, similar to Risk, has been released that allows for megabattles of up to 1,000,000 armies versus 1,000,000 armies. Also, rather than simulating a battle with a die roll, an army's strength can be any number from 1 to a billion (instead of 1 through 6 for a die roll). One final difference in Risk1000000 is that it gives the defenders an extra advantage. Instead of lining up the highest attacking die with the highest defending die and so forth, the attacker must position his armies for each battle and show this information to the defender. The defender can then choose any ordering of her armies.
To see the difference, let's consider an example from regular Risk and a couple examples from Risk1000000. In the original game Risk, if an attacker with two armies rolls a 6 and 3, while a defender rolls a 5 and a 2, we must match the two maximum rolls (6 versus 5) and the two minimum rolls (3 verses 2), which results in the defender losing two armies.
If we were to have the same situation in Risk1000000, the defender would see that the attacker has 6 for its first army and 3 for his second army. The defender can then strategically place the 2 for her first army and the 5 for her second army, resulting in the loss of one defending army and one attacking army.
Consider a slightly larger situation where the attacker had the following values for its armies showing:
18 9 21 5 3 27 15
Imagine that the defender's army values are:
15 8 6 2 25 19 20
If the defender kept this original ordering, she'd only win two battles (25 versus 3 and 20 versus 15).
An optimal rearrangement of armies for the defender is as follows:
19 15 25 6 8 2 20 versus
18 9 21 5 3 27 15
where the defender wins all but one battle, incurring the loss of just one army (in the 27 versues 2 battle) while the attacker would lose six armies.
The Problem
Write a program that, given a list of the values of both the attackers armies and defenders armies, determines the maximum number of attacking armies that can be defeated by the defender, if she plays optimally.
The Input (read from standard input)
The first line of input will contain a single positive integer, c (c 100), representing the number of input cases. The first line of each input case will contain a single integer, n (n 106 ), representing the number of armies battling from each side. The next n lines of the input case will contain a single integer each, representing the value of one of the attacking armies. The following n lines of the input case will contain a single integer each, representing the value of one of the defending armies. All of the values on these 2n lines will be positive integers less than or equal to one billion.
The Output (to standard out)
For each input case, output a single integer, on a line by itself, representing the maximum number of attacking armies that can be defeated by the defender.
Sample Input Sample Output
2 1
2 2
3
6
5
2
3
2
3
12
9
3
4
Implementation Detail - Sorting (must implement either Merge Sort or Quick Sort) The goal of this problem is to practice coding either Merge Sort or Quick Sort. Significant credit will be given only if your solution contains an implementation of one of these sorts. Thus, if you use C's built in sorting function or solve the problem without sorting values, you will lose significant credit, even if your solution is correct. Please write your own implementation of the sort you choose instead of copying the one on the course web page or copying one from online. The whole point of this assignment is to give you the critical experience of implementing an efficient sorting algorithm on your own, as every beginning computer science student before you has done. While there may be other ways to solve this problem, the grading criteria will include points for implementing one of the two aforementioned sorts, sorting both sets of input with them, and then processing that sorted input in either O(n) or O(nlgn) time, using a greedy strategy that always obtains the optimal answer. (Note that while the optimal answer is unique, optimal orderings are not; there may be multiple orderings for a case that achieve the optimal outcome for the defender.)
Explanation / Answer
/* C program To create an algorithm that finds the maximum number of armies that are defeated by the defender. */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ARMY_MAX 1000000
#define ARMY_POW_MAX 1000000000
//struct def
struct Battle_data{
int no_armies; //max 1,000,000
int *army_power_atk; //max 1,000,000,000
int *army_power_def; //max 1,000,000,000
};
//top level functions-----------------
void input(struct Battle_data *data);
int logic(struct Battle_data *data);
void output(int i);
//------------------------------------
//input level functions-------------------------------------------------------------
void get_int(int *i);
void load_array(int arr[], int size);
void load_struct(int atk[], int def[], int size, struct Battle_data *data, int i);
//----------------------------------------------------------------------------------
//logic level functions--------------------------------------------------------------------------------
int *sort_arr(int *pInt, int first_index, int last_index);
int compare(int *atk, int *def, int top_atk, int top_def, int i);
int partition(int *pInt, int first_index, int last_index);
void swap(int *i, int *j);
//-----------------------------------------------------------------------------------------------------
int main() {
//struct init
struct Battle_data data;
data.army_power_atk = malloc(sizeof(int) * ARMY_POW_MAX);
data.army_power_def = malloc(sizeof(int) * ARMY_POW_MAX);
data.no_armies = 0;
//main variables
int input_cases = 0;
int i;
int score;
//scans in input cases (first value)
scanf("%d", &input_cases);
//loads input cases and proceeds with input.
for (i = 0; i < input_cases; i++) {
//to input
input(&data);
//collect score from logic
score = logic(&data);
printf(" ");
//printf to screen
output(score);
printf(" ");
}
free(data.army_power_atk);
free(data.army_power_def);
return 0;
}
//----------------------------------------------------------------------------------------------------------------------
void input(struct Battle_data *data) {
/*input() - collect all input from *.in file. and organize according to program needs. */
//init army size
int army_size = 0;
//gets army_size from stdin
get_int(&army_size);
//init army power values for attack and defense
int army_pow_val_atk[army_size];
int army_pow_val_def[army_size];
//loads array with stdin
load_array(army_pow_val_atk, army_size);
load_array(army_pow_val_def, army_size);
//loads struct with values collected from load_array()
load_struct(army_pow_val_atk, army_pow_val_def, army_size, data, 0);
}
void load_struct(int atk[], int def[], int size, struct Battle_data *data, int i) {
/*load_struct() - function load_struct() takes values from array and places them inside struct for better management
* and readability*/
if(i < size) {
data->army_power_atk[i] = atk[i];
data->army_power_def[i] = def[i];
data->no_armies = size;
load_struct(atk, def, size, data, i + 1);
}
}
void load_array(int arr[], int size) {
/*load_array() - loads array with values collected from scanf() [input] and placed into array specified*/
int i;
for(i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}
}
void get_int(int *i) {
//get_int() - gets an integer value from scanf [input] and loads into value specified.
scanf("%i", i);
}
//logic functions-------------------------------------------------------------------------------------------------------
int logic(struct Battle_data *data) {
/*logic() - logic level functions deal with all logic functions in the program.
* 1. set local variables: mainly to deal with sorting
* 2. sort struct arrays using quick sort(placed in local arrays)
* 3. compare values inside arrays.
* 4. return solution to main.*/
//local variables
int first_index = 0;
int last_index = data->no_armies - 1;
int iteration_count = 0;
//collect data from struct
int *atk = data->army_power_atk;
int *def = data->army_power_def;
//sorts the arrays inside arrays(taken from structs) for both atk and def
sort_arr(atk, first_index, data->no_armies - 1);
sort_arr(def, first_index, data->no_armies - 1);
//compares the array values to each other
iteration_count = compare(atk, def, last_index, last_index, iteration_count);
//return result
return iteration_count;
}
int compare(int *atk, int *def, int top_atk, int top_def, int i) {
/*compare() - function compares two values from arrays. If value def is greater than or equal to value atk; return
* compare(with both indices of atk and def - 1. i is increased by 1). If value atk is greater then
* value def; return compare(atk - 1). this is all wrapped in a conditional clause stating that the
* index of either array cannot be less than 0
*
* return i.(iteration counter)*/
//condition: indices of both atk anbd def must be greater then 0
if(top_atk >= 0 && top_def >= 0) {
//if atk <= def
if (atk[top_atk] <= def[top_def]) {
return compare(atk, def, top_atk - 1, top_def - 1, i + 1);
}
//if atk > def
else if (atk[top_atk] > def[top_def]) {
return compare(atk, def, top_atk - 1, top_def, i);
}
}
return i;
}
int *sort_arr(int *pInt, int first_index, int last_index) {
/*sort_arr() - quick sort variant.
* the function uses the pivot_locale variable to act as the partition and split through the sort. */
int pivot_locale;
if (first_index < last_index){
//select partition.
pivot_locale = partition(pInt, first_index, last_index);
sort_arr(pInt, first_index, pivot_locale);
sort_arr(pInt, pivot_locale + 1, last_index);
}
}
int partition(int *pInt, int first_index, int last_index) {
/*parition() function - function uses the perameters given and swaps all integers in order from least to greatest*/
//local variables
int pivot = pInt[first_index];
int left = first_index;
int i;
//for loop that is ditated by how big the partition in question is
for (i = first_index; i <= last_index; i++) {
//if out of place in partition, swap with current(pointed to) index.
if(pInt[i] < pivot){
left = left + 1;
//swap
swap(&pInt[i], &pInt[left]);
}
}
//else swap
swap(&pInt[first_index], &pInt[left]);
//return lower left bound for partition.
return left;
}
void swap(int *i, int *j) {
//swap() - swap function, swaps pointer locale
int temp = *i;
*i = *j;
*j = temp;
}
//----------------------------------------------------------------------------------------------------------------------
void output(int i) {
//output "level" - prints to screen.
printf("%i ", i);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.