Lista de probleme 2

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr x, iar altul un număr y mai mare sau egal cu x. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la x și y. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă greșesc la calcule, în schimb, trebuie să găsiți numărul pe care l-ar putea spune al doilea. Să se calculeze pentru fiecare întrebare p minimum, pentru care relația este satisfăcută.

În jurul muzeului din orașul Smallville exista un gard ce conține N scânduri de înălțimi diferite. Putem spune că scândura i are înălțimea Hi. Directorul muzeului le-a cerut angajaților să vopsească acest gard cu un număr minim de culori, astfel încât să se respecte următoarea condiție: pentru un număr întreg K cunoscut, orice secvență de K scânduri consecutive nu trebuie să conțină două scânduri de aceeași înălțime, colorate identic. Scrieţi un program care să găsească numărul minim de culori ce vor fi folosite pentru a colora gardul.