Bina Nusantara Programming Contest for High School Students 2008

Problem : A | B | C | D | E | F | G | H

G - Perubahan Minimal

Biaya minimum yang diperlukan untuk mengubah barisan input menjadi barisan yang diminta (1..N) bisa didapatkan dengan terlebih dahulu mengurutkan semua bilangan pada barisan input dan kemudian mengubah setiap bilangan menjadi 1..N sesuai dengan urutannya. Cara ini menjamin tidak akan terjadi overlaping yang tidak diperlukan ketika mengubah bilangan.

Statistik Problem G
YES = 9
NO - Wrong Answer = 44
NO - Time Limit Exceeded = 14
NO - Run-time Error = 1
NO - Compile Error = 0

Solusi C/C++ (oleh Suhendry Effendy)

#include <cstdio>
#include <algorithm>
using namespace std;

int arr[10005];

int main()
{
  int T;
  scanf( "%d", &T );
  
  while ( T-- ) {
    int n;
    scanf( "%d", &n );
    for ( int i = 0; i < n; i++ )
      scanf( "%d", &arr[i] );

    sort(arr,arr+n);

    int ans = 0;
    for ( int i = 0; i < n; i++ )
      ans += abs(i + 1 - arr[i]);

    printf( "%d\n", ans );
  }
  
  return 0;
}

Solusi Pascal (oleh Eko Wibowo)

type
  tlist = array[1..10000] of longint;
var
  t, n, i, ans : longint;
  arr : tlist;

// diambil dari contoh pada free-pascal
procedure sort(var a:tlist;l,r: longint);
var i,j,x,y: longint;
begin
  i := l;
  j := r;
  x := a[(l + r) div 2];
  repeat
     while a[i] < x do i := i + 1;
     while x < a[j] do j := j - 1;
     if i <= j then
     begin
       y := a[i];
       a[i] := a[j];
       a[j] := y;
       i := i + 1;
       j := j - 1;
     end;
   until i > j;
   if l < j then sort(a,l,j);
   if i < r then sort(a,i,r);
end;

begin
  read(t);
  while t > 0 do
  begin
    t := t - 1;
    read(n);
    for i := 1 to n do read(arr[i]);
    sort(arr,1,n);
    ans := 0;
    for i := 1 to n do ans := ans + abs(arr[i] - i);
    writeln(ans);
  end;
end.