Anonymous avatar Anonymous committed e528a35

round 1b

Comments (0)

Files changed (3)

+from __future__ import division
+
+import sys
+
+def solve(J):
+    X = sum(J)
+    J = [float(j)/X for j in J]
+    Js = list(sorted(J))
+    T = 2.0 / len(J)
+
+    while Js[-1] >= T:
+        Js.pop()
+        T = (sum(Js) + 1.0) / len(Js)
+
+    res = []
+    for j in J:
+        if j >= T:
+            res.append(0)
+        else:
+            res.append(100*(T-j))
+    return res
+
+if __name__ == '__main__':
+    NP = int(sys.stdin.readline())
+    for i in xrange(NP):
+        L = map(int, sys.stdin.readline().split())
+        print("Case #%d: %s" % (i+1, " ".join(map(str, solve(L[1:])))))
+from __future__ import division, print_function
+from heapq import heappush, heappop
+import sys
+
+def solve(H, N, M, ceils, fllors):
+    Q = [(0,0,0)]
+    done = {}
+
+    def move(t, ax, ay):
+        h = H - t
+        if t == 0:
+            nt = 0
+        elif h - floors[y][x] >= 20:
+            nt = t+10
+        else:
+            nt = t+100
+        if (ax,ay) in done and done[(ax,ay)] <= nt:
+            return
+        done[(ax,ay)] = nt
+        #print(nt, ax, ay)
+        heappush(Q, (nt, ax, ay))
+
+    def trymove(ax, ay):
+        if ax < 0 or ay < 0 or ax >= M or ay >= N:
+            return
+        c = min(ceils[ay][ax], ceils[y][x])
+        if c - max(floors[y][x], floors[ay][ax]) < 50:
+            return
+        if c - h >= 50:
+            move(t, ax, ay)
+        else:
+            move(t + 50-(c-h), ax, ay)
+
+    while Q:
+        t, x, y = heappop(Q)
+        if x == M-1 and y == N-1:
+            return t/10.0
+
+        h = H - t
+        trymove(x-1, y)
+        trymove(x, y-1)
+        trymove(x+1, y)
+        trymove(x, y+1)
+    return -1
+
+
+def read_split():
+    return sys.stdin.readline().split()
+
+if __name__ == '__main__':
+    NP = int(sys.stdin.readline())
+    for i in xrange(NP):
+        H, N, M = map(int, read_split())
+        ceils = [map(int, read_split()) for _ in xrange(N)]
+        floors = [map(int, read_split()) for _ in xrange(N)]
+        print("Case #%d: %s" % (i+1, solve(H, N, M, ceils, floors)))
+#!/usr/bin/env rdmd
+
+import std.stdio;
+import std.array;
+import std.conv;
+import std.string;
+import std.algorithm;
+
+
+bool rec(int[] s, int x, int y, int[] xs, int[] ys)
+{
+    if (x == y && x != 0) {
+        writeln(join(map!(to!string)(xs), " "));
+        writeln(join(map!(to!string)(ys), " "));
+        return true;
+    }
+    if (s.empty) { return false; }
+
+    if (rec(s[1..$], x, y, xs, ys)) return true;
+    if (rec(s[1..$], x+s[0], y, xs~[s[0]], ys)) return true;
+    if (rec(s[1..$], x, y+s[0], xs, ys~[s[0]])) return true;
+    return false;
+}
+
+void solve(int[] s)
+{
+    size_t L = s.length;
+    if (!rec(s, 0, 0, [], [])) {
+        writeln("Impossible");
+    }
+}
+
+void main()
+{
+    int T = to!int(chomp(readln()));
+    for (int t=1; t<=T; ++t) {
+        string L = readln();
+        int[] s=array(map!(to!int)(split(chomp(L))));
+        write("Case #", t, ": ");
+        solve(s[1..$]);
+    }
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.