154.cpp

Back Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// 154.cpp http://acm.uva.es/p/v1/154.html
//
// Solution to ACM problem #154 - "Recycling"
//
// Matthew Eagar - meagar@gmail.com
// Verified to work as of July 28 / 2009
//
#include <iostream>
#include <vector>
#include <cassert>
#include <climits>
struct City {
int id;
std::vector<char> bins;
City() : id(0), bins(5) { }
std::istream& read(std::istream& in) {
// line ending with 'e' means end of case
if (in.peek() == 'e') {
// Eat the line
while (in.get() != '\n' && in);
in.setstate(std::ios::failbit);
return in;
}
// line beginning with '#' means EOF
if (in.peek() == '#') {
// Eat the hash character
in.ignore();
in.setstate(std::ios::failbit);
in.setstate(std::ios::eofbit);
return in;
}
// Read the 5 bins from the input stream
for (int i = 0; i < 5; ++i) {
char bin, tmp, material;
// format is "b/m,"...
in >> bin >> tmp >> material >> tmp;
// ...except the last bin, which won't have a ','
if (tmp != ',')
in.putback(tmp);
switch(bin) {
case 'r': bins[0] = material; break;
case 'o': bins[1] = material; break;
case 'y': bins[2] = material; break;
case 'g': bins[3] = material; break;
case 'b': bins[4] = material; break;
default: assert(false);
}
}
return in;
}
// Return the number of differences between the given city and ourselves
int diff(const City& c) const {
int diffs = 0;
for (int i = 0; i < 5; ++i)
if (bins[i] != c.bins[i])
++diffs;
return diffs;
}
}; // Class city
std::istream& operator>>(std::istream& in, City& c) { return c.read(in); }
class Solver {
public:
Solver() : cities_() { }
// Read our list of cities from the given input stream
std::istream& read(std::istream& in) {
cities_.clear();
int i = 0;
for (City c; in >> c;) {
c.id = ++i;
cities_.push_back(c);
}
if (!in.eof())
in.clear();
return in;
}
// Solve for the best city
int solve() {
// Find the city that has the fewest differences between all other cities
int min = INT_MAX, minIdx = 0;
typedef std::vector<City>::const_iterator citr;
// For each city...
for (citr i = cities_.begin(); i != cities_.end(); ++i) {
int diffs = 0;
// Compare with each other city...
for (citr j = cities_.begin(); j != cities_.end(); ++j) {
// Except ourselves...
if (i == j)
continue;
diffs += i->diff(*j);
}
if (diffs < min) {
// We have a new best candidate
min = diffs;
minIdx = i->id;
}
}
return minIdx;
}
private:
std::vector<City> cities_;
}; // class Solver
std::istream& operator>>(std::istream& in, Solver& s) { return s.read(in); }
int main() {
for (Solver s; std::cin >> s;)
std::cout << s.solve() << std::endl;
}