Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1228
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1228
Start Grid
Maratona de Programação da SBC 
Brazil
Timelimit: 1
Nlogonia will hold the sensational world final of the Formula 17 drivers championship. Competitors line up at the start and compete for the race. You will have access to the start and finish grids. The question is to determine the minimum number of overtakes that were made during the competition.
Input
The input contains several test cases. Each test case uses three lines. The first line of a test case contains an integer N (2 ≤ N ≤ 24) indicating the number of competitors. Each competitor is identified by a number from 1 to N. The second line contains the N competitors in order of the starting grid. The third line of each case has the same competitors, but now in the order they finish the race.
Output
For each test case print a line containing a single integer, the minimum number of overtakes necessary to get from the starting grid to the finishing grid.
| Sample Input | Sample Output |
|
5 |
3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#define true 1
#define falas 0
#define MAXSIZE 30
int main (void)
{
int n, i, j;
int chegada[MAXSIZE];
int largada[MAXSIZE];
int final[MAXSIZE];
while (scanf("%d", &n) != EOF)
{
for (i = 0; i < n; ++i)
scanf("%d", &largada[i]);
for (i = 0; i < n; ++i)
scanf("%d", &chegada[i]);
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (largada[i] == chegada[j])
{
final[j] = i + 1;
break;
}
// for (i = 0; i < n; ++i)
// printf("%d ", final[i]);
int ultra = 0;
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j)
if (final[i] > final[j])
{
final[j] = final[j] ^ final[i];
final[i] = final[i] ^ final[j];
final[j] = final[j] ^ final[i];
++ultra;
}
printf("%d\n", ultra);
}
}
Input
1 2 3 4 5
3 1 2 5 4
5
3 1 2 5 4
1 2 3 4 5
5
3 1 2 5 4
5 3 2 1 4
Output
3
4
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
int main(){
int largada[24];
int chegada[24];
int comp[24];
int fim, n, aux;
while(scanf("%d",&n) != EOF){
fim = 0;
aux = 0;
while(aux < n){
scanf("%d", &largada[aux]);
aux++;
}
aux = 0;
while(aux < n){
scanf("%d", &chegada[aux]);
aux++;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(largada[i] == chegada[j]){
comp[j] = i + 25;
}
}
}
for(int k = 0; k < n; k++){
for(int l = k+1; l < n; l++>{
if(comp[k] > comp[l]){
aux = comp[l];
comp[l] = comp[k];
comp[k] = aux;
fim++;
}
}
}
printf("%d\n",fim);
}
return 0;
}
Input
1 2 3 4 5
3 1 2 5 4
5
3 1 2 5 4
1 2 3 4 5
5
3 1 2 5 4
5 3 2 1 4
Output
3
4
#3 Code Example with Python Programming
Code -
Python Programming
while True:
try: n = int(input())
except EOFError: break
c = 0
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
while a != b:
for i in range(n):
if a[i] != b[i]:
t = b.index(a[i])
p = b[t]
b.remove(b[t])
b.insert(i, p)
c += abs(t-i)
break
print(c)
Input
1 2 3 4 5
3 1 2 5 4
5
3 1 2 5 4
1 2 3 4 5
5
3 1 2 5 4
5 3 2 1 4
Output
3
4