circular

Time limit: 0.25s
Memory limit: 256MB
Input: circular.in
Output: circular.out


O imprimantă circulară are litere mari ale alfabetului englezesc dispuse circular de la AA la ZZ. Imprimanta are un indicator care inițial este plasat la litera AA.
Pentru a tipări o literă indicatorul imprimantei se mișcă la stânga sau dreapta. Mișcarea indicatorului către o literă alăturată aflată la stânga sau la dreapta literei curente se realizează într-o secundă. De exemplu: pentru a tipări șirul BCYBCY sunt necesare 66 secunde. Imprimanta va alege întotdeauna sensul cel mai avantajos de deplasare, astfel încât timpul de deplasare să fie minim.
Imprimanta tipărește literele în două culori: roșu sau albastru. Unele litere se tipăresc cu cerneală roșie, restul cu cerneală albastră. Pentru simplitate le vom numi litere roșii și litere albastre.
Fiind date un șir de litere albastre nu neapărat distincte și mulțimea literelor roșii ale imprimantei, să se calculeze:

  1. Care este timpul pentru tipărirea la imprimanta circulară a șirului de litere albastre.
  2. Să se insereze între oricare două litere albastre aflate pe poziții consecutive câte o literă roșie astfel încât să se obțină timpul minim pentru tipărire și să se afișeze:
    • timpul minim;
    • numărul de șiruri distincte care sunt tipărite cu timp minim;
    • șirul minim lexicografic dintre toate șirurile ce sunt tipărite în acest timp.

Date de intrare

Fișierul circular.in conține:

  1. pe prima linie un număr natural cc cu valori posibile 11 sau 22 reprezentând cerința problemei;
  2. pe a doua linie un șir de litere albastre, nu neapărat distincte;
  3. pe a treia linie mulțimea literelor roșii distincte în ordine alfabetică.

Date de ieșire

În fișierul circular.out se va afișa în funcție de cerință:

  • Dacă c=1c = 1, un singur număr natural reprezentând timpul necesar pentru tipărirea la imprimantă a șirului de litere albastre.
  • Dacă c=2c = 2, se vor tipări trei rezultate, fiecare pe câte o linie:
    • timpul minim pentru tipărire conform cerinței a doua;
    • numărul de șiruri distincte care sunt tipărite cu timp minim modulo 666 013\text{modulo }666\ 013;
    • șirul minim lexicografic ce obține acest timp.

Restricții

  • Cele două șiruri conțin doar litere mari ale alfabetului englez.
  • Lungimea șirului de litere albastre nu depășește 50 00050\ 000 de litere.
  • Mulțimea literelor roșii nu depășește 2525 de litere, care sunt distincte și afișate în ordine alfabetică.
  • Toate celelalte litere care nu se regăsesc în mulțimea literelor roșii, sunt albastre.
  • Pentru cazul c=2c = 2 se acordă punctaj parțial astfel:
    • 25%25\% din punctaj, pentru afișarea timpului minim;
    • 25%25\% din punctaj, pentru afișarea numărului de șiruri ce obțin timpul minim;
    • 50%50\% din punctaj, pentru afișarea șirului minim lexicografic.
  • Atenție! Pentru obținerea punctajului la cerința a doua, pentru orice test, în fișierul de ieșire trebuie să existe exact trei linii care respectă formatul cerut.
  • Cerința 1 valorează 24 de puncte, iar cerința 2 valorează 76 de puncte.

Exemplul 1

circular.in

1
BBTH
AEIOU

circular.out

21

Explicație

Timpul de tipărire al șirului BBTH\color{blue} BBTH este 2121 și se obține astfel:

  • de la AA la B=1B = 1 secundă
  • de la BB la B=0B = 0 secunde
  • de la BB la T=8T = 8 secunde
  • de la TT la H=12H = 12 secunde

Exemplul 2

circular.in

2
BBTH
AEIOU

circular.out

23
4
BABATIH

Explicație

Timpul minim pentru tipărirea la imprimantă este 2323 și se obține pentru șirul BABATIH\color{blue}B \color{red}A \color{blue}B \color{red}A \color{blue}T \color{red}I \color{blue}H astfel:

  • de la AA la B=1B = 1 secundă
  • de la BB la A=1A = 1 secundă
  • de la AA la B=1B = 1 secundă
  • de la BB la A=1A = 1 secundă
  • de la AA la T=7T = 7 secunde
  • de la TT la I=11I = 11 secunde
  • de la II la H=1H = 1 secundă

în total 2323 de secunde.
Avem 44 șiruri pentru care se obține timp minim la tipărire: BABATIH\color{blue}B \color{red}A \color{blue}B \color{red}A \color{blue}T \color{red}I \color{blue}H, BABATOH\color{blue}B \color{red}A \color{blue}B \color{red}A \color{blue}T \color{red}O \color{blue}H, BABUTIH\color{blue}B \color{red}A \color{blue}B \color{red}U \color{blue}T \color{red}I \color{blue}H, BABUTOH\color{blue}B \color{red}A \color{blue}B \color{red}U \color{blue}T \color{red}O \color{blue}H.
Prima soluție în ordine lexicografică este BABATIH\color{blue}B \color{red}A \color{blue}B \color{red}A \color{blue}T \color{red}I \color{blue}H.

Exemplul 3

circular.in

2
AMYMAMAMY
BCDEFGHIJKLNOPQRSTUVWX

circular.out

96
568708
ABMNYNMBABMBABMNY

Explicație

Timpul minim de tipărire este 9696.
Avem 214 358 881214\ 358\ 881 șiruri distincte, iar 214 358 881 modulo 666 013=568 708214\ 358\ 881 \text{ modulo } 666\ 013 = 568\ 708.
Prima soluție în ordine lexicografică este ABMNYNMBABMBABMNY\color{blue}A \color{red}B \color{blue}M \color{red}N \color{blue}Y \color{red}N \color{blue}M \color{red}B \color{blue}A \color{red}B \color{blue}M \color{red}B \color{blue}A \color{red}B \color{blue}M \color{red}N \color{blue}Y.

Problem info

ID: 284

Editor: ezluci

Author:

Source: OJI 2022 X: Problema 1

Tags:

OJI 2022 X

Log in or sign up to be able to send submissions!