diff options
Diffstat (limited to 'others/other')
| -rwxr-xr-x | others/other/ChonSo/chonso.py | 104 | ||||
| -rw-r--r-- | others/other/README.md | 118 | ||||
| -rwxr-xr-x | others/other/chonso.py | 98 | ||||
| -rw-r--r-- | others/other/divseq.c | 38 | ||||
| -rwxr-xr-x | others/other/hinhvuong.py | 7 | ||||
| -rw-r--r-- | others/other/quacau.c | 31 |
6 files changed, 396 insertions, 0 deletions
diff --git a/others/other/ChonSo/chonso.py b/others/other/ChonSo/chonso.py new file mode 100755 index 0000000..da8dd2e --- /dev/null +++ b/others/other/ChonSo/chonso.py @@ -0,0 +1,104 @@ +#!/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 222391b..3eb8332 100644 --- a/others/other/README.md +++ b/others/other/README.md @@ -375,3 +375,121 @@ Ba số nguyên dương theo thứ tự min, cmin, count | --------- | --------- | | 2 10 | 6 4 3 | | 200 200 | 200 12 1 | + +## Qua cầu + +Cho một chiếc cầu ngang có chiều dài n+1 được tạo bởi các ô vuông kích thước +1×1 được đánh số từ 0 đến n, bạn đứng tại vị trí 0 lúc bắt đầu, và một chiếc +giầy đăc biệt có thể nhảy xa tối đa m ô, tối thiểu 1 ô. + +### Yêu cầu + +Bạn hãy chỉ ra có bao nhiêu cách có thể đi đến vị trí thứ n của cây cầu này với +đôi giầy đặc biệt kia. Được biết trên cây cầu có k vị tri bị hỏng và bạn không +thể bước vào đó. + +### Dữ liệu + +* Dòng đầu tiên chứa 3 số n, m, k. +* Dòng 2 chứa k số là vị trí các ô bị hỏng. + +### Kết quả + +1 dòng chứa số cách đi qua cầu mod 1000000007. + +### Giới hạn + +* Subtask1: 0 ≤ n, m ≤ 1000 (80% số điểm). +* Subtask2: 0 ≤ n, m ≤ 10<sup>6</sup> (20% số điểm). + +### Ví dụ + +| quacau.inp | quacau.out | +| ------------ | :--------: | +| 8 3 2<br>3 4 | 8 | + +## Đếm dãy chia hết + +Cho một dãy số nguyên dương, đếm số lượng dãy con liên tiếp có tổng chia hết +cho *d*. Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu +hoặc điểm cuối hai dãy con đó trong dãy đã cho là khác nhau. Ví dụ + +* Với *d* = 4, dãy (2, 1, 2, 1, 4, 1) có 4 dãy con thoả mãn là (1, 2, 1), (1, + 2, 1, 4), (4) và (2, 1, 4, 1). +* Với *d* = 2, dãy (1, 1, 1, 1) có 4 dãy con thỏa mãn. + +### Dữ liệu + +* Dòng đầu tiên là số *T* - số lượng test. +* T nhóm dòng tiếp theo, mỗi dòng tương ứng một yêu cầu: + * Dòng đầu là 2 số nguyên dương *d* và *N*. + * Dòng thứ 2 chứa *N* số nguyên biểu diễn dãy số. + +### Kết quả + +*T* dòng là kết quả các test tương ứng theo thứ tự. + +### Ví dụ + +| DIVSEQ.INP | DIVSEQ.OUT | +| ----------------------- | :--------: | +| 1<br>4 6<br>2 1 2 1 4 1 | 4 | + +### Giới hạn + +* *T* ≤ 100. +* *d* ≤ 1000000, *N* ≤ 50000, 50% số test có *N* ≤ 1000. + +## Hình vuông + +Cho 4 điểm trên hệ trục tọa độ chuẩn Oxy. Hãy kiểm tra xem bốn điểm này có phải +là bốn đỉnh của một hình vuông có các cạnh song song với các trục toạ độ hay +không? + +### Dữ liệu + +Gồm 4 dòng, mỗi dòng ghi 2 số nguyên là tọa độ của một điểm. Mỗi số nguyên có +giá trị tuyệt đối không quá 10<sup>9</sup>. + +### Kết quả + +Diện tích hình vuông nếu bốn điểm thoả mãn yêu cầu đề bài, ngược lại ghi `-1`. + +### Ví dụ + +| HINHVUONG.INP | HINHVUONG.OUT | +| :--------------------------: | :-----------: | +| -3 -1<br>-3 3<br>1 3<br>1 -1 | 16 | + +## Chọn số + +Cho một dãy số nguyên a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>. + +### Yêu cầu: + +Đếm số cách chọn ra dãy số khác nhau gồm m phần tử. Hai dãy số được gọi là khác +nhau nếu tồn tại ít nhất một vị trí mà ở đó giá trị 2 phần tử của 2 dãy là khác +nhau. + +### Dữ liệu + +* Dòng đầu ghi 2 số n, m. +* Dòng tiếp theo ghi các số nguyên a<sub>i</sub> (các số cách nhau ít nhất một + dấu cách). + +### Kết quả + +Ghi ra số lượng cách chọn dãy. Vì kết quả có thể rất lớn nên chỉ cần ghi phần +dư của kết quả khi chia (10<sup>12</sup> + 7). + +### Giới hạn + +* 3 ≤ n ≤ 1000. +* 1 ≤ m < n. +* a<sub>i</sub> ≤ 10<sup>9</sup> ∀ 1 ≤ i ≤ n. + +### Ví dụ + +| chonso.inp | chonso.out | +| ------------ | :--------: | +| 3 2<br>1 3 1 | 3 | diff --git a/others/other/chonso.py b/others/other/chonso.py new file mode 100755 index 0000000..e1e4da3 --- /dev/null +++ b/others/other/chonso.py @@ -0,0 +1,98 @@ +#!/usr/bin/env python3 +from fractions import Fraction +from functools import reduce +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``. + + length : int + Maximum length for coef + """ + MAXLEN = 1001 + + def __init__(self, coef, length=None): + self.coef = list(coef)[:(length or Polynomial.MAXLEN)+1] + + def __len__(self): + """Return len(self).""" + return len(self.coef) + + def __getitem__(self, term): + """Return coefficient of the corresponding term.""" + try: + return self.coef[term] + except IndexError: + return 0 + + def __iter__(self): + return iter(self.coef) + + def __repr__(self): + return 'Polynomial({})'.format(self.coef) + + def __add__(self, value): + """Return self+value.""" + length = max(len(self), len(value)) + return Polynomial((self[i]+value[i] for i in range(length))) + + def __mul__(self, value): + """Return self*value.""" + if isinstance(value, Polynomial): + l = [] + for i in range(min(len(self) + len(value) - 1, Polynomial.MAXLEN)): + l.append(sum(value[i - j] * c for j, c in enumerate(self) + if 0 <= i - j < len(value))) + return Polynomial(l) + + if isinstance(value, (int, float, complex, Fraction)): + return Polynomial((i * value for i in self.coef)) + + 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.""" + EXPPOLY = Polynomial((Fraction(1, factorial(i)) for i in range(Polynomial.MAXLEN))) + + def __init__(self, degree): + Polynomial.__init__(self, ExpPoly.EXPPOLY.coef, length=degree) + + +def chonso(m, a): + t = tuple(min(a.count(i), m) for i in set(a)) + d = {i: t.count(i) for i in set(t)} + Polynomial.MAXLEN = m + 1 + g = (ExpPoly(k) ** v for k, v in d.items()) + return reduce(mul, g, factorial(m))[-1].numerator + + +if __name__ == '__main__': + with open('chonso.inp') as fi, open('chonso.out', 'w') as fo: + n, m = map(int, fi.readline().split()) + a = tuple(int(i) for i in fi.readline().split())[:n] + print(chonso(m, a) % (10**12 + 7), file=fo) diff --git a/others/other/divseq.c b/others/other/divseq.c new file mode 100644 index 0000000..57b17dd --- /dev/null +++ b/others/other/divseq.c @@ -0,0 +1,38 @@ +#include <stdio.h> +#include <stdlib.h> + +int main() +{ + FILE *fi = fopen("DIVSEQ.INP", "r"), *fo = fopen("DIVSEQ.OUT", "w"); + char t; + unsigned short n; + unsigned long d, i, *b, *c; + long long *a, res; + + fscanf(fi, "%hhd", &t); + for (; t; t--) { + fscanf(fi, "%ld %hu", &d, &n); + a = malloc(n * sizeof(long long)); + for (i = 0; i < n; i++) { + fscanf(fi, "%Ld", a + i); + a[i] %= d; + } + + b = malloc(n * sizeof(long)); + c = calloc(d, sizeof(long)); + for (c[*b = *a % d] += *c = i = 1; i < n; i++) + c[b[i] = (b[i - 1] + a[i]) % d]++; + free(a); + free(b); + + for (res = i = 0; i < d; i++) + res += c[i] * (c[i] - 1) / 2; + free(c); + + fprintf(fo, "%Ld\n", res); + } + + fclose(fi); + fclose(fo); + return 0; +} diff --git a/others/other/hinhvuong.py b/others/other/hinhvuong.py new file mode 100755 index 0000000..8e3891a --- /dev/null +++ b/others/other/hinhvuong.py @@ -0,0 +1,7 @@ +#!/usr/bin/env python3 +with open('HINHVUONG.INP') as fi, open('HINHVUONG.OUT', 'w') as fo: + A, B, C, D = sorted([int(i) for i in s.split()] for s in fi.readlines()) + if A[0] != B[0] or C[0] != D[0] or A[1] != C[1] or B[1] != D[1]: + fo.write('-1\n') + else: + print((B[0]-C[0]) ** 2, file=fo) diff --git a/others/other/quacau.c b/others/other/quacau.c new file mode 100644 index 0000000..48abc03 --- /dev/null +++ b/others/other/quacau.c @@ -0,0 +1,31 @@ +#include <stdio.h> +#include <stdlib.h> + +int main() +{ + FILE *f = fopen("quacau.inp", "r"); + long n, m, i; + long long k, *ways; + char *broken; + + fscanf(f, "%ld %ld %Ld", &n, &m, &k); + broken = calloc(n + 1, sizeof(char)); + for (; k; k--) { + fscanf(f, "%ld", &i); + broken[i] = 1; + } + fclose(f); + + ways = (long long *) calloc(n + m + 1, sizeof(long long)) + m; + *ways = 1; + for (i = 0; i < n; i++) { + k = (ways[i] + k - ways[i - m] + 1000000007) % 1000000007; + if (!broken[i + 1]) + ways[i + 1] = k; + } + + f = fopen("quacau.out", "w"); + fprintf(f, "%Ld\n", ways[n]); + fclose(f); + return 0; +} |