Lista de probleme 14

Pe un cerc se află N poziții, consecutiv așezate și notate cu 1,2,3,...,N. Distanțele între oricare două poziții vecine sunt egale cu un pas. Un robot se află inițial la poziția 1. În una dintre poziții se află un depozit cu cantitatea X de energie, de la care robotul se poate alimenta. Robotul se poate deplasa pe cerc numai în sensul acelor de ceas. Robotul poate păstra o cantitate maximă W de energie, iar inițial este alimentat la capacitate maximă. Pentru fiecare pas robotul cheltuiește o unitate de energie.

1) Precizându-se numărul de poziții N, energia inițială a robotului W, poziția P a depozitului și cantitatea X de energie existentă inițial în depozit, se cere să se precizeze numărul de pași pe care îi poate efectua robotul.
2) Precizându-se numărul de poziții N, energia inițială a robotului W și cantitatea X de energie existentă inițial în depozit, se vor determina și afișa numărul maxim de pași pe care îi poate efectua robotul și cea mai mică poziție, convenabil aleasă, unde se poate instala depozitul pentru obținerea numărului maxim de pași.

Pentru orice număr natural N se asociază o cifră din mulţimea {0,1,2,3,4,5}, numită amprentă, astfel: se calculează diferenţa pozitivă a sumelor cifrelor de pe poziţiile pare, respectiv impare; dacă această diferenţă este mai mică decât 10 atunci algoritmul se opreşte, în caz contrar algoritmul se aplică în continuare, repetat, asupra diferenţei pozitive, până când se va obţine o cifră mai mică decât 10, iar dacă cifra este mai mare decât 5, atunci cifrele 6,7,8,9 se vor înlocui respectiv cu 5,4,3,2. De exemplu pentru numărul N = 90 amprenta este 2, iar pentru N = 91909091 amprenta este 1.

1) Se dă un număr natural N şi se cere determinarea amprentei acestuia.
2) Se dau două numere naturale P, Q şi o cifră C din {0,1,2,3,4,5} şi se cere determinarea numărului de valori dintre P şi Q, inclusiv, care au amprenta egală cu C.

Pe un cerc sunt așezate echidistant N puncte, etichetate în sensul acelor de ceas cu 1, 2, 3, …, N.
Se dau M intervale de forma [a, b] și T interogări de forma P Q.

Pentru fiecare interogare [P, Q] să se verifice dacă este adevărat sau fals că intersecția tuturor intervalelor care au puncte comune cu [P, Q] include intervalul [P, Q].

O permutare de ordin K este formată din toate numerele 1, 2, …, K nu neapărat în această ordine.
O secvență de lungime L este formată din L elemente ale șirului aflate pe poziții consecutive. Spunem că o secvență de lungime L este permutare de ordin L dacă ea conține toate numerele 1, 2, …, L, nu neapărat în această ordine.

Se dă un șir de N numere naturale nenule \( {a}_{1}, {a}_{2}, …,{a}_{N} \), ce reprezintă o permutare de ordin N. Să se calculeze numărul secvențelor din șirul a care au proprietatea că sunt permutări.

Pentru orice număr natural x definim operația cmmp prin care adăugăm cifre la stânga lui x, la dreapta lui x sau la ambele capete ale lui x, astfel încât numărul obținut să fie pătrat perfect și cât mai mic posibil.
 
Se dau N numere naturale \( {s}_{1},{s}_{2}…{s}_{N} \).

Să se determine pentru fiecare număr s[k], 1 ≤ k ≤ N, cel mai mic pătrat perfect care se poate obține prin aplicarea operației cmmp.

Dorind să inventeze ceva nou Mate a inventat numerele “ecou”. Un număr natural A se numeşte număr-ecou dacă există un număr natural B cu proprietatea că numărul A se poate obţine prin concatenarea de un număr de ori (cel puţin de două ori) a numărului B. De exemplu numărul 313313 este număr-ecou, iar 31313 nu este număr-ecou.

Mate şi-a propus să afle câte numere-ecou sunt printre numerele naturale care au exact N cifre. Deoarece acest număr poate fi foarte mare, se va afişa doar restul împărţirii rezultatului la 10^9+17.

Se dau N numere naturale \( {a}_{1},{a}_{2}…{a}_{n}\). O pereche (a[j],a[k]) cu 1≤j<k≤N se numește pereche specială dacă are proprietatea că din a[j] și a[k] prin “lipire” se formează un număr X în care cifrele conținute apar de număr par de ori. De exemplu numerele 123 şi 21223 dacă se lipesc produc numărul 12321223 în care 1 apare de 2 ori, 2 apare de 4 ori și 3 apare de 2 ori.

Să se determine numărul perechilor speciale.

Pentru reprezentarea numerelor s-a decis să nu se mai folosească cifra C. Astfel din șirul numerelor naturale se vor elimina toate numerele care conțin cifra C. Notăm noul șir cu S.

1) Să se determine al N-lea număr din șirul S.
2) Se dau Y și Z, două numere naturale din șirul S. Să se determine numărul de numere naturale eliminate dintre Y și Z.

Fie un zid perfect dreptunghiular de înaltime H și lățime W, format din cărămizi de înalțime 1 și lățime variabilă, lipite între ele.

Să se taie acest zid pe verticală astfel încât numărul de cărămizi ce trebuie tăiate să fie minim. În cazul în care există mai multe astfel de locuri unde poate fi tăiat zidul, se dorește ca diferența lățimilor celor două bucăți obținute să fie cât mai mică.

Se dau N puncte din plan prin coordonatele lor.
Se mai dau Q perechi de puncte, diferite de cele date inițial.

Să se verifice, pentru fiecare pereche de puncte (A , B) dintre cele Q, dacă există traseu care pornește din A și ajunge în B, prin deplasări cu pași de lungime 1 spre Nord, Vest, Sud, Est și evitând orice punct dintre cele N date inițial.