diff options
author | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2017-08-03 03:06:23 +0700 |
---|---|---|
committer | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2017-08-03 03:06:23 +0700 |
commit | 5cfeec0f11dbcff922fe5b1a1a17bccf4812852e (patch) | |
tree | c866745d54978d860f93acbff14e7ca1d1d2db59 /others/other/defrag.py | |
parent | 44f9d4b8e63d4f7f1b447744124e95f22c8ce296 (diff) | |
download | cp-5cfeec0f11dbcff922fe5b1a1a17bccf4812852e.tar.gz |
[others] Move other/colorec.* to mHoang and add other/{defrac,lang}.py
Diffstat (limited to 'others/other/defrag.py')
-rwxr-xr-x | others/other/defrag.py | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/others/other/defrag.py b/others/other/defrag.py new file mode 100755 index 0000000..df0e273 --- /dev/null +++ b/others/other/defrag.py @@ -0,0 +1,32 @@ +#!/usr/bin/env python3 +with open('DEFRAC.INP') as f: + v, n, m = map(int, f.readline().split()) + t, l, b = tuple(map(int, f.readline().split())), [], -1 + +for i in range(n): + a, b, p = t[i * 2], t[i*2 + 1], b + tmp = a - p - 1 + if i: l[-1].extend([tmp, l[-1][1] + tmp >= m]) + l.append([b - a + 1, tmp]) +tmp = v - b - 1 +l[-1].extend([tmp, l[-1][1] + tmp >= m]) +s = sorted(l, key=(lambda i: i[1]), reverse=True) + +with open('DEFRAC.OUT', 'w') as f: + if s[0][1] >= m: + f.write('0\n') + else: + best = None + for i, v in enumerate(l): + if best is None or v < best: + if v[-1]: + best = v[0], i + elif sum(v[:3]) >= m: + for j in s: + if j is not v and j[1] >= v[0]: + best = v[0], i + break + if best is None: + f.write('-1\n') + else: + print(best[1] + 1, file=f) |