Lista de probleme 3

Fermierul Amooot merge la magazinul de furaje pentru a achiziționa amestecuri de iarbă pentru pășunatul vacilor sale. Vânzătorul Popică, viclean de fel, îi prezintă un șir V de N oferte; însă, pentru ca Amooot să poată achiziționa hrana, acesta va trebui neapărat să selecteze o subsecvență canonică de oferte!

Spunem că o subsecvență A[i], A[i+1], … , A[j] , 1 ≤ i ≤ j ≤ N este canonică dacă A[k] % A[i] = 0, pentru orice k, i ≤ k ≤ j. De exemplu, în șirul (3, 4, 2, 10, 4, 12, 3), subsecvențe canonice sunt (2, 10) sau (2, 10, 4, 12), dar nu și subsecvența (10, 4, 12).

Văzând condițiile impuse de Popică, Amooot își pune două întrebări:

1. Care este cea mai lungă subsecvență canonică din V?
2. Câte subsecvențe canonice există în V?

În Grădina Botanică Regală „Etherea”, cercetătorii studiază o specie rară de cireș japonez, numită Sakura Tennyo. Grădina este reprezentată printr-o matrice cu N linii și M coloane, în care fiecare celulă corespunde unei parcele de pământ. Inițial, toate parcelele au fertilitatea 0.

În grădină au loc, pe rând, Q înfloriri. O înflorire din celula (r, c), având puterea K, eliberează polen care, purtat de curenții de aer, se poate răspândi în cel mult 4 zone triunghiulare, după reguli precizate.

Determinați matricea finală a fertilității după aplicarea tuturor celor Q înfloriri.

Înainte de prima cursă din sezon, Marele Premiu al orașului Necleab, Carol și Luis pot să facă mașina mai rapidă folosindu-se de un șir de n numere întregi, indexat de la 0 la n − 1, și patru numere: k, p, q și r. Carol selectează o mulțime care conține indicii unei subsecvențe de lungime q · k din șirul de n numere. Indicele de start al acestei subsecvențe, notat cu i, trebuie să îndeplinească condiția 𝑖 % 𝑘 = 𝑟. Luis selectează inițial o mulțime care conține indicii unei subsecvențe de lungime 𝑝 din șirul de n numere. Ulterior, el adaugă indici astfel încât, la final, un indice i aparține mulțimii dacă și numai dacă indicele 𝑖 + 𝑘 aparține aceleiași mulțimi, ori de câte ori ambii indici sunt cuprinși între 0 și n − 1. Pentru ca în sfârșit anul ăsta să fie anul lor, piloții vor să facă mașina cât mai rapidă. Urmând regulile descrise mai sus, care este viteza maximă cu care piloții pot îmbunătăți mașina?