# PBinfo #4097 – circular1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

O imprimantă circulară are litere mari ale alfabetului englezesc dispuse circular de la A la Z. Imprimanta are un indicator care inițial este plasat la litera A.



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 BCY mișcarea indicatorului se va face către dreapta de la A la B într-o secundă, apoi de la B la C într-o secundă, apoi către stânga de la C la Y în 4 secunde. În total pentru a tipări șirul BCY sunt necesare 6 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. 

Cerința
Fiind date un șir de litere albastre nu neapărat distincte și mulțimea literelor roșii ale imprimantei, să se calculeze:


#* Care este timpul pentru tipărirea la imprimantă circulară a șirului de litere albastre.

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 de intrare circular.in conține:


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

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


Dacă c=1, un singur număr natural reprezentând timpul necesar pentru tipărirea la imprimantă a șirului de litere albastre.
Dacă c=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 666013, șirul minim lexicografic ce obține acest timp.

Restricții și precizări

Cele două șiruri conțin doar litere mari ale alfabetului englez
Lungimea șirului de litere albastre nu depășește 50.000 de litere
Mulțimea literelor roșii nu depășește 25 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 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.
pentru 24 de puncte c = 1
pentru 76 de puncte c = 2

Exemplul 1:
circular.in

1
BBTH
AEIOU
circular.out

21
Explicație
Timpul de tipărire al șirului BBTH este 21 și se obține astfel:


de la A la B = 1 secundă
de la B la B = 0 secunde
de la B la T = 8 secunde
de la T la H = 12 secunde

Exemplul 2:
circular.in

2
BBTH
AEIOU
circular.out

23
4
BABATIH
Explicație
Timpul minim pentru tipărirea la imprimantă este 23 și se obține pentru șirul BABATIH astfel:
de la A la B = 1 secundă
de la B la A = 1 secundă
de la A la B = 1 secundă
de la B la A = 1 secundă
de la A la T = 7 secunde
de la T la I = 11 secunde
de la I la H = 1 secundă
în total 23 de secunde.
Avem 4 șiruri pentru care se obține timp minim la tipărire: BABATIH, BABATOH, BABUTIH, BABUTOH. Prima soluție în ordine lexicografică este BABATIH.

Exemplul 3:
circular.in

2
AMYMAMAMY
BCDEFGHIJKLNOPQRSTUVWX
circular.out

96
568708
ABMNYNMBABMBABMNY
Explicație
Timpul minim de tipărire este 96. Avem 214.358.881 șiruri distincte, iar 214358881 mod 666013 = 568708. Prima soluție în ordine lexicografică este ABMNYNMBABMBABMNY.

## Cod sursă C++

```cpp
/// Boca Alina Gabriela - Colegiul National de Informatica Tudor Vianu Bucuresti
#include <fstream>
#include<cmath>
using namespace std;
ifstream cin("circular.in");
ofstream cout("circular.out");
int a[26][26],v[26];
long long circular(string s)
{
    int cost=0,n;
    char j='A';
    n=s.size();
    for(int i=0; i<n; i++)
    {
        if(j<s[i])
        {
            if(s[i]-j<'Z'-s[i]+j-64)
                cost+=s[i]-j;
            else
                cost+='Z'-s[i]+j-64;
        }
        else
        {
            if(j-s[i]<'Z'-j+s[i]-64)
                cost+=j-s[i];
            else
                cost+='Z'-j+s[i]-64;
        }
        j=s[i];
    }
    return cost;
}
int main()
{
    int c;
    cin>>c;
    string p, t,rez;
    cin>>p>>t;
    if(c==1)
    {
        cout<<circular(p);
    }
    else
    {
        int i,j,k=0,y=1;
        string alf="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        for(i=0; i<26; i++)
        {
            if(alf[i]==t[k])
            {
                v[k]=i;
                k++;
            }
            for(j=0; j<26; j++)
                if(i<j)
                {
                    a[i][j]=min(abs(i-j), abs(26-j+i));
                }
                else
                {
                    a[i][j]=min(abs(i-j), abs(26-i+j));
                }
        }
        int nrtotal=1,costtotal=0,q;
        int x;
        for(j=0; j<alf.size(); j++)
            if(p[0]==alf[j])
            {
                k=j;
                break;
            }
        costtotal=min(k,26-k);
        rez.push_back(p[0]);
        for(i=1; i<p.size(); i++)
        {
            for(j=0; j<alf.size(); j++)
                if(p[i]==alf[j])
                {
                    q=j;
                    break;
                }
            int mincost=60,nr=0;
            for(j=0; j<t.size(); j++)
            {
                if (mincost>a[k][v[j]]+a[q][v[j]])
                {
                    mincost=a[k][v[j]]+a[q][v[j]];
                    nr=1;
                    x=v[j];
                }
                else if(a[k][v[j]]+a[q][v[j]]==mincost)
                {
                    nr++;
                    if(x>v[j])
                    {
                        x=v[j];
                    }
                }
            }
            rez.push_back(alf[x]);
            nrtotal*=(nr%666013);
            nrtotal=nrtotal%666013;
            costtotal+=mincost;
              rez.push_back(p[i]);
            k=q;
        }
        cout<<costtotal<<endl<<nrtotal<<endl;
        cout<<rez;
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4097)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4097/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4097/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)