Cerinta completa

You have N soldiers numbered from 1 to N. Each of your soldiers is either a liar or a truthful person. You have M sets of information about them. Each set of information tells you the number of liars among a certain range of your soldiers. Let L be the total number of your liar soldiers. Since you can’t find the exact value of L, you want to find the minimum and maximum value of L.

Input Format

  • The first line of the input contains two integers N and M.
  • Each of next M lines contains three integers:
    A B C where the set of soldiers numbered as {A, A+1, A+2, …, B}, exactly C of them are liars. (1 <= Ai <= Bi <= n) and (0 <= Ci <= Bi-Ai).

Note: N and M are not more than 101, and it is guaranteed the given informations is satisfiable.

Output Format
Print two integers Lmin and Lmax to the output.

Sample Input #1 

3 2
1 2 1
2 3 1

Sample Output #1

1 2

Sample Input #2 

20 11
3 8 4
1 9 6
1 13 9
5 11 5
4 19 12
8 13 5
4 8 4
7 9 2
10 13 3
7 16 7
14 19 4

Sample Output #2

13 14

Explanation
In the first input, the initial line is “3 2”, i.e. that there are 3 soldiers and we have 2 sets of information. The next line says there is one liar in the set of soldiers {1, 2}. The final line says there is one liar in the set {2,3}. There are two possibilities for this scenario: Soldiers number 1 and 3 are liars or soldier number 2 is liar.
So the minimum number of liars is 1 and maximum number of liars is 2. Hence the answer, 1 2.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            this.in = is;
        }

        private int read() 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;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();

        int v = n + 1;
        long INF = (long) 1e15;
        long[][] dist = new long[v][v];
        for (int i = 0; i < v; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int i = 1; i <= n; i++) {
            // p[i] - p[i-1] <= 1
            if (1 < dist[i - 1][i]) dist[i - 1][i] = 1;
            // p[i-1] - p[i] <= 0
            if (0 < dist[i][i - 1]) dist[i][i - 1] = 0;
        }

        for (int i = 0; i < m; i++) {
            int a = fs.nextInt();
            int b = fs.nextInt();
            int c = fs.nextInt();
            int u = a - 1;
            int w = b;
            if (c < dist[u][w]) dist[u][w] = c;
            if (-c < dist[w][u]) dist[w][u] = -c;
        }

        for (int k = 0; k < v; k++) {
            for (int i = 0; i < v; i++) {
                long dik = dist[i][k];
                if (dik >= INF) continue;
                for (int j = 0; j < v; j++) {
                    long nd = dik + dist[k][j];
                    if (nd < dist[i][j]) dist[i][j] = nd;
                }
            }
        }

        long lMin = -dist[n][0];
        long lMax = dist[0][n];
        System.out.println(lMin + " " + lMax);
    }
}

Scor obtinut: 1.0

Submission ID: 464614790

Link challenge: https://www.hackerrank.com/challenges/liars/problem

Liars