Pythonデータ可視化

**Solution Explanation** For every test case we are given * `N` – number of students * `M` – number of subjects * `K` – a student is *smart* if he/she has marks ≥ `K` in **every** subject For each student we have to decide whether he/she is smart or not. -------------------------------------------------------------------- #### Algorithm For each test case ``` read N, M, K smart = 0 repeat N times ok = true repeat M times read x if x < K ok = false if ok smart++ output smart ``` -------------------------------------------------------------------- #### Correctness Proof We prove that the algorithm outputs the number of smart students for every test case. *Lemma 1* For a fixed student the variable `ok` is true after reading all his/her marks **iff** the student has marks ≥ `K` in every subject. *Proof.* `ok` is initialised to true. During the inner loop each mark `x` is examined. If `x < K` the algorithm sets `ok = false`. Thus after the loop `ok` is false exactly when at least one mark is smaller than `K`. Consequently `ok` is true exactly when all marks are ≥ `K`. ∎ *Lemma 2* `smart` is increased exactly for the smart students. *Proof.* After processing a student, by Lemma 1 `ok` is true precisely when the student is smart. The algorithm increments `smart` only in this case, therefore `smart` counts exactly the smart students. ∎ *Theorem* For each test case the algorithm outputs the correct number of smart students. *Proof.* After all `N` students have been processed, by Lemma 2 `smart` equals the number of smart students. The algorithm outputs this value, hence the output is correct. ∎ -------------------------------------------------------------------- #### Complexity Analysis Let `S = N · M` be the total number of marks in a test case. * Time complexity: The algorithm reads each mark once – **O(S)**. * Space complexity: Only a few integer variables are used – **O(1)**. -------------------------------------------------------------------- #### Reference Implementation (Java 17) ```java import java.io.BufferedInputStream; import java.io.IOException; import java.util.StringTokenizer; public class Main { /* fast scanner for integers */ private static class FastScanner { private final BufferedInputStream in = new BufferedInputStream(System.in); private final byte[] buffer = new byte[1 << 16]; private int ptr = 0, len = 0; private int readByte() throws IOException { if (ptr >= len) { len = in.read(buffer); ptr = 0; if (len <= 0) return -1; } return buffer[ptr++]; } int nextInt() throws IOException { int c, sign = 1, val = 0; do { c = readByte(); } while (c <= ' ' && c != -1); // skip whitespace if (c == '-') { // negative numbers sign = -1; c = readByte(); } while (c > ' ') { val = val * 10 + (c - '0'); c = readByte(); } return val * sign; } } public static void main(String[] args) throws Exception { FastScanner fs = new FastScanner(); StringBuilder out = new StringBuilder(); int T = fs.nextInt(); while (T-- > 0) { int N = fs.nextInt(); int M = fs.nextInt(); int K = fs.nextInt(); int smart = 0; for (int i = 0; i < N; i++) { boolean ok = true; for (int j = 0; j < M; j++) { int mark = fs.nextInt(); if (mark < K) ok = false; } if (ok) smart++; } out.append(smart).append('\n'); } System.out.print(out.toString()); } } ``` The program follows exactly the algorithm proven correct above and conforms to the Java 17 standard.