Lista de probleme 94

Filtrare

În planul xOy se găsesc n puncte de coordonate numere naturale, nu neapărat aflate pe poziții distincte. Pentru fiecare punct din plan de coordonate (x, y) trebuie să spuneți câte alte puncte au coordonatele (p, q) cu proprietatea că 0 ≤ p < x și 0 ≤ q ≤ y (atenție, p este strict mai mic decât x, iar q este mai mic sau egal cu y).

Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y].

Se dau n puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale (x, y), unde x și y sunt numere naturale. Spunem că două puncte (x, y) și (i, j) sunt simetrice dacă x = j și y = i. Să se determine numărul perechilor de puncte simetrice.

Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații:

  • 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val;
  • 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori);
  • 3 st dr – se cere să se afișeze lungimea cele mai lungi secvențe de numere prime alcătuită exclusiv din elemente ale șirului care au indicii aflați în intervalul [st, dr](o secvență a unui șir este alcătuită din elemente aflate poziții consecutive).

Dându-se Q operații, să se raspundă în ordine la cele de tip 2 și 3.

Gigel are un șir cu N beculețe, numerotate de la 1 la N, inițial toate stinse. Cu acest șir Gigel face M operații, de două tipuri:

  • 1 i j: toate beculețe numerotate cu valori între i și j își schimbă starea
  • 2 k: se determină starea beculețului numerotat cu k.

Scrieți un program care să determine citește N, M și cele M operații și determină rezultatul fiecărei operații de tipul 2.

Se citesc de la tastură două numere naturale n și m, apoi un șir de n numere naturale. Asupra șirului de numere se pot aplica m operații de două feluri: modificarea unei valori din șir și respectiv determinarea sumei valorilor aflate în șir între două poziții date.

Se dă un string S format doar din litere mici ale alfabetului englez și Q operații de forma:

  • 1 a b len – se va afișa 1 dacă secvențele S[a, a+len-1] și S[b, b+len-1] sunt egale. În caz contrar, se va afișa 0.
  • 2 l r ch – toate caracterele între pozițiile l și r devin ch.

Să se scrie un program care poate efectua aceste operații.

Se dă un arbore binar care conține valori numere naturale. Să se afișeze frunzele acestui arbore.

Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și interogarea unui interval de indici (determinarea celei mai mici valori aflate între cei doi indici, inclusiv).
Afișați răspunsul la fiecare interogare.

Josephus este un matematician înrăit.
Într-o zi acesta se joacă cu primele N numere prime, când se decide să își construiască propiul său șir circular format din aceste numere. Pe prima poziție se va afla primul număr prim, adică 2, iar mai apoi se parcurge circular șirul din K în K, completându-se cu restul de numere prime, până la repartizarea tuturor.