Each subproblem of this problem is to be solved separately. They both share the same principle: you are given a formal specification of a task and a set of programs. Each of those programs contains a function named solve that attempts to solve the given task. All programs are written in an easily-readable subset of Python, and shouldn’t contain any language-specific tricks or gotchas.
Your goal is to determine which of those programs correctly solve the given task. We consider a program correct if, for every valid input, the program terminates after a finite number of steps (even if that number of steps is huge) and the returned answer is correct.
Given are two integers n and k (1 ≤ k ≤ n ≤ 100). The task in this subproblem is to compute the value of the binomial coefficient $n\choose k$. In other words, compute the number of ways in which we can choose a k-element subset of an n-element set. For example, for n = 10 and k = 2 we should compute the value 45. (Note that Python can handle arbitrarily large integers.)
The programs are stored in files named j1_01.py through j1_11.py. Each program contains a function solve that expects 2 parameters: the integers n and k.
The output file you submit as your solution to the easy subproblem J1 must contain exactly 11 whitespace-separated words. The i-th word of your output describes the i-th program j1_i.py. The word must be “good” if the program correctly solves all valid instances, or “bad” otherwise.
Given is a simple connected undirected weighted graph. The task of this subproblem is to find the length of the shortest path between two given vertices of the graph.
The programs are stored in files named j2_01.py through j2_15.py. Each program contains a function solve that expects 5 parameters:
n: the number of vertices in the graph (2 ≤ n ≤ 100). Vertices are numbered 0 through n − 1.m: the number of edges in the graph (n − 1 ≤ m ≤ n(n − 1)/2).edge_list: the list of all m edges of the graph. Each edge is a triple (p, q, w) where p and q are the vertices that are connected by the edge (p ≠ q) and w is a positive integer which denotes the edge length (1 ≤ w ≤ 1 000). Note that no two edges share the same pair {p, q}.start and end: the two distinct endpoints of the path we are looking for.For your convenience, we also provide the files j2_sample.{in,out} and j2_read_input.py. The in file contains a sample instance, the out contains its correct solution. The third file contains the function read_input that loads an instance from standard input and parses it into arguments expected by solve.
The output file you submit as your solution to the hard subproblem J2 must contain exactly 15 whitespace-separated words. The i-th word describes the i-th program j2_i.py. The word must be one of “good”, “ones”, and “bad”. Here, “ones” means that the program is not correct in general, but it does correctly solve all instances with unit-length edges (i.e., ones where for each edge we have w = 1). Answer “bad” if neither “good” nor “ones” applies.
If you make a submission that is syntactically correct but does not get all answers right, our grader will tell you how many programs were classified correctly.
Note that you can only make at most 7 submissions for the easy subproblem J1, and at most 10 submissions for the hard subproblem J2. Be careful.