The Java Program: Balloons.java
1 import java.io.*;
2 import java.util.Arrays;
3 import java.util.Scanner;
4
5 public final class Balloons {
6
7
8
9
10 public static class Team implements Comparable<Team> {
11 public final int number, distances[], prefer, difference;
12 private static int counter=0;
13 private int id = counter++;
14
15
16
17
18
19
20
21
22 public Team (int n, int d0, int d1) {
23 number = n;
24 distances = new int[]{d0,d1};
25
26 prefer = d0<d1 ? 0 : 1;
27 difference = Math.abs (d1-d0);
28 }
29
30 public int compareTo (Team t) {
31 if (t.difference < difference) return -1;
32 if (t.difference > difference) return +1;
33 if (t.id < id) return -1;
34 if (t.id > id) return +1;
35 assert this.equals (t);
36 return 0;
37 }
38
39 public String toString() {
40 return String.format ("{Team %d: n=%d, dist=(%d,%d), diff=%d}",
41 id, number, distances[0], distances[1], difference);
42 }
43 }
44
45 private static final Scanner STDIN =
46 new Scanner (new BufferedInputStream (System.in));
47
48 public static void main (String[] args) {
49
50 for(;;) {
51 final int n = STDIN.nextInt();
52 if (n==0) break;
53
54 final int a = STDIN.nextInt();
55 assert 0<=a && a<=10000;
56 final int b = STDIN.nextInt();
57 assert 0<=b && b<=10000;
58 final int[] s = {a,b};
59
60 Team teams[] = new Team[n];
61 for (int i=0; i<n; i++) {
62 final int k = STDIN.nextInt();
63 final int d0 = STDIN.nextInt();
64 final int d1 = STDIN.nextInt();
65 teams[i] = new Team (k, d0, d1);
66 }
67
68
69
70
71 Arrays.sort (teams);
72
73
74 int total = 0;
75 for (Team team : teams) {
76 assert team.number < s[0]+s[1];
77 System.out.print (team);
78
79
80 final int p = team.prefer;
81 final int q = 1-p;
82 if (s[p] >= team.number) {
83
84 total += team.number * team.distances[p];
85 s[p] -= team.number;
86 } else {
87
88
89
90 final int rest = team.number - s[p];
91 total += s[p]* team.distances[p];
92 s[p] = 0;
93
94
95 total += rest * team.distances[q];
96 s[q] -= rest;
97 }
98 System.out.printf ("%d %d %d%n", s[0],s[1],total);
99 }
100
101 System.out.println (total);
102 }
103 }
104 }
105
106
107
108
109
110