{
ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'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.