Текущ брой на Списание ИнфоМан
 


Международна олимпиада по информатика 2005, Задача 2.1. BIRTHDAY

Уловието на задачата може да прочетете тук.

Решение

За дадената пермутация трябва да се разгледат възможностите децата да се разположат по посока на часовниковата стрелка (ППЧС) и обратно (ППОЧС), след което от тези две разположения да се вземе по-доброто. Ще опишем как се решава задачата, когато децата са разположени ППЧС. За разположение ППОЧС решението е аналогично.

Нека отбележим с P = p1, p2,.., pn пермутацията на децата. Ако фиксираме детeто p1 да се намира на позиция f, то е еднозначно определено къде точно трябва да седят всички останали деца. Нека за дадено fдвижението на детето iсе описва чрез числото df,i, като това число може да е положително или отрицателно в зависимост от посоката на движение. Например числото 3 означава преместване 3 позиции в посока по часовниковата стрелка, а числото -5 обозначава преместване 5 позиции в обратна посока. Нека най-голямото цяло число не по-голямо от n/2бележим с m, а най-малкото цяло число не по-малко от n/2бележим с М. При всяко движение детето може да избере дали да се придвижи до целта си в посока по или обратно на часовниковата стрелка в зависимост от това кое му костава по-малко стъпки. Тогава можем да твърдим, че 1-Mdf,i m.

Стойностите за df,iмогат лесно да бъдат пресметнати по следния начин:

df,pi = min(a, n-a), като а = (f+i-1-pi) mod n.

За фиксирано fдефинираме множеството Sf по следния начин: Sf = {df,i : i = 1,2,…,n}.Това множество съдържа всички нужни движения, които децата трябва да извършат, за да се постигне пермутацията P и детето p1 да се намира на позиция f. За да оценим оптималността на едно таковапридвижване е важно къде в интервала [1-M;m] се намират най-малкото и най-голямото число от Sf. Едно решение е толкова по-оптимално, колкото по-далеч от съответния край на интервала е по-голямото по абсолютна стойност число. Това от своя страна означава, че оптималното решение на задачата ще съдържа колкото се може по-дълги и равни помежду си два празни подинтервала в двата края на интервала [1-M;m].

Ако е дадено някакво Sfлесно може да се пресметне Sf+1като се “преместят” елементите на Sf. Получава се така, че дадена стойност xсе замества с x+1, ако x<mи се замества с 1-M, ако x = m. Казано иначе, ако изобразим интервала [1-M;m]и множеството Sf върху числовата ос, преходът между Sf и Sf+1 ще изглежда като преместване на точките от Sf с една позиция надясно, а тези, които след преместването излязат от интервала отиват в неговото начало.

Така ако е даденo някаквoпроизволно S0, всички останали Sfмогат да се пресметнат като последователно се “местят” елементите на S0 надясно.Следователно ако се намери най-голямото множество от последователни числа, които не се срещат в S0 (нека те са Cна брой), може да се избере такова изместване Sf, че половините на този интервал от числа да са разположени в двата края на [1-M, m], което, както отбелязахме, би ни дало и най-доброто решение. От тук следва, че отговорът на задачата е най-голямото цяло число, което е не по-голямо от (n-C)/2.

Примерна реализация


#include <stdio.h>
#include <string.h>

#define MAXN 1000100

int ar[MAXN]; // Input permutation
int br[MAXN]; // Position reference array
int have[MAXN]; // Available distances
// we need to move (modulo N)

int N;

int solve () {

    int i,j,t,max = 0;
    
    memset(have,0,sizeof(have));

    // Counting the distances we
    // have to move to get the
    // order right (modulo N)
    // starting with permutation
    // 1, 2, 3, ..., N-1, N
    for (i=1; i<=N; i++) {
        have[ (N+br[i]-i)%N ] = 1;
    }

    // Calculating the number of
    // missing consecutive distances
    // in the range [j..N] and [1..i]
    for (i=0; have[i] == 0; i++) ;
    max += i;
    for (j=N-1; have[j] == 0; j--) ;
    max += N-j;

    // Calculating all other missing
    // consecutive distance in the
    // range [i..j] and finding the
    // longest range
    for (i++; i<j; i++) {
    
        t = 0;
        while (i<j && have[i] == 0) {
              i++;
              t++;
        }
        if (max < t) max = t;
    }

    return (N-max)/2;
}
int reverse() {
    int i,j,temp;
    for (i=1,j=N; i<j; i++,j--) {
        temp = ar[i];
        ar[i] = ar[j];
        ar[j] = temp;
    }
    return 0;
}

int calc() {
    int i;
    for (i=1; i<=N; i++) {
        br[ar[i]] = i;
    }
    return 0;
}

int main () {
    int i,a,ans,t;


    // Reading input
    scanf("%d",&N);
    for (i=1; i<=N; i++) {
        scanf("%d",&a);
        ar[i] = a;
    }
    
    // Calculating reference array
    calc();

    // Solving clockwise case
    ans = solve();

    // Reversing the permutation
    // to solve the second case
    reverse();
    calc();

    // Solving the counterclockwise case
    t = solve();

    // Comparing the two cases
    if (ans > t) ans = t;
    printf("%d\n",ans);
    return 0;
}

Автор: Анализ - Антон Димитров, Реализация - Веселин Кулев


обратно към брой 27