In this HackerRank Two Robots problem solution, You have a warehouse with M containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be 1 meter apart. You also have 2 robots that can pick up 1 piece of candy and transport it between any two containers.
The robots take instructions in the form of queries consisting of two integers, Ma and Mb, respectively. To execute a query, a robot travels to container Ma, picks up 1 candy, transports it to container Mb, and then stops at Mb until it receives another query.
Calculate the minimum total distance the robots must travel to execute N queries in order.
Problem solution in Python.
def twoRobots(m, queries): prev_bot = queries[0][0] mintotal = 0 containers = [0]*(m+1) for a,b in queries: distance = abs(a-b) traveled = abs(prev_bot-a) minMoves = mintotal for k,v in enumerate(containers): minMoves = min( minMoves, abs(k-a)+v) containers[k] += traveled+distance containers[prev_bot] = minMoves+distance mintotal += traveled+distance prev_bot = b return min(containers) for t in range(int(input().strip())): m,n=(map(int,input().rstrip().split())) queries = [] for _ in range(n): queries.append(tuple(map(int, input().rstrip().split()))) print(twoRobots(m, tuple(queries)))
Problem solution in Java.
// practice with kaiboy import java.io.*; import java.util.*; public class two_robots extends PrintWriter { two_robots() { super(System.out); } Scanner sc = new Scanner(System.in); public static void main(String[] $) { two_robots o = new two_robots(); o.main(); o.flush(); } static final int INF = 0x3f3f3f3f; void main() { int t = sc.nextInt(); while (t-- > 0) { int m = sc.nextInt(); int n = sc.nextInt(); int[] aa = new int[n]; int[] bb = new int[n]; for (int i = 0; i < n; i++) { aa[i] = sc.nextInt(); bb[i] = sc.nextInt(); } int[] dd = new int[n]; dd[0] = Math.abs(aa[0] - bb[0]); for (int i = 1; i < n; i++) dd[i] = dd[i - 1] + Math.abs(bb[i - 1] - aa[i]) + Math.abs(aa[i] - bb[i]); int ans = dd[n - 1]; int[][] dp = new int[n][m + 1]; for (int i = 0; i < n; i++) for (int x = 1; x <= m; x++) dp[i][x] = INF; for (int u = 1; u < n; u++) for (int v = 1; u + v <= n; v++) { int i = u + v - 1; int x = bb[u - 1]; dp[i][x] = Math.min(dp[i][x], dd[u + v - 1] - Math.abs(bb[u - 1] - aa[u])); } for (int i = 0; i < n - 1; i++) for (int x = 1; x <= m; x++) { int d = dp[i][x]; if (d == INF) continue; int y = bb[i]; dp[i + 1][x] = Math.min(dp[i + 1][x], d + Math.abs(y - aa[i + 1]) + Math.abs(aa[i + 1] - bb[i + 1])); dp[i + 1][y] = Math.min(dp[i + 1][y], d + Math.abs(x - aa[i + 1]) + Math.abs(aa[i + 1] - bb[i + 1])); } for (int x = 1; x <= m; x++) ans = Math.min(ans, dp[n - 1][x]); println(ans); } } }
Problem solution in C++.
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> using namespace std; const int Infinity = 1000000007; const int NotInit = -1; struct Query { int from, to, dist; Query(int from = 0, int to = 0, int dist = 0) : from(from), to(to), dist(dist) {} void scan() { scanf("%d%d", &from, &to); dist = abs(from - to); } }; vector<Query> queries; vector<vector<int>> dp; int minDistance(int x, int y) { if (dp[x][y] != NotInit) return dp[x][y]; int result = Infinity; auto queryId = max(x, y); auto& query = queries[queryId]; if (min(x, y) + 1 < queryId) { result = x == queryId ? minDistance(x - 1, y) : minDistance(x, y - 1); result += query.dist; result += abs(queries[queryId - 1].to - query.from); } else { for (int i = 0; i < queryId-1; ++i) { int prevDistance = x == queryId ? minDistance(i, y) : minDistance(x, i); int newDistance = i == 0 ? 0 : abs(query.from - queries[i].to); result = min(result, prevDistance + newDistance + query.dist); } } dp[x][y] = result; return result; } void solve() { int n, m; scanf("%d%d", &m, &n); queries.resize(n+1); for (int i = 1; i <= n; ++i) { queries[i].scan(); } dp.resize(n+1); for (int i = 0; i <= n; ++i) { dp[i].assign(n+1, NotInit); } dp[0][1] = queries[1].dist; dp[1][0] = queries[1].dist; int ans = Infinity; for (int i = 0; i <= n; ++i) { ans = min(ans, minDistance(i, n)); ans = min(ans, minDistance(n, i)); } printf("%dn", ans); } int main(void) { //freopen("input.txt", "rt", stdin); //freopen("output.txt", "wt", stdout); int t; scanf("%d", &t); while(t --> 0) { solve(); } return 0; }
Problem solution in C.
#include<stdio.h> int main() { int t, k; scanf("%d", &t); for( k = 0 ; k < t ; k++ ) { int m, n, i, j, a, b; scanf("%d %d", &m, &n); int ar[m+1], r2 = 0, temp, min; for( j = 0 ; j <= m ; j++ ) { ar[j] = 0; } for( i = 0 ; i < n ; i++ ) { scanf("%d %d", &a, &b); min = ar[0] + abs(a-b); for( j = 1 ; j <= m ; j++ ) { if( ar[j] == 0 ) { continue; } temp = ar[j] + abs(j-a) + abs(a-b); if( temp < min ) { min = temp; } } if( r2 == 0 ) { temp = abs(a-b); } else { temp = abs(r2-a) + abs(a-b); } ar[0] += temp; for( j = 1 ; j <= m ; j++ ) { if( ar[j] == 0 ) { continue; } ar[j] += temp; } if( ar[r2] == 0 || ar[r2] > min ) { ar[r2] = min; } r2 = b; } min = ar[0]; for( j = 1 ; j <= m ; j++ ) { if( ar[j] != 0 && ar[j] < min ) { min = ar[j]; } } printf("%dn", min); } return 0; }