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("%d\n", 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("%d\n", min);
}
return 0;
}
0 Comments