Soluții trimise

Pentru a descoperi ieșirea din Marele Labirint, exploratorul trebuie să descifreze o hartă antică. Harta este reprezentată sub forma unui tablou bidimensional cu 𝑁 linii și 𝑀 coloane, cu elemente numere naturale nenule. Liniile sunt numerotate de la 1 la 𝑁 (de sus în jos), iar coloanele de la 1 la 𝑀 (de la stânga la dreapta).

Definim un mapat ca fiind un pătrat descris de o poziție (𝑖,𝑗) numită colț principal și o latură de lungime 𝐿, unde 1 ≤ 𝐿 ≤ min(𝑖, 𝑗). Mapatul acoperă toate celulele având indicii (𝑥,𝑦), unde 𝑖 − 𝐿 + 1 ≤ 𝑥 ≤ 𝑖 și 𝑗 − 𝐿 + 1 ≤ 𝑦 ≤ 𝑗, adică este un pătrat de 𝐿 × 𝐿 celule al cărui colt, dreapta-jos este chiar (𝑖,𝑗).

Valoarea unui mapat se calculează astfel:

1. Se determină suma tuturor elementelor din pătrat, notată cu 𝑆.
2. Valoarea mapatului este produsul dintre 𝑆 și valoarea de la poziția (𝑖,𝑗).

Fixând o lungime 𝐿 și o linie 𝑖 (cu 𝑖 ≥ 𝐿), pentru fiecare coloană 𝑗 ≥ 𝐿, notăm cu 𝐴[𝑗] valoarea mapatului cu colțul principal la coordonatele (𝑖,𝑗) și latura de lungime 𝐿. O secvență de mapate situate pe linia i este determinată de doi indici, 𝑠𝑡 și 𝑑𝑟. Definim suma secvenței de mapate ca fiind 𝐴[𝑠𝑡] + 𝐴[𝑠𝑡 +1] + ··· + 𝐴[𝑑𝑟] , cu 𝐿 ≤ 𝑠𝑡 ≤ 𝑑𝑟 ≤ 𝑀.

Se dau 𝑞 întrebări de tipul 1 și 𝑝 întrebări de tipul 2.

1. Întrebare de tipul 1. Cunoscându-se trei valori 𝐿, 𝑖 și maxVal, determinați lungimea maximă a unei secvențe de mapate cu latura de lungime 𝐿, situate pe linia 𝑖 și având suma secvenței de mapate mai mică sau egală cu maxVal.
2. Întrebare de tipul 2. Cunoscându-se patru valori 𝐿, 𝑖, minVal și maxVal, determinați numărul secvențelor de mapate cu latura de lungime 𝐿, situate pe linia 𝑖 și având suma secvenței de mapate cuprinsă între minVal și maxVal.