{
ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'02 - 16 ноември 2002
ТЕМА ЗА 9 – 10 КЛАС (ГРУПА B)

Задача 1.  КАНДИДАТИ

На избори за кмет се явили 5 кандидата P, Q, R, S и Т – по един представител
на всяка от партиите A, B, C, D и E. Редът, по който са написани кандидатите
не е задължително да указва принадлежност към съответна партия в дадената
по-горе редица от партии. Определете какви могат да бъдат резултатите от
изборите (кой кандидат кое поредно място е заел) и кой кандидат от коя партия
е, ако е известно следното:

Представителите на партия B и на партия C са се класирали на първо и на пето
място (но без да уточняваме кой кое от тези две места e заел) и никой от тях
не носи име Q или R. Кандидатът T е заел по-предно място от S. P не е
представител на C. Представителят на партия D е заел по-предно място от R, но
е след Q.

Създайте текстов файл с име CANDID.TXT, който да съдържа толкова редове,
колкото са намерените от вас възможности за удовлетворяване на условията на
задачата. Всеки ред трябва да съдържа по 5 двойки главни латински букви,
определящи партията и името на представителя й (първо буквата за партията,
после буквата на кандидата). Във всеки от тези редове двойките букви трябва да
са подредени по реда на класирането на изборите – първата двойка да представя
партията и представителя й, заели първото място на изборите и т.н. Буквите в
двойките, както и самите двойки трябва да бъдат отделени с точно един
интервал. Така всеки ред трябва да съдържа по 19 знака, включително
интервалите.

Правила за оценяване:

Ако сте намерили правилно всички възможности, получавате максималния брой
точки за задачата. При намерени по-малко възможности, но удовлетворяващи
условията, получавате съответна пропорционална част от максималния брой точки.
За всяка посочена от вас грешна възможност, от вашата оценка се отнемат по 20
точки, като ще се спази изискването оценка ви да не стане отрицателна.

РЕШЕНИЕ:

Тази задача изисква единствено предаването на изходен файл, съдържанието на
който да бъде оценен. Ето защо, не е нужно никакво “хитро” решение. В същност,
задачата дори може да бъде решена без ползването на компютър, но това разбира
се би било излишна загуба на време.

Едно много добро правило за състезателни задачи казва, че ако една задача може
да се реши с “груба сила”, без значение дали има по-бързо решение, то трябва
да се използва груба сила (така ще има повече време за другите задачи).

Разглежданото тук решение генерира всички възможни пермутации (нареждания) на
партиите относно заетите места на изборите и за всяко нареждане на партиите
генерира всички възможни пермутации на кандидатите относно местата на които са
се класирали. При всяка конфигурация получаваме кой кандидат на кое място се е
класирал и коя партия кое място е заела. Така стигаме до съответствие между
партии и кандидати, защото една партия и нейният кандидат заемат едно и също
място. Единственото нещо което трябва да направим е да проверим дали
конфигурацията отговаря на информацията от условието (кой кандидат преди кой
е, коя партия на кое място може да бъде и т.н.).

Имайки 5 партии и 5 кандидата, ние получаваме 5!*5!=120*120=14400
конфигурации, които трябва да проверим. Това е толкова малко, че дори няма
смисъл да си правим труда да генерираме пермутации на N елемента със сложност
O(N!), а може да използвам по-лесно генериране със сложност O(N^N). Дори така,
решението ще работи под 1 секунда на компютрите, които използваме днес.

Следователно това решение е задоволително дори ако не се искаше изходен файл
за проверка, а програма която да го генерира в реално време. Това още един път
показва “мъдростта” на правилото за използване на груба сила за решаването на
задачи, когато това е възможно.

Масивът Par, индексите на който са имената на париите, помни на кое място е
всяка партия. Масивът Kan, индексите на който са имената на кандидатите, помни
на кое място е всеки кандидат. Масивите MestaP и MestaK помнят съответно кое
място от коя партия и кой кандидат е заето. Всичко друго се вижда лесно в
самото решение.

Kristiyan Haralambiev
}

program Candidates;
var
        F                       : Text;
        Par                     : array['A'..'E'] of Byte;
        Kan                     : array['P'..'T'] of Byte;
        MestaP, MestaK          : array[1..5] of Char;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure CheckAnswer;
var
        I                       : Byte;
begin
  if ( ((Par['B']=1)and(Par['C']=5)) or ((Par['B']=5)and(Par['C']=1)) ) and
     (MestaK[Par['B']]<>'Q') and (MestaK[Par['B']]<>'R') and
     (MestaK[Par['C']]<>'Q') and (MestaK[Par['C']]<>'R') and
     (Kan['T']<Kan['S']) and
     (MestaP[Kan['P']]<>'C') and
     (Par['D']<Kan['R']) and (Par['D']>Kan['Q'])
  then begin
    Write(F, MestaP[1], ' ', MestaK[1]);
    for I := 2 to 5 do Write(F, ' ', MestaP[I], ' ', MestaK[I]);
    WriteLn(F);
  end;
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure SolveKan(I : Byte);
var
        C                       : Char;
begin
  if I > 5 then CheckAnswer
  else
    for C := 'P' to 'T' do
      if Kan[C] = 0 then begin
        Kan[C] := I;
        MestaK[I] := C;

        SolveKan(I+1);

        MestaK[I] := ' '; //debug feature
        Kan[C] := 0;
      end;
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure SolvePar(I : Byte);
var
        C                       : Char;
begin
  if I > 5
    then SolveKan(1)
  else
    for C := 'A' to 'E' do
      if Par[C] = 0 then begin
        Par[C] := I;
        MestaP[I] := C;

        SolvePar(I+1);

        MestaP[I] := ' '; //debug feature
        Par[C] := 0;
      end;
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure Solve;
begin
  FillChar(Par, SizeOf(Par), 0);
  FillChar(Kan, SizeOf(Kan), 0);

  SolvePar(1);
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  Assign(F, 'candid.txt'); ReWrite(F);

  Solve;

  Close(F);
end.