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
|
use std::io;
#[derive(Clone)]
struct Range {
first: i64,
last: i64,
}
impl Range {
fn new(first: i64, last: i64) -> Self {
assert!(first <= last);
Self { first, last }
}
fn contains(&self, value: i64) -> bool {
value >= self.first && value <= self.last
}
fn len(&self) -> i64 {
1 + self.last - self.first
}
}
fn in_ranges(ranges: &Vec<Range>, value: i64) -> bool {
for range in ranges {
if range.contains(value) {
return true;
}
}
false
}
fn merge_or_add(ranges: &mut Vec<Range>, range: &Range) {
if range.len() == 0 {
return;
}
let i = ranges.partition_point(|x| x.last < range.first);
if i == ranges.len() {
ranges.push(range.clone());
return;
}
if ranges[i].first > range.last {
ranges.insert(i, range.clone());
return;
}
if ranges[i].contains(range.first) {
if ranges[i].contains(range.last) {
// Whole range is swallowed
return;
}
merge_or_add(ranges, &Range::new(ranges[i].last + 1, range.last));
return;
}
if ranges[i].contains(range.last) {
ranges.insert(i, Range::new(range.first, ranges[i].first - 1));
return;
}
let before = Range::new(range.first, ranges[i].first - 1);
let after = Range::new(ranges[i].last + 1, range.last);
ranges.insert(i, before);
merge_or_add(ranges, &after);
}
fn remove_overlap(ranges: &Vec<Range>) -> Vec<Range> {
let mut ret = Vec::new();
for range in ranges {
merge_or_add(&mut ret, range);
}
ret
}
fn main() {
let mut ranges = Vec::new();
loop {
let mut buffer = String::new();
let bytes = io::stdin().read_line(&mut buffer).unwrap();
if bytes == 0 || buffer == "\n" {
break;
}
let mut iter = buffer.trim_end().split('-');
let first = iter.next().unwrap().parse::<i64>().unwrap();
let last = iter.next().unwrap().parse::<i64>().unwrap();
ranges.push(Range::new(first, last));
}
ranges.sort_by(|a, b| a.first.cmp(&b.first));
let mut available = Vec::new();
loop {
let mut buffer = String::new();
let bytes = io::stdin().read_line(&mut buffer).unwrap();
if bytes == 0 {
break;
}
available.push(buffer.trim_end().parse::<i64>().unwrap());
}
let mut fresh = 0;
for ingredient in available {
if in_ranges(&ranges, ingredient) {
fresh += 1;
}
}
println!("Fresh ingrediences {}", fresh);
let ranges2 = remove_overlap(&ranges);
let mut fresh2 = 0;
for range in ranges2 {
fresh2 += range.len();
}
println!("Fresh ids {}", fresh2);
}
|
