Lista de probleme 9

Considerăm că toate punctele de coordonate întregi din plan sunt colorate în negru, cu excepţia a n puncte care sunt colorate în roşu. Două puncte roşii aflate pe aceeaşi linie orizontală sau pe aceeaşi linie verticală (adică puncte care au aceeaşi ordonată sau aceeaşi abscisă) pot fi unite printr-un segment. Colorăm în roşu toate punctele de coordonate întregi de pe acest segment. Repetăm operaţia cât timp se obţin puncte roşii noi. Cunoscând coordonatele celor n puncte care erau iniţial roşii, aflaţi numărul maxim de puncte roşii care vor exista în final.

Se consideră o matrice dreptunghiulară A cu m linii şi n coloane cu valori 0 sau 1, liniile şi coloanele fiind numerotate de la 1 la m, respectiv de la 1 la n. Numim dreptunghi de colţuri (x1, y1) (x2,y2) cu x1 < x2 şi y1 < y2 mulţimea elementelor A[i][j] cu x1 ≤ i ≤ x2 si y1 ≤ j ≤ y2. Numim perimetru al dreptunghiului de colţuri (x1, y1) (x2, y2) mulţimea elementelor A[i][j] pentru care (i = x1 şi y1 ≤ j ≤ y2) sau (i = x2 şi y1 ≤ j ≤ y2) sau (j = y1 şi x1 ≤ i ≤ x2) sau (j = y2 şi x1 ≤ i ≤ x2).

Determinaţi diferenţa maximă dintre numărul de elemente egale cu 1 şi numărul de elemente egale cu 0 aflate pe perimetrul aceluiaşi dreptunghi, precum şi numărul de dreptunghiuri pentru care se obţine această diferenţă.

Se consideră un tablou bidimensional cu m linii şi n coloane. Se numeşte traseu în V o parcurgere prin elementele tabloului astfel:

• se pleacă întotdeauna dintr-un element de pe prima linie a tabloului, se ajunge în final într-un alt element de pe prima linie a tabloului, trecând prin cel puţin 3 elemente, fără a trece printr-un element de mai multe ori;
• parcurgerea elementelor tabloului se face în forma unei singure litere V ca în desen, dintr-un element putându-se trece doar într-un alt element imediat vecin pe diagonală.

Fiecare element al tabloului conţine valori întregi. La parcurgerea traseului se calculează suma elementelor de pe traseu.

Determinaţi traseul în V care are suma maximă. În cazul în care există mai multe trasee de sumă maximă, se va alege traseul care parcurge cele mai puţine elemente. Dacă şi în acest caz există mai multe soluţii, se alege traseul cel mai din stânga (cel cu indicele coloanei de pornire cel mai mic).

Gigel se distrează construind şiruri crescătoare de numere din mulţimea {1,2,…,n}. La un moment dat observă că unele şiruri, de cel puţin k termeni (k ≥ 3), au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru n ≥ 22:
2, 3, 4
1, 5, 9, 13
7, 10, 13, 16, 19, 22
Dându-se numărul natural n ajutați-l pe Gigel să numere câte astfel de șiruri poate să construiască.

Ovi este un băieţel foarte isteţ căruia îi place să scrie pe asfalt cu creta şi să ţopăie. El desenează cu cretă roşie un dreptunghi de lăţime exact 2 metri şi lungime N metri, pe care îl împarte în pătrate egale de latură 1 metru, unele laturi interioare fiind desenate cu cretă roşie, iar restul laturilor interioare cu cretă albă. Ovi porneşte din pătratul aflat în colţul stânga sus al dreptunghiului, sărind dintr-un pătrat în altul vecin pe linie sau coloană, cu condiţia ca latura care desparte cele două pătrate să nu fie colorată în roşu. El îşi doreşte ca prin sărituri succesive să ajungă în toate pătratele dreptunghiului, dar a observat că numai pentru anumite variante de colorare a laturilor pătratelor reuşeşte acest lucru.

