Lista de probleme 23

Filtrare

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 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.

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 ș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.

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 celui mai mare divizor comun pentru valorile aflate între cei doi indici, inclusiv).

#2534 Bogdan

Se dă un șir de n elemente, numere naturale. Problema constă în două operații:

1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val.
2 i j : Stabiliți dacă secvența [i,j], din șirul curent, este ordonată crescător.

Se dau numerele N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact un interval din descompunere). De exemplu, pentru perechea 5,10, o descompunere în intervale este [5,5], [6,8],[9,10]. Dorim să realizăm o descompunere în intervale a tuturor celor M perechi de numere date, astfel încât să se îndeplinească condițiile următoare (notăm L = 1 + [log2N]).
  • fiecare pereche să aibă în descompunere maxim 2*L intervale.
  • numărul total de intervale distincte cu mai mult de un element care apar în descompuneri să nu depășească valoarea N.

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 determinarea, urmată de ștergerea, elementului minim. Dacă valoarea minimă apare de mai multe ori în șir, se elimină prima sa apariție. Se consideră că elementele aflate în dreapta celui eliminat se deplasează o poziție la stânga (acoperă golul lăsat).

Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui interval (schimbarea valorii tuturor elementelor aflate între două poziții date) și interogarea unui interval (determinarea celei mai mici valori aflate între două poziții date).