Soluţia problemei Tigri

Recomandăm înţelegerea editorialului acestei probleme în toate detaliile sale, întrucât a fost scris cu scop educaţional. Pentru o cât mai bună instruire, vă suntem disponibili prin intermediul forumului să vă răspundem la întrebările care ar răsări.

Ignorând pentru moment tipurile de date ale variabilelor X, Y, lei şi tigri, operaţiile în C++ pe care am vrea să le efectuăm sunt:

I

/// iniţializare
lei = 0;
tigri = 0;

D

/// depositum X
if (lei + X >= 0) {
    lei += X;
}

E

/// emptum X Y
if (lei - X * Y >= 0 && tigri + X >= 0) {
    lei -= X * Y;
    tigri += X;
}

V

/// vendere X Y
if (lei + X * Y >= 0 && tigri - X >= 0) {
    lei += X * Y;
    tigri -= X;
}

Ce tipuri de date să folosim?

Dacă s-ar fi garantat că X, Y, lei şi tigri pot fi reprezentate pe tipul de date int din C/C++, ar fi fost suficient să le declarăm ca fiind de tip int. Dar garanţia nu este dată decât pentru lei, prin urmare implementarea banală nu va obţine 100 de puncte.

De asemenea, soluţia nu stă în întrebuinţarea unui tip de date precum BigInteger din Java sau implementarea de mână a numerelor mari, din pricina limitei de timp. Fără să ne folosim de garanţia că 0 ≤ lei < 2³¹ (1), nu putem rezolva complet problema.

Din fericire, operaţiile sunt fie efectuate complet, fie practic ignorate. La finalul unei operaţii efectuate, (1) se respectă. Prin urmare, orice operaţie efecutată are proprietatea că 0 ≤ lei + X < 2³¹ pentru D, 0 ≤ lei - X * Y < 2³¹ pentru E şi 0 ≤ lei + X * Y < 2³¹ pentru V. Luând în calcul invariantul (1), deducem că:

• Un D efectuat are proprietatea că -2³¹ < X < 2³¹.
• Un E sau V efectuat are proprietatea că -2³¹ < X * Y < 2³¹. Atunci când X este nenul, mai deducem că -2³¹ < X, Y < 2³¹. Atunci când X este nul, observăm că valoarea lui Y nu contează - mai mult, putem chiar ignora operaţia.

Ce avem de înţeles din aceste proprietăţi şi observaţii? Că atunci când X este 0 sau când X sau Y sunt, în modul, mai mari sau egali ca 2³¹, ignorăm direct operaţia. Codul de la D, E sau V nici nu este apelat în aceste cazuri. Prin urmare, atunci când codul este apelat, putem ţine lei, X şi Y pe tipul de date int, cu atenţie să calculăm produsul X * Y pe long long.

Despre tigri, acum putem şti că, în modul, este mai mic sau egal cu suma modulelor tuturor valorilor X din fişier, prin urmare -N * (2³¹-1) ≤ tigri ≤ N * (2³¹-1). Deci tigri poate fi reţinut ca un întreg pe tipul de date long long.

Cum să citim fişierul de intrare?

Linie cu linie, desigur, dar cum să facem în aşa fel încât să decidem dacă să ignorăm direct operaţia sau să obţinem în variabilele X şi Y valorile corespunzătoare şi să lăsăm implementarea de la D, E şi V să-şi facă treaba?

Sunt două metode. În timp ce procesăm caracter cu caracter cifrele (şi semnul „-”) care compun numerele X şi Y din fişier,

• fie reţinem într-o variabilă de tip bool, numită, să zicem, valid, dacă cifrele procesate compun valori care dau şansa ca operaţia să aibă rost să o efectuăm, iar apoi condiţionăm în funcţie de valoarea lui valid dacă intrăm în codul de la D, E sau V;
• fie, în caz că ne dăm seama că operaţia poate fi direct ignorată, să ne asigurăm că valorile finale ale lui X şi Y vor fi în aşa fel încât codul de la D, E sau V să nu producă schimbare în valorile lui lei şi tigri. Codul va fi apelat oricum, deci practic nu mai ignorăm direct operaţia, dar ne asigurăm că urmează să fie ignorată.

Desigur, trebuie reţinut primul caracter al liniei ( d, e sau v) pentru a şti care dintre codurile D, E şi V să le efectuăm, dar şi ca să ştim câte numere să citim.

În ambele variante, se recomandă folosirea unei funcţii care să citească un număr şi care să fie apelată pentru X şi, dacă e nevoie, pentru Y. De asemenea, avem grijă să reţinem dacă întâlnim semnul „-” înainte cifrelor, respectiv să înmulţim modulul numărului citit mai apoi cu -1, dacă e nevoie.

În prima variantă, numărul nenegativ nr (adică viitorul modul al lui X sau Y) este actualizat după fiecare cifră citită 0 ≤ cifrăNouă ≤ 9 (pe care o deducem ca fiind egală cu valoarea ASCII a caracterului citit - verificat ca fiind cifră -, minus valoarea ASCII a caracterului „0”) în felul următor:

/// 1 şiftat la stânga de 31 de ori înseamnă 2^31 când e reţinut pe „long long”, dar nu şi când e reţinut pe „int”
static const long long doiLa31 = 1LL << 31;
/// „nr” e de tip „int”
if (10LL * nr + cifrăNouă < doiLa31) {
    nr = 10 * nr + cifrăNouă; /// nu mai e nevoie de conversia la „long long”, pentru că ştim că rezultatul se încadrează pe „int”
} else {
    valid = false; /// nu mai e nevoie să actualizăm „nr” pentru că nu vom mai folosi conţinutul variabilei la actualizarea lui „lei” sau „tigri”
}

(În plus, atunci când X este 0 iar valid este încă true după citirea lui Y, putem modifica valoarea lui valid în false. Mai pe larg despre de ce nu e nevoie de acest pas, urmăriţi a doua variantă de implementare propusă.)

În a doua variantă, vom reţine nr (respectiv X şi Y) pe long long şi îş vom plafona la o valoare precum const long long big = doiLa31 (condiţiile lui big, sunt, de fapt, ca pătratul său să intre pe long long şi să fie mai mare sau egal ca 2³¹). Plafonarea, mai bine cunoscută în varianta sa din engleză („to cap”), înseamnă că, după fiecare actualizare a valorii nr, inserăm următoarea bucată de cod:

#include <algorithm>
nr = std::min(nr, big);

Observăm că, în felul acesta, codul de la D, E şi V are aceleaşi urmări ca şi când valorile lui X sau Y ar fi fost cele din fişierul de intrare. Motivul e acela că, dacă X sau Y din fişier are modulul mai mare sau egal ca 2³¹, operaţia oricum va fi ignorată, iar misiunea codului de a nu modifica variabilele lei şi tigri e la fel de bine îndeplinită atunci când X sau Y (respectiv) este fix 2³¹.