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
| // EDIT 2016-12-24-23h13 : amélioration de getNumberInRange
// EDIT 2016-12-25-12h29 : renommage de getNumberInRange en readNumberInRange
// EDIT 2016-12-26-13h18 : amélioration de strictlyMaxElement
#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <stdexcept>
#include <vector>
//! \remark If the strictly largest element does not exist, return last iterator.
template<class ForwardIt, class Compare>
ForwardIt strictlyMaxElement(ForwardIt first, ForwardIt last, Compare cmp)
{
if(first == last)
return last;
ForwardIt largest = first;
bool strictlyLargest = true;
for(++first; first != last; ++first) {
if(cmp(*largest, *first)) {
largest = first;
strictlyLargest = true;
} else {
strictlyLargest = strictlyLargest && cmp(*first, *largest);
}
}
return strictlyLargest ? largest : last;
}
template<class CharT, class Traits, class NumberT>
NumberT readNumberInRange(std::basic_istream<CharT, Traits>& input, NumberT min, NumberT max)
{
NumberT result;
input >> result;
if(input.eof()) {
throw std::runtime_error("Fail to read a number from input stream: end of file.");
} else if(input.bad()) {
throw std::runtime_error("Fail to read a number from input stream: bad state.");
} else if(input.fail()) {
input.clear(); // unset failbit
input.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // skip bad input
throw std::runtime_error("Input error when reading a number: bad format.");
} else if(result < min || result > max) {
std::ostringstream oss;
oss << "Input error: the number (" << result
<< ") must be between " << min << " and " << max << '.';
throw std::runtime_error(oss.str());
}
return result;
}
struct Frog {
typedef unsigned DistanceType;
typedef unsigned TurnCountType;
DistanceType totalDistance = 0;
TurnCountType winningTurnCount = 0;
};
int main()
{
try {
const size_t frogNumber = readNumberInRange(std::cin, 1, 100);
const Frog::TurnCountType turnNumber = readNumberInRange(std::cin, 1, 1000);
std::vector<Frog> frogs(frogNumber);
for(Frog::TurnCountType k = 0; k < turnNumber; ++k)
{
const auto winningFrogIt = strictlyMaxElement(std::begin(frogs), std::end(frogs),
[](const Frog& f1, const Frog& f2){return f1.totalDistance < f2.totalDistance;});
if(winningFrogIt != std::end(frogs))
++(winningFrogIt->winningTurnCount);
const size_t frogId = readNumberInRange(std::cin, 1, int(frogNumber));
const Frog::DistanceType jumpDistance = readNumberInRange(std::cin, 1, 100);
frogs[frogId - 1].totalDistance += jumpDistance;
}
const auto winningFrogIt = std::max_element(frogs.cbegin(), frogs.cend(), // GCC 4.9.2: std::cbegin and std::cend do not exist yet.
[](const Frog& f1, const Frog& f2){return f1.winningTurnCount < f2.winningTurnCount;});
const size_t winningFrogId = std::distance(frogs.cbegin(), winningFrogIt) + 1;
std::cout << winningFrogId;
return 0;
} catch(const std::exception& e) {
std::cerr << e.what() << '\n';
return 1;
}
} |
Exercice France IOI
Répondre avec citation
Envoyé par Bousk
Partager