Clasa a IX-a lecția 23: Difference between revisions
No edit summary |
(No difference)
|
Latest revision as of 14:30, 10 February 2021
Note de curs: prof. Isabela Coman
Sume partiale
Fie N un numar natural și un șir de N numere naturale V[1], V[2], …, V[N]. Pentru M întrebări de forma (i,j), să se calculeze suma termenilor V[i], V[i + 1], …, V[j].
! ATENTIE ! Adunam n numere. De ce tip va fi suma?
#include <stdio.h>
#include <stdlib.h>
long long S[100000];
int main(){
FILE *fin, *fout;
long long n, m, i, j, x;
fin = fopen ( "sume2.in", "r" );
fscanf ( fin, "%lld", &n );
fout = fopen ( "sume2.out", "w" );
for ( i = 1; i <= n; i ++ ){
fscanf ( fin, "%lld", &x );
S[i] = S[i-1] + x;
}
fscanf ( fin, "%lld", &m );
for ( int k = 1; k <= m; k ++ ){
fscanf ( fin, "%lld%lld", &i, &j );
fprintf ( fout, "%lld\n", S[j] - S[i-1] );
}
return 0;
}Se consideră un tablou unidimensional cu n elemente numere întregi, numerotate de la 1 la n, inițial toate nule. Asupra tabloului se fac m operații s d X cu semnificația: toate elementele cu indici cuprinși între s și d își măresc valoare cu X. Să se afișeze tabloul după realizarea celor m operații.
// Folosim smenul lu Mars
#include<stdio.h>
// Declaram vectorul global, pentru a fi initializat cu 0. El are 2 elemente in plus deoarece, pozitia 1 nu o folosim, iar pozitia n + 1 o vom marca ca sfarsit de interval, in caz ca am un interval cu limita egala cu n.
int v[200002];
int main(){
int n, m, i, a, b, x;
scanf("%d%d", &n, &m );
for(i = 1; i <= m; i++ ){
scanf( "%d%d%d", &a, &b, &x);
v[a] += x; // a este prima pozitie unde vom aduna x
v[b+1] -= x; // b+1 este prima pozitie unde nu voi mai aduna x
}
for( i = 1; i <= n; i++ ){ // pt fiec poz v[i] voi calcula o suma a tuturor marcajelor de pana la pozitia v[i]
v[i] += v[i-1];
printf( "%d ", v[i] );
}
return 0;
}Element majoritar
Se dă un vector cu n elemente, numere naturale. Verificați dacă vectorul are un element majoritar. Numim element majoritar o valoare pentru care numărul de apariții în vector este mai mare decât n/2.
#include <stdio.h>
int v[100000];
int main() {
int n, i, cnt, maj;
// citim sirul de valori
scanf( "%d", &n );
for ( i = 0; i < n; i++ )
scanf( "%d", &v[i] );
maj = v[0]; // presupunem ca prima valoare e majoritara
cnt = 1; // pana acum a aparut o data
for ( i = 1; i < n; i++ )
if ( v[i] == maj ) // daca am gasit o val egala cu majoritarul
cnt++; // cresc cnt de elem majoritar
else {
cnt--; // altfel decrementam numarul de elem maj
if ( cnt < 0 ) { // daca am scazut sub zero
maj = v[i]; // schimbam elementul presupus ca majoritar
cnt = 1; // resetam contorul elem majorita
}
}
// verificare candidat la element majoritar
cnt = 0;
for ( i = 0; i < n; i++ ) // numaram de cit ori apare maj in vector
if ( v[i] == maj )
cnt++;
if ( cnt > n / 2 ) // daca maj apare de mai mult de n/2 ori este majoritar
printf( "DA %d\n", maj );
else
printf( "NU\n" );
}Two pointers
Fie N un numar natural și un șir de N numere naturale V[1], V[2], …, V[N] in ordine crescatoare. Sa se puna daca exista 2 elemente din vector a caror suma sa fie egala cu x.
// solutie naiva O(n^2):luam toate perechile de 2 elemente si calculam suma lor
ok = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (A[i] + A[j] == X)
ok = 1; // am gasit o pereche
if (A[i] + A[j] > X)
break; // daca suma a devenit mai mare ca x, intrerup cautarea
}// solutie O(n): vom folosi 2 pozitii in vactor, initial extremitatile sirului (2 pointeri) cu care ne vom apropia de sol corecta
int i = 0; // represents first pointer
int j = N - 1; // represents second pointer
gasit = 0;
while (i < j) {
if ( A[i] + A[j] == X ) // Daca gasim o pereche
gasit = 1;
else if (A[i] + A[j] < X ) // Dc suma e mai mica, ne mutam cu i pe un element mai mare
i++;
else // Dc suma e mai mare, ne mutam cu j pe un element mai mic
j--;
}Algoritmul se bazeaza pe faptul ca sirul este sortat. Pornim cu suma primului si ultimului element. Daca avem o suma mai mica decat cea pe care dorim sa o obtinem, atunci alegem urmatorul element de dupa A[i], daca suma e mai mare atunci alegem un element mai mic decat A[j]. In functie de suma rezultata, vom ajusta pozitiile celor 2 pointeri pas cu pas, pana cand fie gasim o pereche, fie pozitia lui i devine mai mare decat cea a lui j, semn ca am testat toate perechile posibile.
https://tp-iiita.quora.com/The-Two-Pointer-Algorithm
Laborator
Probleme cu sume partiale
SecvK
Se dă un șir cu n numere naturale și un număr k. Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.
SumaInSecv
Se dă un vector format din n elemente, numere naturale nenule, şi un număr natural S. Determinaţi, dacă există o secvenţă de elemente din şir cu suma elementelor egală cu S.
SumeSecv
Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i<j≤n. Să se determine, pentru pereche (i,j), suma elementelor din secvenţa determinată de i şi j.
SumeSecv1
Se dă un șir cu n elemente numere naturale, numerotate de la 1 la n și m perechi de indici i j. Pentru fiecare pereche de indici se calculează suma elementelor din secvență determinată de cei doi indici. Afișați suma maximă obținută.
swap01
Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j]. Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.
produs3
!!!Problema Grea Sume partiale, XOR, baza 2, gauss
Paint
Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment își câştigă existența ca zugrav. Roberto a primit sarcina de a zugrăvi un zid având lungimea n metri şi înălţimea un metru. Pentru aceasta are la dispoziţie m zile. În fiecare zi i, el acoperă cu un singur strat de vopsea o porţiune compactă de înălțime un metru și de lungime l[i] metri, începând de la distanţa d[i] metri faţă de capătul din stânga al zidului. Roberto ştie din experienţă că fiecare porţiune de zid trebuie acoperită cu cel puţin K straturi de vopsea pentru ca stratul final de vopsea să aibă consistenţa dorită. Din nefericire, firea lui de artist nu i-a permis să-şi poată planifica munca în mod optim, astfel că la capătul celor m zile de efort, Roberto a constatat că zidul are porţiuni pe care le-a acoperit de mai mult de k ori şi alte porţiuni pe care le-a acoperit de mai puţin de k ori. Pentru a recupera în proprii săi ochi dar mai ales în ochii şefului de echipă, el trebuie să afle mai întâi suprafaţa totală a tuturor porţiunilor de zid care mai trebuie zugrăvite. Cunoscând lungimea zidului n, numărul de zile m şi porţiunile compacte pe care le zugrăveşte în fiecare zi, determinaţi suprafaţa totală a zidului care mai trebuie zugrăvită.
TV
#include <cstdio>
#define MAXSEC 60*60*24
using namespace std;
int v[MAXSEC];
int main() {
FILE *fin = fopen ( "tv.in", "r" );
FILE *fout = fopen ( "tv.out", "w" );
int cer, n, i, d, h, m, s, start;
fscanf ( fin, "%d%d", &cer, &n );
for ( i = 0; i < n; i++ ) {
fscanf ( fin, "%d %d:%d:%d", &d, &h, &m, &s );
start = h * 60 * 60 + m * 60 + s;
v[start] ++;
v[start + d] --;
}
// Presupunem ca secunda de aur este 0 ( 00:00:00 )
int poz = 0; // secunda de aur
int vmax = v[0]; // nr maxim de posturi care emit publicitate intr-o secunda
int nr_sec; // nr sec fara publicitate
if ( v[0] == 0 )
nr_sec = 1;
else
nr_sec = 0;
for ( i = 1; i < MAXSEC; i++ ) {
v[i] += v[i - 1];
if ( v[i] == 0 )
nr_sec ++;
if ( v[i] > vmax ){
vmax = v[i];
poz = i;
}
}
if ( cer == 2 )
nr_sec = poz;
fprintf ( fout, "%02d:%02d:%02d", nr_sec / 3600, nr_sec % 3600 / 60, nr_sec % 60 );
return 0;
}Flori1
twoop
Se dă un șir de N elemente, numere întregi. Pe acest șir se aplică operații de două tipuri : Tip 1: st dr val – elementele de pe pozițiile din intervalul [st, dr] cresc cu valoarea val Tip 2: poz – să se afișeze valoarea elementului de pe poziția poz . Dându-se șirul de elemente și operațiile, aplicați operațiile pe șir.
Probleme cu element majoritar
- http://varena.ro/problema/proiecte ( element majoritar )
Probleme cu two pointers
Memory006
Se dă un şir de numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2k, unde k este un număr dat.
#1350 produs2
Se consideră un şir cu elemente numere naturale nenule. Să se afle câte secvenţe din şir au produsul mai mic decât un număr dat.
#2405 politic
În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina fiecăruia. Oricare doi deputați ale căror doctrine corespund unor numere consecutive fac parte din același partid. Prin urmare, partidele vor fi alcătuite din deputați ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputați, cu doctrinele 1, 2, 3, 5 şi 6, atunci înseamnă că aceștia sunt grupați în două partide: unul format din 1, 2 și 3 și altul din 5 și 6.) Un guvern trebuie să beneficieze de susținerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputați, atunci un guvern are nevoie de susținerea a cel puțin 4 deputați. Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este urmatoarea: două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeași coaliţie doar dacă din coaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice 1, 2, 4, 5, 7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă din coaliţia respectivă face parte şi partidul format din 4 şi 5. Fiind dat parlamentul din Ţara lui Papură Vodă printr-un şir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţie majoritară. ONI Gimnaziu 2007
#1471 maxdiv
Scrieţi un program care afişează, pentru un şir dat format din n numere naturale numărul de secvenţe maxdiv şi cea mai lungă secvenţă maxdiv.
Tema
Rezolvati problemele de la secvente, ramase nerezolvate, din fisa de laborator Note de curs: prof. Isabela Coman
Sume partiale
Fie N un numar natural și un șir de N numere naturale V[1], V[2], …, V[N]. Pentru M întrebări de forma (i,j), să se calculeze suma termenilor V[i], V[i + 1], …, V[j].
! ATENTIE ! Adunam n numere. De ce tip va fi suma?
#include <stdio.h>
#include <stdlib.h>
long long S[100000];
int main(){
FILE *fin, *fout;
long long n, m, i, j, x;
fin = fopen ( "sume2.in", "r" );
fscanf ( fin, "%lld", &n );
fout = fopen ( "sume2.out", "w" );
for ( i = 1; i <= n; i ++ ){
fscanf ( fin, "%lld", &x );
S[i] = S[i-1] + x;
}
fscanf ( fin, "%lld", &m );
for ( int k = 1; k <= m; k ++ ){
fscanf ( fin, "%lld%lld", &i, &j );
fprintf ( fout, "%lld\n", S[j] - S[i-1] );
}
return 0;
}Se consideră un tablou unidimensional cu n elemente numere întregi, numerotate de la 1 la n, inițial toate nule. Asupra tabloului se fac m operații s d X cu semnificația: toate elementele cu indici cuprinși între s și d își măresc valoare cu X. Să se afișeze tabloul după realizarea celor m operații.
// Folosim smenul lu Mars
#include<stdio.h>
// Declaram vectorul global, pentru a fi initializat cu 0. El are 2 elemente in plus deoarece, pozitia 1 nu o folosim, iar pozitia n + 1 o vom marca ca sfarsit de interval, in caz ca am un interval cu limita egala cu n.
int v[200002];
int main(){
int n, m, i, a, b, x;
scanf("%d%d", &n, &m );
for(i = 1; i <= m; i++ ){
scanf( "%d%d%d", &a, &b, &x);
v[a] += x; // a este prima pozitie unde vom aduna x
v[b+1] -= x; // b+1 este prima pozitie unde nu voi mai aduna x
}
for( i = 1; i <= n; i++ ){ // pt fiec poz v[i] voi calcula o suma a tuturor marcajelor de pana la pozitia v[i]
v[i] += v[i-1];
printf( "%d ", v[i] );
}
return 0;
}Element majoritar
Se dă un vector cu n elemente, numere naturale. Verificați dacă vectorul are un element majoritar. Numim element majoritar o valoare pentru care numărul de apariții în vector este mai mare decât n/2.
#include <stdio.h>
int v[100000];
int main() {
int n, i, cnt, maj;
// citim sirul de valori
scanf( "%d", &n );
for ( i = 0; i < n; i++ )
scanf( "%d", &v[i] );
maj = v[0]; // presupunem ca prima valoare e majoritara
cnt = 1; // pana acum a aparut o data
for ( i = 1; i < n; i++ )
if ( v[i] == maj ) // daca am gasit o val egala cu majoritarul
cnt++; // cresc cnt de elem majoritar
else {
cnt--; // altfel decrementam numarul de elem maj
if ( cnt < 0 ) { // daca am scazut sub zero
maj = v[i]; // schimbam elementul presupus ca majoritar
cnt = 1; // resetam contorul elem majorita
}
}
// verificare candidat la element majoritar
cnt = 0;
for ( i = 0; i < n; i++ ) // numaram de cit ori apare maj in vector
if ( v[i] == maj )
cnt++;
if ( cnt > n / 2 ) // daca maj apare de mai mult de n/2 ori este majoritar
printf( "DA %d\n", maj );
else
printf( "NU\n" );
}Two pointers
Fie N un numar natural și un șir de N numere naturale V[1], V[2], …, V[N] in ordine crescatoare. Sa se puna daca exista 2 elemente din vector a caror suma sa fie egala cu x.
// solutie naiva O(n^2):luam toate perechile de 2 elemente si calculam suma lor
ok = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (A[i] + A[j] == X)
ok = 1; // am gasit o pereche
if (A[i] + A[j] > X)
break; // daca suma a devenit mai mare ca x, intrerup cautarea
}// solutie O(n): vom folosi 2 pozitii in vactor, initial extremitatile sirului (2 pointeri) cu care ne vom apropia de sol corecta
int i = 0; // represents first pointer
int j = N - 1; // represents second pointer
gasit = 0;
while (i < j) {
if ( A[i] + A[j] == X ) // Daca gasim o pereche
gasit = 1;
else if (A[i] + A[j] < X ) // Dc suma e mai mica, ne mutam cu i pe un element mai mare
i++;
else // Dc suma e mai mare, ne mutam cu j pe un element mai mic
j--;
}Algoritmul se bazeaza pe faptul ca sirul este sortat. Pornim cu suma primului si ultimului element. Daca avem o suma mai mica decat cea pe care dorim sa o obtinem, atunci alegem urmatorul element de dupa A[i], daca suma e mai mare atunci alegem un element mai mic decat A[j]. In functie de suma rezultata, vom ajusta pozitiile celor 2 pointeri pas cu pas, pana cand fie gasim o pereche, fie pozitia lui i devine mai mare decat cea a lui j, semn ca am testat toate perechile posibile.
https://tp-iiita.quora.com/The-Two-Pointer-Algorithm
Laborator
Probleme cu sume partiale
SecvK
Se dă un șir cu n numere naturale și un număr k. Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.
SumaInSecv
Se dă un vector format din n elemente, numere naturale nenule, şi un număr natural S. Determinaţi, dacă există o secvenţă de elemente din şir cu suma elementelor egală cu S.
SumeSecv
Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i<j≤n. Să se determine, pentru pereche (i,j), suma elementelor din secvenţa determinată de i şi j.
SumeSecv1
Se dă un șir cu n elemente numere naturale, numerotate de la 1 la n și m perechi de indici i j. Pentru fiecare pereche de indici se calculează suma elementelor din secvență determinată de cei doi indici. Afișați suma maximă obținută.
swap01
Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j]. Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.
produs3
!!!Problema Grea Sume partiale, XOR, baza 2, gauss
Paint
Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment își câştigă existența ca zugrav. Roberto a primit sarcina de a zugrăvi un zid având lungimea n metri şi înălţimea un metru. Pentru aceasta are la dispoziţie m zile. În fiecare zi i, el acoperă cu un singur strat de vopsea o porţiune compactă de înălțime un metru și de lungime l[i] metri, începând de la distanţa d[i] metri faţă de capătul din stânga al zidului. Roberto ştie din experienţă că fiecare porţiune de zid trebuie acoperită cu cel puţin K straturi de vopsea pentru ca stratul final de vopsea să aibă consistenţa dorită. Din nefericire, firea lui de artist nu i-a permis să-şi poată planifica munca în mod optim, astfel că la capătul celor m zile de efort, Roberto a constatat că zidul are porţiuni pe care le-a acoperit de mai mult de k ori şi alte porţiuni pe care le-a acoperit de mai puţin de k ori. Pentru a recupera în proprii săi ochi dar mai ales în ochii şefului de echipă, el trebuie să afle mai întâi suprafaţa totală a tuturor porţiunilor de zid care mai trebuie zugrăvite. Cunoscând lungimea zidului n, numărul de zile m şi porţiunile compacte pe care le zugrăveşte în fiecare zi, determinaţi suprafaţa totală a zidului care mai trebuie zugrăvită.
TV
#include <cstdio>
#define MAXSEC 60*60*24
using namespace std;
int v[MAXSEC];
int main() {
FILE *fin = fopen ( "tv.in", "r" );
FILE *fout = fopen ( "tv.out", "w" );
int cer, n, i, d, h, m, s, start;
fscanf ( fin, "%d%d", &cer, &n );
for ( i = 0; i < n; i++ ) {
fscanf ( fin, "%d %d:%d:%d", &d, &h, &m, &s );
start = h * 60 * 60 + m * 60 + s;
v[start] ++;
v[start + d] --;
}
// Presupunem ca secunda de aur este 0 ( 00:00:00 )
int poz = 0; // secunda de aur
int vmax = v[0]; // nr maxim de posturi care emit publicitate intr-o secunda
int nr_sec; // nr sec fara publicitate
if ( v[0] == 0 )
nr_sec = 1;
else
nr_sec = 0;
for ( i = 1; i < MAXSEC; i++ ) {
v[i] += v[i - 1];
if ( v[i] == 0 )
nr_sec ++;
if ( v[i] > vmax ){
vmax = v[i];
poz = i;
}
}
if ( cer == 2 )
nr_sec = poz;
fprintf ( fout, "%02d:%02d:%02d", nr_sec / 3600, nr_sec % 3600 / 60, nr_sec % 60 );
return 0;
}Flori1
twoop
Se dă un șir de N elemente, numere întregi. Pe acest șir se aplică operații de două tipuri : Tip 1: st dr val – elementele de pe pozițiile din intervalul [st, dr] cresc cu valoarea val Tip 2: poz – să se afișeze valoarea elementului de pe poziția poz . Dându-se șirul de elemente și operațiile, aplicați operațiile pe șir.
Probleme cu element majoritar
- http://varena.ro/problema/proiecte ( element majoritar )
Probleme cu two pointers
Memory006
Se dă un şir de numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2k, unde k este un număr dat.
#1350 produs2
Se consideră un şir cu elemente numere naturale nenule. Să se afle câte secvenţe din şir au produsul mai mic decât un număr dat.
#2405 politic
În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina fiecăruia. Oricare doi deputați ale căror doctrine corespund unor numere consecutive fac parte din același partid. Prin urmare, partidele vor fi alcătuite din deputați ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputați, cu doctrinele 1, 2, 3, 5 şi 6, atunci înseamnă că aceștia sunt grupați în două partide: unul format din 1, 2 și 3 și altul din 5 și 6.) Un guvern trebuie să beneficieze de susținerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputați, atunci un guvern are nevoie de susținerea a cel puțin 4 deputați. Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este urmatoarea: două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeași coaliţie doar dacă din coaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice 1, 2, 4, 5, 7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă din coaliţia respectivă face parte şi partidul format din 4 şi 5. Fiind dat parlamentul din Ţara lui Papură Vodă printr-un şir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţie majoritară. ONI Gimnaziu 2007
#1471 maxdiv
Scrieţi un program care afişează, pentru un şir dat format din n numere naturale numărul de secvenţe maxdiv şi cea mai lungă secvenţă maxdiv.
Tema
Rezolvati problemele de la secvente, ramase nerezolvate, din fisa de laborator
