Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2448
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2448
Postman
By OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
A postman is responsible for giving the orders in the street Joãozinho. On the company policy, orders must be delivered in the same order they were sent, even if that is not the quickest way. Tired of going up and down that road so many times, our friend wants to show the company how long it takes to deliver orders in an attempt to overturn this policy.
Joãozinho's street has N homes. Of course, the houses are numbered in an orderly fashion (not necessarily consecutive numbers). Considering that houses have approximately the same size, you can assume that the postman takes one unit of time to walk from one house to the immediately neighboring house.
There M orders for this street, which should be delivered in the same order in which they arrived. Each order contains the number of the house where it should be delivered.
Write a program that determines how long the postman will take to deliver all orders, assuming that when the time starts ticking, it is the first house (the lower number), and the time finishes telling when all orders were delivered (even if the postman is not back in the first house). You can disregard the time to put the order in the mailbox (that is, if it has only an order, to the first house, the answer to the problem is zero).
Input
The first line contains two integers, N and M (1 ≤ N, M ≤ 45,000), respectively the number of houses and the number of orders. The second line contains N (1 ≤ Ni ≤ 109) integers in strictly ascending order, indicating the numbers of the houses. The third line contains M (1 ≤ Mi ≤ 109) integers indicating the numbers of the houses where the orders are to be delivered, in the order given at the entrance.
Output
Your program should produce a single line containing a single integer, as long as the postman will take to deliver all orders in the correct order, assuming that it starts in the fewest home.
| Input Sample | Output Sample |
|
5 5 1 5 10 20 40 10 20 10 40 1 |
10 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define MAX 45100
long casas[MAX];
long cartas[MAX];
int busca(long *, long, long);
int main (void)
{
long tmp;
long i, x, z;
long n, m, tempo;
scanf("%ld %ld", &n, &m);
for (i = 1; i < = n; ++i)
scanf("%ld", &casas[i]);
z = 1;
tempo = 0;
for (i = 1; i < = m; ++i)
{
scanf("%ld", &tmp);
x = busca(casas, n, tmp);
tempo += abs(x - z);
z = x;
}
printf("%ld\n", tempo);
}
int busca(long *casas, long tam, long chave)
{
int hi, low, mid;
hi = tam; low = 1;
while (low < = hi)
{
mid = (low + hi) / 2;
if (chave < casas[mid])
hi = mid - 1;
else if (chave > casas[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
Input
1 5 10 20 40
10 20 10 40 1
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <map>
using namespace std;
int abs(int x) {
if (x > 0) return x;
return -x;
}
int main() {
int i, n, m, davez, resposta = 0, atual = 1;
map < int, int> mapa;
scanf("%d %d", &n, &m);
for (i = 1; i < = n; i++) {
scanf("%d", &davez);
mapa[davez] = i;
}
for (i = 0; i < m; i++) {
scanf("%d", &davez);
resposta += abs(mapa[davez] - atual);
atual = mapa[davez];
}
printf("%d\n", resposta);
return 0;
}
Input
1 5 10 20 40
10 20 10 40 1
Output