Clasa a V-a lecția 22 - 20 ian 2015
Tema - rezolvări
Rezolvări aici [1]
Lecţie
Probleme olimpiada pe şcoală - rezolvări
Problema cifre 4
Problema cifre 4 este o problemă de bazele informaticii. Ea necesită doar noţiuni introductive de algoritmi şi programare.
#include <stdio.h>
int main() {
FILE *fin, *fout;
int n, maxcf, max2cf, npp, cf, cf2;
fin = fopen( "cifre4.in", "r" );
fscanf( fin, "%d", &n ); // citire numar n
fclose( fin );
maxcf = n % 10; // initializam cifra maxima cu ultima cifra a numarului
npp = 0; // numarul de cifre patrate perfecte este initial zero
if ( maxcf == 0 || maxcf == 1 || maxcf == 4 || maxcf == 9 )
npp++; // doar cifrele 0, 1, 4 si 9 sint patrate perfecte
max2cf = n % 100; // initializam numarul maxim de 2 cifre cu ultimele 2 cifre
n /= 10; // eliminam ultima cifra
while ( n > 0 ) { // cita vreme mai avem cifre in n
cf = n % 10; // extragem ultima cifra in cf
if ( cf > maxcf ) // o comparam cu maximul
maxcf = cf; // daca este mai mare, o retinem in maxim
if ( cf == 0 || cf == 1 || cf == 4 || cf == 9 ) // cf este patrat perfect?
npp++; // daca da, adunam unu la contorul de patrate perfecte
cf2 = n % 100; // extragem numarul format din ultimele doua cifre
if ( cf2 > max2cf ) // este mai mare decit maximul?
max2cf = cf2; // daca da, il retinem
n/= 10; // eliminam ultima cifra a numarului
}
fout = fopen( "cifre4.out", "w" );
fprintf( fout, "%d\n%d\n%d\n", maxcf, npp, max2cf );
fclose( fout );
return 0;
}
Problema gondola
Problema gondola este o problemă cu secvenţe. Rezolvarea ei nu necesită vectori. Problema se poate rezolva în mai multe feluri. Voi prezenta mai jos o soluţie bazată pe memorarea ultimei înălţimi şi a ultimei diferenţe de înălţime între doi stîlpi consecutivi.
În primul rînd să observăm că toate înălţimile pe care le vom lua în calcul în rezolvare provin din suma a două secvenţe şi anume secvenţa originală de înălţimi plus secvenţa postamentelor, care are o regulă de generare:
stîlpi: h0 h1 h2 h3 h4 h5 ... postamente: 1 2 3 1 2 3 ... înălţimi: h0+1 h1+2 h2+3 h3+1 h4+2 h5+3 ...
Observăm că regula de generare a postamentelor este:
postamentul i: pi = 1 + i % 3
Punctul a
Primul punct este banal, el cere suma înălţimilor.
Punctul b
Şi al doilea punct este relativ simplu. Vom memora ultima înălţime, pentru a putea calcula diferenţa dintre înălţimea curentă şi ultima. Vom avea grijă că diferenţa poate fi în sens crescător sau descrescător.
Punctul c
La punctul c ni se cere să găsim maximul diferenţelor de diferenţe. De acee trebuie să memorăm ultima diferenţă, pe care o vom compara cu diferenţa curentă. La fel, vom avea grijă că această diferenţă poate fi în sens crescător sau descrescător.
Iată o soluţie posibilă:
#include <stdio.h>
int main() {
FILE *fin, *fout;
int n, i, h1, h2, d1, d2, dd, maxd, maxdd;
long long s;
fin = fopen( "gondola.in", "r" );
fscanf( fin, "%d", &n ); // numarul de stilpi
fscanf( fin, "%lld", &s ); // citim prima inaltime direct in suma
s++; // adunam inaltimea postamentului
fscanf( fin, "%d", &h1 ); // citim a doua inaltime
h1 += 2; // adunam postamentul
if ( h1 > s ) // calculam prima diferenta de inaltime
maxd = d1 = h1 - s;
else
maxd = d1 = s - h1;
s += h1; // adunam inaltimea la suma
maxdd = 0; // initial diferenta de diferente este zero
// incepem sa citim stilpii, incepind cu al treilea (i=2)
for ( i = 2; i < n; i++ ) {
fscanf( fin, "%d", &h2 ); // citim inaltimea stilpului
h2 = h2 + 1 + i % 3; // adunam postamentul
s += h2;
if ( h2 > h1 ) // calculam diferenta curenta
d2 = h2 - h1;
else
d2 = h1 - h2;
if ( d2 > maxd ) // actualizam diferenta maxima
maxd = d2;
if ( d2 > d1 ) // calculam diferenta ultimelor doua diferente
dd = d2 - d1;
else
dd = d1 - d2;
if ( dd > maxdd ) // actualizam diferenta de diferente maxima
maxdd = dd;
h1 = h2; // memoram ultima inaltime
d1 = d2; // memoram ultima diferenta
}
fclose( fin );
fout = fopen( "gondola.out", "w" );
fprintf ( fout, "%lld\n%d\n%d\n", s, maxd, maxdd );
fclose( fout );
return 0;
}
Temă
Atenţie: rezolvaţi problemele următoare folosind vectori de frecvenţă! Acesta este scopul temei.
- Cifre comune rezolvată cu vectori de frecvență!
- Cifre 3
- Minnr
- Minnrk
Rezolvări aici [2]