Recently, a new game, Risk 1000000 , similar to Risk, has been released that all
ID: 3672605 • Letter: R
Question
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
Explanation / Answer
run:
5
1
490851 , 429784 , 920357 , 923556 , 28246 , 662315 , 956217 , 114383 , 623422 , 667665 , 732626 , 453658 , 4813 , 877451 , 55342 , 128237 , 394041 , 324633 , 38395 , 466842 , 535009 , 164665 , 289869 , 282536 , 32327 , 313533 , 709034 , 13307 , 265212 , 4680 , 849859 , 45921 , 912473 , 151461 , 690302 , 204411 , 943785 , 558915 , 805486 , 579014 , 132388 , 108369 , 406948 , 115333 , 408150 , 326002 , 559775 , 590221 , 265823 , 486813 , 213022 , 611117 , 636371 , 104341 , 105814 , 965239 , 386817 , 815807 , 117312 , 51311 , 825425 , 553957 , 929290 , 206800 , 608135 , 861830 , 865325 , 249845 , 993316 , 866775 , 178782 , 176427 , 206571 , 117466 , 15646 , 641808 , 960321 , 229402 , 202028 , 78759 , 928173 , 669568 , 521947 , 115452 , 954176 , 903509 , 480254 , 253678 , 791758 , 253397 , 426239 , 961886 , 597914 , 398060 , 784271 , 209395 , 352336 , 643088 , 367031 , 528903 , 68011 , 215226 , 945933 , 948337 , 587319 , 697474 , 362115 , 349743 , 971376 , 742486 , 98778 , 296432 , 105738 , 506518 , 132084 , 939900 , 641738 , 959632 , 29318 , 696769 , 763537 , 72403 , 713900 , 423355 , 178297 , 357746 , 285462 , 502142 , 468056 , 984855 , 563104 , 416227 , 210146 , 201153 , 236032 , 650381 , 773931 , 405723 , 880664 , 453079 , 82633 , 884090 , 563500 , 715996 , 885080 , 778163 , 403949 , 305442 , 938647 , 87255 , 444212 , 429795 , 724655 , 673293 , 630666 , 556922 , 814228 , 573898 , 973092 , 607015 , 340164 , 584367 , 995372 , 719807 , 793581 , 977022 , 386618 , 666291 , 120875 , 924410 , 504865 , 95674 , 489007 , 198939 , 896678 , 869726 , 378939 , 394219 , 41868 , 39200 , 931081 , 252480 , 744203 , 257609 , 211340 , 29718 , 842015 , 254415 , 748878 , 502600 , 237884 , 88224 , 437048 , 171883 , 642334 , 890125 , 364784 , 407176 , 550399 ,
Attacker army values:
86 , 60 , 19 , 94 , 38 , 14 , 4 , 41 , 43 , 60 ,
Defender army values:
50 , 63 , 84 , 10 , 51 , 99 , 3 , 74 , 24 , 5 ,
An Optimal Re arrangement:
86 , 50 60 , 63 19 , 84 94 , 10 38 , 51 14 , 99 4 , 3 41 , 74 43 , 24 60 , 5 BUILD SUCCESSFUL (total time: 5 seconds)
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package ships1;
import java.util.Random;
import java.util.Scanner;
/**
*
* @author Admin
*/
public class Ships1 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int c, n;
// TODO code application logic here
Scanner sc = new Scanner(System.in);
Random r1 = new Random();
int r2;
c = sc.nextInt();
n = sc.nextInt();
for (int i=1; i<200; i++) {
r2 = r1.nextInt(1000000) + 1; /// a random number between 1 and a million
// r2 = r1.nextInt(10) + 1; // a random number between 1 and 10
System.out.print(" " + r2 + " , "); // each number represents the strength of the army
} // end for
int [] a1 = new int[20];
int [] a2 = new int[20];
System.out.println(" Attacker army values:");
int i;
for (i=1; i<=10; i++) {
r2 = r1.nextInt(100) + 1;
System.out.print(" " + r2 + " , ") ;
a1[i] = r2;
} // end for
System.out.println(" Defender army values:");
for (i=1; i<=10; i++) {
r2 = r1.nextInt(100) + 1;
System.out.print(" " + r2 + " , ") ;
a2[i] = r2;
} // end for
System.out.println(" An Optimal Re arrangement:");
int diff;
diff = (a1[i] - a2[1]);
for (i=1; i<=10; i++) {
if ( (a1[i] - a2[i]) > diff )
diff = a1[i] - a2[i];
System.out.print(" " + a1[i] + " , " + a2[i] + " ");
} // end for
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.