From 887c286cc8228e13f85b587ab92b37e920161eb9 Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Mon, 15 Apr 2019 17:20:41 +0700
Subject: Codechef celebrate 4.20 a bit early this year

---
 codechef/fence.py           |  15 +++++++++++++++
 codechef/maxrem.py          |  20 ++++++++++++++++++++
 codechef/mcsinyx-SNCK19.pdf | Bin 0 -> 1281964 bytes
 codechef/sj1.py             |  22 ++++++++++++++++++++++
 codechef/strch.c            |  30 ++++++++++++++++++++++++++++++
 codechef/subrem.py          |  26 ++++++++++++++++++++++++++
 6 files changed, 113 insertions(+)
 create mode 100755 codechef/fence.py
 create mode 100755 codechef/maxrem.py
 create mode 100644 codechef/mcsinyx-SNCK19.pdf
 create mode 100755 codechef/sj1.py
 create mode 100644 codechef/strch.c
 create mode 100755 codechef/subrem.py

(limited to 'codechef')

diff --git a/codechef/fence.py b/codechef/fence.py
new file mode 100755
index 0000000..8d1b266
--- /dev/null
+++ b/codechef/fence.py
@@ -0,0 +1,15 @@
+#!/usr/bin/env python3
+ADJ = (1, 0), (0, 1), (-1, 0), (0, -1)
+
+for i in range(int(input())):
+    fences = set()
+    n, m, k = map(int, input().split())
+    for j in range(k):
+        row, col = map(int, input().split())
+        for dr, dc in ADJ:
+            r, c = row + dr, col + dc
+            try:
+                fences.remove((r, c, row, col))
+            except KeyError:
+                fences.add((row, col, r, c))
+    print(len(fences))
diff --git a/codechef/maxrem.py b/codechef/maxrem.py
new file mode 100755
index 0000000..30087c7
--- /dev/null
+++ b/codechef/maxrem.py
@@ -0,0 +1,20 @@
+#!/usr/bin/env python3
+from bisect import bisect   # bisect takes no key argument. What a dick.
+
+input()
+a = [-int(i) for i in input().split()]
+a.sort()
+
+res = 0
+for i in a:
+    if i > res: break
+    for j in range(i, a[0] + i, i):
+        idx = bisect(a, j)
+        try:
+            tmp = a[idx] % i
+        except IndexError:
+            continue
+        if tmp < res: res = tmp
+        if res == i + 1: break
+
+print(-res)
diff --git a/codechef/mcsinyx-SNCK19.pdf b/codechef/mcsinyx-SNCK19.pdf
new file mode 100644
index 0000000..fc741e7
Binary files /dev/null and b/codechef/mcsinyx-SNCK19.pdf differ
diff --git a/codechef/sj1.py b/codechef/sj1.py
new file mode 100755
index 0000000..475f114
--- /dev/null
+++ b/codechef/sj1.py
@@ -0,0 +1,22 @@
+#!/usr/bin/env python3
+from collections import defaultdict, deque
+from math import gcd
+
+for t in range(int(input())):
+    n, edges = int(input()), defaultdict(list)
+    for _ in range(1, n):
+        x, y = (int(i) - 1 for i in input().split())
+        edges[x].append(y)
+        edges[y].append(x)
+    v = [int(i) for i in input().split()]
+    m = [int(i) for i in input().split()]
+
+    queue, count = deque([0]), defaultdict(int, {0: 1})
+    while queue:
+        i = queue.popleft()
+        for j in edges[i]:
+            count[j] += 1
+            if count[j] > 1: continue
+            v[j] = gcd(v[i], v[j])
+            queue.append(j)
+    print(*(m[i] - gcd(v[i], m[i]) for i in range(n) if count[i] == 1))
diff --git a/codechef/strch.c b/codechef/strch.c
new file mode 100644
index 0000000..518378e
--- /dev/null
+++ b/codechef/strch.c
@@ -0,0 +1,30 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int main()
+{
+	int t;
+	long n, i, j;
+	long long res;
+	char *s = malloc(1000001), x;
+
+	scanf("%d", &t);
+	while (t--) {
+		scanf("%ld", &n);
+		fgets(s, n, stdin);
+		res = n * (n + 1) / 2;
+		scanf("%s %c", s, &x);
+
+		for (i = 0; i < n; ++i) {
+			if (s[i] == x)
+				continue;
+			for (j = i; j < n && s[j] - x; ++j);
+			res -= (j - i) * (j - i + 1) / 2;
+			i = j;
+		}
+
+		printf("%lld\n", res);
+	}
+
+	return 0;
+}
diff --git a/codechef/subrem.py b/codechef/subrem.py
new file mode 100755
index 0000000..02f11b1
--- /dev/null
+++ b/codechef/subrem.py
@@ -0,0 +1,26 @@
+#!/usr/bin/env python3
+from collections import defaultdict
+
+for t in range(int(input())):
+    n, x = map(int, input().split())
+    a, edges = [int(i) for i in input().split()], defaultdict(list)
+    for _ in range(1, n):
+        u, v = (int(i) - 1 for i in input().split())
+        edges[u].append(v)
+        edges[v].append(u)
+
+    queue, parents, walked = [0], [0] * n, [not i for i in range(n)]
+    for i in queue:
+        for j in edges[i]:
+            if walked[j]: continue
+            walked[j], parents[j] = 1, i
+            queue.append(j)
+
+    net, profit = a.copy(), a.copy()
+    queue.reverse()
+    queue.pop()
+    for i in queue:
+        parent, profit[i] = parents[i], max(net[i], -x, profit[i])
+        net[parent] += net[i]
+        profit[parent] += profit[i]
+    print(max(net[0], -x, profit[0]))
-- 
cgit 1.4.1