Ajutaţi-l pe Ovi să numere câte posibilităţi de colorare în roşu a unor laturi interioare ale pătratelor sunt astfel încât plecând din colţul stânga sus să poată ajunge prin sărituri în oricare alt pătrat.

Renumitul arhitect Prăbuşilă doreşte să construiască unul din cele mai interesante turnuri de pe planetă. Acest turn, în mod cu totul deosebit, va avea etaje de diverse lăţimi, între 1 şi 100, numere întregi. Prăbuşilă s-a hotărât deja ce dimensiune va avea fiecare din etajele turnului, dar nu şi cum să le aşeze pe orizontală. El ar dori mai întâi să ştie câte variante are.

Scrieţi un program care să determine în conformitate cu decizia directorului, diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipa LNA şi suma punctajelor la matematică ale elevilor din echipă, precum şi suma tuturor punctajelor elevilor din echipa LNA.

Balaurul Arhirel se decide să înveţe biologie, aşa că doreşte să cumpere manualul de clasa a X-a. Din păcate, acesta nu se mai găsește pe piaţă, dar Balaurul reuşeşte să găsească o copie la un prieten. După ce începe să citească, Balaurul Arhirel observă că există greşeli în copia prietenului, iar într-un impuls de energie, se hotărăşte să corecteze manualul. El are la dispoziţie un dicţionar de M cuvinte dintre care trebuie să extragă variante pentru cuvântul greşit. Asupra cuvântului greşit balaurul poate să facă următoarele schimbări în așa fel încât acesta să ajungă la o variantă din dicționar:
– poate șterge o literă;
– poate insera o literă;
– poate schimba o literă în altă literă.
Totuși, Balaurul Arhirel este leneş, aşa că nu doreşte să opereze mai mult de K schimbări în cuvântul greșit pentru a-l aduce la o formă corectă (existentă în dicționar).
Ajutaţi-l pe Balaurul Arhirel să afle care dintre cuvintele din dicţionar ar putea fi variante ale cuvântului greşit.

Balaurului Arhirel nu îi plac prea mult şirurile care nu sunt ordonate. Din acest motiv, nu poate să suporte permutările de N elemente, aşa că se decide să le sorteze şi pentru asta inventează o metodă proprie de sortare.
El ia iniţial un şir S care reprezintă o permutare de ordin N. Caută în şirul S cel mai mic (min) şi cel mai mare element (max). Să considerăm că min se află în şirul S pe poziţia pmin, iar max pe poziţia pmax. Să notăm cu x minimul dintre pmin şi pmax, iar cu y maximul dintre pmin şi pmax. Şirul S a fost astfel partiționat în alte trei şiruri, S1, S2, S3 care pot avea fiecare zero elemente, un element sau mai multe elemente. Şirul S1 începe la prima poziţie din şir şi se termină la poziţia x-1. Şirul S2 începe la poziţia x+1 şi se termină la poziţia y-1. Şirul S3 începe la poziţia y+1 şi se termină la ultima poziţie din şir.
Balaurul Arhirel mută valoarea min la capătul din stânga al lui S, iar valoarea max la capătul din dreapta al şirului S şi reia sortarea pentru fiecare din şirurile S1, S2, S3.
Evident, această metodă nu va funcţiona întotdeauna pentru sortarea unei permutări.
Spre exemplu, pentru şirul S = (3 4 1 6 5 2), se găseşte min = 1 şi max = 6, iar S1 = (3 4), S2 = (), S3 = (5 2). Se mută min şi max la capetele lui S: S = (1 3 4 5 2 6) şi se procedează la sortarea pe rând a şirurilor S1, S2, S3. S1 este sortat, S2 nu are elemente, iar S3 va deveni S3 = (2 5). În final, S = (1 3 4 2 5 6).
Ajutaţi-l pe Balaurul Arhirel să afle câte dintre permutările de N elemente pot fi sortate prin metoda sa.