From ce427c0741ff51539e5410710dd04a11d8d22b4f Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Mon, 24 Jul 2017 02:23:37 +0700 Subject: Add others/other/{cube,kite}.py --- others/other/ChonSo/chonso.py | 104 ------------------------------------------ others/other/README.md | 69 ++++++++++++++++++++++++++++ others/other/cube.py | 26 +++++++++++ others/other/kite.py | 9 ++++ 4 files changed, 104 insertions(+), 104 deletions(-) delete mode 100755 others/other/ChonSo/chonso.py create mode 100755 others/other/cube.py create mode 100755 others/other/kite.py (limited to 'others') diff --git a/others/other/ChonSo/chonso.py b/others/other/ChonSo/chonso.py deleted file mode 100755 index da8dd2e..0000000 --- a/others/other/ChonSo/chonso.py +++ /dev/null @@ -1,104 +0,0 @@ -#!/usr/bin/env python3 -from fractions import Fraction -from functools import reduce -from itertools import permutations -from math import factorial -from operator import floordiv, mul - - -class Polynomial: - """A fixed-length power series class. - - The Polynomial class is made to calculate the number of permutations - and combinations using generating function, so it only provides '+', - '*', '**' methods and doesn't support negative power degrees. - - Parameters - ---------- - coef : iterable of numeric objects - Polynomial coefficients in order of increasing degree, i.e., - ``(1, 2, 3)`` give ``1 + 2*x + 3*x**2``. - - maxdeg : int - Highest degree the polynomial will hold. - """ - def __init__(self, coef, maxdeg): - self.coef = [c for i, c in enumerate(coef) if i <= maxdeg] - self.coef += [0] * (maxdeg - len(self.coef) + 1) - self.maxdeg = maxdeg - - def __len__(self): - """Return len(self).""" - return self.maxdeg + 1 - - def __getitem__(self, term): - """Return coefficient of the corresponding term.""" - return self.coef[term] if -len(self) <= term <= self.maxdeg else 0 - - def __setitem__(self, term, coefficient): - """Set coefficient of the corresponding term.""" - if 0 <= term <= self.maxdeg: self.coef[term] = coefficient - - def __repr__(self): - return 'Polynomial({})'.format(self.coef) - - def __rshift__(self, value): - """Return self with coefficients shifted value positions to the - right (syntactic sugar). - """ - return Polynomial(([0] * value + self.coef)[:len(self)], self.maxdeg) - - def __add__(self, value): - """Return self+value.""" - length = max(len(self), len(value)) - return Polynomial([self[i]+value[i] for i in range(length)], length-1) - - def __mul__(self, value): - """Return self*value.""" - if isinstance(value, Polynomial): - res = Polynomial([], self.maxdeg) - for i, c in enumerate(value.coef): - res += (self >> i) * c - return res - if isinstance(value, (int, float, complex, Fraction)): - return Polynomial([i * value for i in self.coef], self.maxdeg) - err = "unsupported operand type(s) for *: 'Polynomial' and '{}'" - raise TypeError(err.format(type(value).__name__)) - - def __rmul__(self, value): - """Return value*self.""" - return self * value - - def __pow__(self, value): - """Return self**value.""" - if value == 1: return self - tmp = self ** (value//2) - if value % 2: return tmp * self * tmp - return tmp * tmp - - -class ExpPoly(Polynomial): - """Exponential polynomial, with highest degree of 1000.""" - maxdeg = 1000 - EXPPOLY = Polynomial([Fraction(1, factorial(i)) for i in range(maxdeg + 1)], - maxdeg) - - def __init__(self, degree, maxdeg): - Polynomial.__init__(self, ExpPoly.EXPPOLY.coef[:degree+1], maxdeg) - - -def chonso(m, a): - t = tuple(a.count(i) for i in set(a)) - d = {i: t.count(i) for i in set(t)} - ExpPoly.maxdeg = m - g = [ExpPoly(k, m) ** v for k, v in d.items()] - print(t, d, g) - return reduce(mul, g, factorial(m))[-1].numerator - - -if __name__ == '__main__': - with open('chonso.inp') as f: - n, m = map(int, f.readline().split()) - a = tuple(int(i) for i in f.readline().split())[:n] - - with open('chonso.out', 'w') as f: print(chonso(m, a) % (10**12 + 7), file=f) diff --git a/others/other/README.md b/others/other/README.md index 3eb8332..f901d94 100644 --- a/others/other/README.md +++ b/others/other/README.md @@ -493,3 +493,72 @@ dư của kết quả khi chia (1012 + 7). | chonso.inp | chonso.out | | ------------ | :--------: | | 3 2
1 3 1 | 3 | + +## Thả diều + +Trong một cuộc thi thả diều, ban giám khảo căn cứ vào độ cao của mỗi chiếc +diều đạt được khi thả lên trời và xếp hạng cho chiếc diều đó theo một cách đặc +biệt: Những chiếc diều không được thả cùng một lúc, mà theo trình tự từng +chiếc một. Khi một chiếc diều được thả lên trời, ban giám khảo sẽ căn cứ vào +độ cao của chiếc diều và xếp hạng cho chiếc diều đó bằng cách so độ cao của nó +với độ cao của những chiếc diều đã thả trước đó: hạng của một chiếc diều bằng +số diễu đã thả cao hơn nó cộng thêm 1. + +### Yêu cầu + +Có *n* chiếc diều lần lượt được thả lên trời, em hãy cho biết dãy số biểu diễn +giá trị xếp hạng của *n* chiếc diều đó. + +### Dữ liệu + +* Dòng đầu là số nguyên *n* ≤ 100000 cho biết số chiếc diều tham gia dự thi. +* *n* dòng tiếp theo, mỗi dòng ghi một số nguyên dương ≤ 109 mô tả + độ cao của một chiếc diều, theo thứ tự mà nó được thả lên. + +### Kết quả + +Gồm *n* dòng: dòng thứ *i* ghi số nguyên biểu diễn giá trị xếp hạng của chiếc +diều thứ *i* tại thời điểm nó được thả lên. + +### Ví dụ + +| KITE.INP | KITE.OUT | +| :-----------------------------------: | :------------------------: | +| 6
78
24
68
40
39
89 | 1
2
2
3
4
1 | + +#### Giải thích + +* Chiếc đầu tiên xếp hạng 1 vì trước nó chưa có chiếc diều nào được thả. +* Chiếc thứ hai xếp hạng 2 vì 24 < 78. +* Chiếc thứ ba cũng xếp hạng 2 vì 24 < 68 < 78. +* Chiếc thứ tư xếp hạng 3 vì 24 < 40 < 68 < 78. +* Chiếc thứ năm xếp hạng 4 vì 24 < 39 < 40 < 68 < 78. +* Chiếc cuối cùng xếp hạng 1 vì 24 < 39 < 40 < 68 < 78 < 89. + +## Khối lập phương + +Cho 3 khối hình hộp chữ nhật có kích thước lần lượt là: (a1, +b1, c1), (a2, b2, c2), +(a3, b3, c3). Hãy xác định xem có thể xếp 3 +khối hình hộp chữ nhật này thành một khối lập phương hay không. + +### Dữ liệu vào + +* Dòng đầu tiên ghi số test T. +* Tiếp theo là T test. Mỗi test được ghi trên 3 dòng, dòng i ghi 3 số nguyên + dương ai, bi, ci. + +### Kết quả + +Ứng với mỗi test, ghi ra `TRUE` hoặc `FALSE` tương ứng với có thể hoặc không +thể xếp thành khối lập phương. + +### Giới hạn + +Các số trong input không vượt quá 100. + +### Ví dụ: + +| Input | Output | +| :-----------------------------------------------------: | :-----------: | +| 2
3 3 1
3 3 1
3 3 1
3 3 1
3 3 1
3 2 2 | TRUE
FALSE | diff --git a/others/other/cube.py b/others/other/cube.py new file mode 100755 index 0000000..03eb30f --- /dev/null +++ b/others/other/cube.py @@ -0,0 +1,26 @@ +#!/usr/bin/env python3 +from collections import deque + + +def same(*a): return all(len(set(i)) == 1 for i in a) + + +def add(h, k): + d = deque(zip(h, k)) + for _ in range(3): + if same(d[1], d[2]): yield sorted((sum(d[0]), d[1][0], d[2][1])) + d.rotate() + + +def cube(d): + for _ in range(3): + for i in add(d[0], d[1]): + for j in add(i, d[2]): + if same(j): return 'TRUE' + d.rotate() + return 'FALSE' + + +for _ in range(int(input())): + d = deque(sorted(map(int, input().split())) for _ in range(3)) + print(cube(d)) diff --git a/others/other/kite.py b/others/other/kite.py new file mode 100755 index 0000000..0330b01 --- /dev/null +++ b/others/other/kite.py @@ -0,0 +1,9 @@ +#!/usr/bin/env python3 +from bisect import bisect_left, insort + +with open('KITE.INP') as inp, open('KITE.OUT', 'w') as out: + n, a = inp.readline(), [] + for line in inp: + x = -int(line) + insort(a, x) + print(bisect_left(a, x) + 1, file=out) -- cgit 1.4.1