about summary refs log tree commit diff
diff options
context:
space:
mode:
authorRaphael McSinyx <vn.mcsinyx@gmail.com>2017-07-24 02:23:37 +0700
committerRaphael McSinyx <vn.mcsinyx@gmail.com>2017-07-24 02:26:15 +0700
commitce427c0741ff51539e5410710dd04a11d8d22b4f (patch)
tree7b12163e0a665ae8d9cb3e482257062457619aa1
parent1ceb9227cb48d50f57343fa42c32815b94855488 (diff)
downloadcp-ce427c0741ff51539e5410710dd04a11d8d22b4f.tar.gz
Add others/other/{cube,kite}.py
-rwxr-xr-xothers/other/ChonSo/chonso.py104
-rw-r--r--others/other/README.md69
-rwxr-xr-xothers/other/cube.py26
-rwxr-xr-xothers/other/kite.py9
4 files changed, 104 insertions, 104 deletions
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 (10<sup>12</sup> + 7).
 |  chonso.inp  | chonso.out |
 | ------------ | :--------: |
 | 3 2<br>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 ≤ 10<sup>9</sup> 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<br>78<br>24<br>68<br>40<br>39<br>89 | 1<br>2<br>2<br>3<br>4<br>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à: (a<sub>1</sub>,
+b<sub>1</sub>, c<sub>1</sub>), (a<sub>2</sub>, b<sub>2</sub>, c<sub>2</sub>),
+(a<sub>3</sub>, b<sub>3</sub>, c<sub>3</sub>). 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 a<sub>i</sub>, b<sub>i</sub>, c<sub>i</sub>.
+
+### 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<br>3 3 1<br>3 3 1<br>3 3 1<br>3 3 1<br>3 3 1<br>3 2 2 | TRUE<br>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)