Submission #143153

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
143153	2019-08-13 09:07:33	mariusnicoli	Mate (COCI18_mate)	C++14	100 / 100	543 ms	53552 KiB

mate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
La aceasta problema numarul de interogari este foarte mare, ceea ce ne duce
cu gandul sa precalculam rezultatele pentru a putea raspunde in o(1)
vom face asta in vectorul sol
sol[L][p-'a'][u-'a'] = cate cuvinte de lungime L au penultima litera
a p-a a alfabetului si ultima litera a u-a. Apar mai sus constructiile -'a'
pentru ca noi vom tine a doua si a treia dimensiune intre 0 si 25.
In prima etapa vom calcula D[i][j][k] = cate cuvinte incep de la pozitia i
sau dupa ea si care se termina in literele jk, in aceasta ordine.
Trebuie sa intelegem bine semnificatia dinamicelor:
- la sol primul indice este lungime de cuvant iar la D el este pozitie din srul dat
- la sol al doilea si al treile a indice reprezinta litere ale alfabetului si nu pozitii
Calculam intai pe D si apoi vom vedea cum il folosim pentru a obtine pe sol
Pentru calculul lui D parcurgem cu i indicii din sirul dat invers
si daca la pozitia i avem litera j, D[i][j][ultima] = D[i][j+1][ultima] + R[i+1][ultima]
unde R[i+1][ultima] = de cate ori apare litera "ultima" dupa pozitia j
Pe R il calculam tot invers, R[i][ultima] = 1 = R[i+1][ultima], daca s[i] = ultima
si R[i][ultima] = R[i+1][ultima] in caz contrar.
Semnificatia formulei de mai sus pentru D este ca daca la pozitia i este
chiar litera j, ne intereseaza de cate ori apare litera ultima dupa pozitia curenta,
acesta fiind numarul de perechi noi de forma j, ultima (nu uitam ca pepozitia i este litera j) care se adauga
In celalalt caz,D[i][j][ultima] = D[i+1][j][ultima], deci ce vine din urma
Asa calculat D, sa vedem cum il obtinem pe sol.
pentru sol[L][p][u], ne-ar interesa aparitiile in sirul s ale literei p.
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

mate.cpp: In function 'int main()':
mate.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (t=0;t<poz[j].size();t++) {
                      ~^~~~~~~~~~~~~~
mate.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s+1);
     ~~~~~^~~~~~~~~~~
mate.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &t);
     ~~~~~^~~~~~~~~~~~
mate.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %c %c", &L, &p, &u);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100