بوت لتتريس والرسوم المتحركة الهندسة العكسية. تحليل المسار المحمول من بطولة البرمجة الثانية

تنسيق الإدخال

تنسيق الإخراج

مثال 1

مثال 2

مثال 3

الملاحظات

 public class CablesSolution { private static final long MODULLO = 2147483647L; public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter pw = new PrintWriter(System.out); int n = in.readInt(); int k = in.readInt(); int m = in.readInt(); DisjointUnionSets dsu = new DisjointUnionSets(n + 1); for (int i = 0; i < k; i++) { int u = in.readInt(); int v = in.readInt(); dsu.union(u, v); } Edge[] edges = new Edge[m]; // (4 + 4 + 8) * 2M = 32M for (int i = 0; i < m; i++) { int u = in.readInt(); int v = in.readInt(); long p = in.readLong(); edges[i] = new Edge(u, v, p); } Arrays.sort(edges); long res = 1; boolean addedEdge = false; for (Edge edge : edges) { if (!dsu.check(edge.getU(), edge.getV())) { dsu.union(edge.getU(), edge.getV()); res = (res * edge.getP()) % MODULLO; addedEdge = true; } } if (!dsu.isJoint()) { res = -1; } else if (!addedEdge) { res = 0; } pw.println(res); pw.flush(); pw.close(); } public static class DisjointUnionSets { private int[] rank; // 4M private int[] parent; // 4M DisjointUnionSets(int size) { rank = new int[size]; parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } int find(int target) { if (parent[target] != target) { parent[target] = find(parent[target]); } return parent[target]; } boolean check(int x, int y) { return find(x) == find(y); } void union(int x, int y) { int xRoot = find(x); int yRoot = find(y); if (xRoot == yRoot) { return; } if (rank[xRoot] < rank[yRoot]) { parent[xRoot] = yRoot; } else if (rank[yRoot] < rank[xRoot]) { parent[yRoot] = xRoot; } else { parent[yRoot] = xRoot; rank[xRoot] = rank[xRoot] + 1; } } boolean isJoint() { int parent = -1; for (int i = 1; i < rank.length; i++) { if (parent == -1) { parent = find(i); } else { if (parent != find(i)) { return false; } } } return true; } } private static class Edge implements Comparable<Edge> { private int u; private int v; private long p; Edge(int u, int v, long p) { this.u = u; this.v = v; this.p = p; } int getU() { return u; } int getV() { return v; } long getP() { return p; } @Override public int compareTo(Edge edge) { return Long.compare(p, edge.p); } } } 

تنسيق الإدخال

تنسيق الإخراج

مثال

الملاحظات

 import copy import math import time import tkinter from enum import Enum FRAMES_PER_SECOND = 60 TIME_BETWEEN_FRAMES = int(1000 / FRAMES_PER_SECOND) class Rectangle(object): def __init__(self, left_x, left_y, width, height, color, angle=0.0): self.center_x = left_x + width / 2 self.center_y = left_y + height / 2 self.width = width self.height = height self.color = color self.angle = angle def get_left_x(self): return self.center_x - self.width / 2 def set_left_x(self, left_x): self.center_x = left_x + self.width / 2 def get_left_y(self): return self.center_y - self.height / 2 def set_left_y(self, left_y): self.center_y = left_y + self.height / 2 left_x = property(get_left_x, set_left_x) left_y = property(get_left_y, set_left_y) class Circle(object): def __init__(self, left_x, left_y, radius, color): self.center_x = left_x + radius self.center_y = left_y + radius self.radius = radius self.color = color self.angle = 0 def get_left_x(self): return self.center_x - self.radius def set_left_x(self, left_x): self.center_x = left_x + self.radius def get_left_y(self): return self.center_y - self.radius def set_left_y(self, left_y): self.center_y = left_y + self.radius left_x = property(get_left_x, set_left_x) left_y = property(get_left_y, set_left_y) class AnimationType(Enum): MOVE = 1 ROTATE = 2 SCALE = 3 class Animation(object): def __init__(self, time, cycle): self.time = time self.cycle = cycle def scale(self, time_spent): return 1 def move(self, time_spent): return 0, 0 def angle(self, time_spent): return 0 def _cycle_progress(self, time_spent): if self.cycle: cycle_time = time_spent % (self.time * 2) if cycle_time > self.time: return 1 - (cycle_time - self.time) / self.time else: return cycle_time / self.time else: if time_spent < self.time: cycle_time = time_spent % self.time return cycle_time / self.time else: return 1 class MoveAnimation(Animation): def __init__(self, figure, to_x, to_y, time, cycle): super().__init__(time, cycle) self.from_x = figure.center_x self.from_y = figure.center_y self.to_x = to_x self.to_y = to_y def move(self, time_spent): cycle_progress = super()._cycle_progress(time_spent) diff_x = self.to_x - self.from_x diff_y = self.to_y - self.from_y return diff_x * cycle_progress, diff_y * cycle_progress class ScaleAnimation(Animation): def __init__(self, destination_scale, time, cycle): super().__init__(time, cycle) self.destination_scale = destination_scale def scale(self, time_spent): cycle_progress = super()._cycle_progress(time_spent) return 1 + (self.destination_scale - 1) * cycle_progress class RotateAnimation(Animation): def __init__(self, rotate_angle, time, cycle): super().__init__(time, cycle) self.rotate_angle = rotate_angle def angle(self, time_spent): cycle_progress = super()._cycle_progress(time_spent) return self.rotate_angle * cycle_progress class Transformer(object): def scale(self, scale): pass def move(self, diff_x, diff_y): pass def rotate(self, angle): pass class RectangleTransformer(Transformer): def __init__(self, rectangle): self.rectangle = rectangle def scale(self, scale): self.rectangle.width = self.rectangle.width * scale self.rectangle.height = self.rectangle.height * scale def move(self, diff_x, diff_y): self.rectangle.center_x = self.rectangle.center_x + diff_x self.rectangle.center_y = self.rectangle.center_y + diff_y def rotate(self, angle): self.rectangle.angle = (self.rectangle.angle + angle) % 360 class CircleTransformer(Transformer): def __init__(self, circle): self.circle = circle def scale(self, scale): self.circle.radius = self.circle.radius * scale def move(self, diff_x, diff_y): self.circle.center_x = self.circle.center_x + diff_x self.circle.center_y = self.circle.center_y + diff_y def rotate(self, angle): pass class Drawer(object): def draw(self, canvas, spent_time): pass class AnimationApplier(object): @staticmethod def apply_animations(spent_time, transformer, animations): for animation in animations: transformer.scale(animation.scale(spent_time)) diff_x, diff_y = animation.move(spent_time) transformer.move(diff_x, diff_y) transformer.rotate(animation.angle(spent_time)) class RectangleDrawer(Drawer): def __init__(self, rectangle, animations): self.rectangle = rectangle self.animations = animations def draw(self, canvas, spent_time): rect = self._transform_rect_with_animations(spent_time) rect_points = self._get_rectangle_points(rect) rotated_points = self._rotate(rect_points, rect.angle, [rect.center_x, rect.center_y]) canvas.create_polygon(rotated_points, fill=rect.color) def _transform_rect_with_animations(self, spent_time): rect = copy.copy(self.rectangle) transformer = RectangleTransformer(rect) AnimationApplier.apply_animations(spent_time, transformer, self.animations) return transformer.rectangle @staticmethod def _get_rectangle_points(rect): half_width = rect.width / 2 half_height = rect.height / 2 return [ [rect.center_x - half_width, rect.center_y - half_height], [rect.center_x - half_width, rect.center_y + half_height], [rect.center_x + half_width, rect.center_y + half_height], [rect.center_x + half_width, rect.center_y - half_height] ] @staticmethod def _rotate(points, angle, center): angle = math.radians(angle) cos_val = math.cos(angle) sin_val = math.sin(angle) cx, cy = center new_points = [] for x_old, y_old in points: x_old -= cx y_old -= cy x_new = x_old * cos_val - y_old * sin_val y_new = x_old * sin_val + y_old * cos_val new_points.append([x_new + cx, y_new + cy]) return new_points class CircleDrawer(Drawer): def __init__(self, circle, animations): self.circle = circle self.animations = animations def draw(self, canvas, spent_time): circle = self._transform_rect_with_animations(spent_time) size = circle.radius * 2 canvas.create_oval(circle.left_x, circle.left_y, circle.left_x + size, circle.left_y + size, fill=circle.color) def _transform_rect_with_animations(self, spent_time): circle = copy.copy(self.circle) transformer = CircleTransformer(circle) AnimationApplier.apply_animations(spent_time, transformer, self.animations) return transformer.circle class Scene(object): def __init__(self, canvas, animated_symbols): self.canvas = canvas self.drawers = self._get_generated_drawers(animated_symbols) @staticmethod def _get_generated_drawers(animated_symbols): drawers = [] for animated_symbol in animated_symbols: figure = animated_symbol.figure animations = animated_symbol.animations if isinstance(figure, Rectangle): drawer = RectangleDrawer(figure, animations) elif isinstance(figure, Circle): drawer = CircleDrawer(figure, animations) else: raise Exception() drawers.append(drawer) return drawers def draw(self, time_spent): self.canvas.delete("all") for drawer in self.drawers: drawer.draw(self.canvas, time_spent) self.canvas.pack() class Timer(object): def __init__(self): self.started_time = None def start(self): self.started_time = self._current_time() def time_spent(self): current_time = self._current_time() return current_time - self.started_time @staticmethod def _current_time(): return int(round(time.time() * 1000)) def scene_loop(window, scene, timer): time_spent = timer.time_spent() scene.draw(time_spent) window.after(TIME_BETWEEN_FRAMES, scene_loop, window, scene, timer) def configure_window_location(window, canvas_width, canvas_height): screen_width = window.winfo_screenwidth() screen_height = window.winfo_screenheight() x = (screen_width / 2) - (canvas_width / 2) y = (screen_height / 2) - (canvas_height / 2) window.geometry('%dx%d+%d+%d' % (canvas_width, canvas_height, x, y)) class AnimatedSymbol(object): def __init__(self, figure, animations): self.figure = figure self.animations = animations class AnimationsParser(object): def parse_animated_symbols(self, file_path): with open(file_path) as f: lines = f.readlines() canvas_width, canvas_height = self._parse_size(lines[0]) symbols_count = int(lines[1]) animated_symbols = [] current = 2 for i in range(symbols_count): figure = self._parse_figure(lines[current]) current += 1 symbol_animations = self._parse_animations(figure, current, lines) current += 1 + len(symbol_animations) animated_symbol = AnimatedSymbol(figure, symbol_animations) animated_symbols.append(animated_symbol) return canvas_width, canvas_height, animated_symbols def _parse_size(self, line): parts = line.split(" ") return int(parts[0]), int(parts[1]) def _parse_animations(self, figure, current, lines): animations = [] animations_count = int(lines[current]) for i in range(animations_count): parts = lines[current + i + 1].split(" ") animation = self._parse_animation(figure, parts) animations.append(animation) return animations def _parse_figure(self, line): parts = line.split(" ") if parts[0] == 'rectangle': center_x = float(parts[1]) center_y = float(parts[2]) width = float(parts[3]) height = float(parts[4]) angle = float(parts[5]) color = parts[6].replace('\n', '') figure = Rectangle(center_x - width / 2, center_y - height / 2, width, height, color, angle) elif parts[0] == 'circle': center_x = float(parts[1]) center_y = float(parts[2]) radius = float(parts[3]) color = parts[4].replace('\n', '') figure = Circle(center_x - radius, center_y - radius, radius, color) else: raise Exception() return figure def _parse_animation(self, figure, parts): if parts[0] == "move": animation = self._parse_move_animation(figure, parts) elif parts[0] == "scale": animation = self._parse_scale_animation(parts) elif parts[0] == "rotate": animation = self._parse_rotate_animation(parts) else: raise Exception() return animation @staticmethod def _parse_move_animation(figure, parts): to_x = float(parts[1]) to_y = float(parts[2]) time = float(parts[3]) cycle = len(parts) >= 5 return MoveAnimation(figure, to_x, to_y, time, cycle) @staticmethod def _parse_scale_animation(parts): destination_scale = float(parts[1]) time = float(parts[2]) cycle = len(parts) >= 4 return ScaleAnimation(destination_scale, time, cycle) @staticmethod def _parse_rotate_animation(parts): rotate_angle = float(parts[1]) time = float(parts[2]) cycle = len(parts) >= 4 return RotateAnimation(rotate_angle, time, cycle) def main(): canvas_width, canvas_height, animated_symbols = \ AnimationsParser().parse_animated_symbols('animation_path.txt') window = tkinter.Tk() configure_window_location(window, canvas_width, canvas_height) canvas = tkinter.Canvas(window, width=canvas_width, height=canvas_height) scene = Scene(canvas, animated_symbols) timer = Timer() timer.start() window.after(TIME_BETWEEN_FRAMES, scene_loop, window, scene, timer) window.mainloop() if __name__ == "__main__": main() 

تنسيق الإدخال

تنسيق الإخراج

مثال

الملاحظات