Cerinta completa

You have a warehouse with containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be meter apart. You also have robots that can pick up piece of candy and transport it between any two containers.

The robots take instructions in the form of queries consisting of two integers, and , respectively. To execute a query, a robot travels to container , picks up candy, transports it to container , and then stops at until it receives another query.

Calculate the minimum total distance the robots must travel to execute queries in order.

Note: You choose which robot executes each query.

Input Format

The first line contains a single integer, (the number of test cases); each of the test cases is described over lines.

The first line of a test case has two space-separated integers, (the number of containers) and (the number of queries).
The subsequent lines each contain two space-separated integers, and , respectively; each line describes the query.

Constraints

Output Format

On a new line for each test case, print an integer denoting the minimum total distance that the robots must travel to execute the queries in order.

Sample Input

3
5 4
1 5
3 2
4 1
2 4
4 2
1 2
4 3
10 3
2 4
5 4
9 8

Sample Output

11
2
5

Explanation

In this explanation, we refer to the two robots as and , each container as , and the total distance traveled for each query as .

Note: For the first query a robot executes, there is no travel distance. For each subsequent query that robot executes, it must travel from the location where it completed its last query.

Test Case 0:
The minimum distance traveled is :

  • Robot:

    meters.
  • Robot:

    meter.
  • Robot:

    meters.
  • Robot:

    meters.

Sum the distances traveled () and print the result on a new line.

Test Case 1:

  • Robot:

    meters.
  • Robot:

    meters.

Sum the distances traveled () and print the result on a new line.

Test Case 2:

  • Robot:

    meters.
  • Robot:

    meters.
  • Robot:

    meters.

Sum the distances traveled () and print the result on a new line.

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 t = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (t-- > 0) {
            int m = fs.nextInt(); // not needed in transitions
            int n = fs.nextInt();

            int[] a = new int[n + 1];
            int[] b = new int[n + 1];
            long base = 0;
            for (int i = 1; i <= n; i++) {
                a[i] = fs.nextInt();
                b[i] = fs.nextInt();
                base += Math.abs(a[i] - b[i]);
            }

            long INF = Long.MAX_VALUE / 4;
            long[] dp = new long[n + 1];
            Arrays.fill(dp, INF);
            dp[0] = 0; // after first query, second robot unused

            for (int i = 2; i <= n; i++) {
                long[] ndp = new long[n + 1];
                Arrays.fill(ndp, INF);

                for (int j = 0; j <= i - 2; j++) {
                    long cur = dp[j];
                    if (cur >= INF) continue;

                    // Main robot (at b[i-1]) does query i
                    long same = cur + Math.abs(b[i - 1] - a[i]);
                    if (same < ndp[j]) ndp[j] = same;

                    // Other robot does query i
                    long moveOther = (j == 0) ? 0 : Math.abs(b[j] - a[i]);
                    long sw = cur + moveOther;
                    if (sw < ndp[i - 1]) ndp[i - 1] = sw;
                }

                dp = ndp;
            }

            long extra = Long.MAX_VALUE;
            if (n == 1) {
                extra = 0;
            } else {
                for (int j = 0; j <= n - 1; j++) {
                    if (dp[j] < extra) extra = dp[j];
                }
            }

            out.append(base + extra).append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464616277

Link challenge: https://www.hackerrank.com/challenges/two-robots/problem

Two Robots