Cerința
Cifrele de la 1 la K se scriu într-un şir, iar secvenţa obţinută se repetă la nesfârşit. De exemplu, pentru K=9 se obţine şirul: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 …. Asupra unui asemenea şir se aplică succesiv operaţia de rostogolire de lungime P, ce presupune ca blocul format cu cifrele de pe primele P poziţii să se rotească cu 1800 şi să se scrie deasupra următoarei secvenţe de lungime P. În cazul exemplului anterior, pentru P=3, vom obţine după 4 operaţii de rostogolire de lungime 3:
Pas 1:
3 2 1
4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…
Pas 2:
6 5 4
1 2 3
7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…
Pas 3:
9 8 7
3 2 1
4 5 6
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…
Pas 4:
3 2 1
6 5 4
1 2 3
7 8 9
4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…
Astfel pe primele P poziţii se formează un bloc având la bază P cifre şi înălţimea N+1, unde N este numărul de rostogoliri de lungime P.
Pentru K, P şi N date se cer următoarele:
a) Suma elementelor blocului după N rostogoliri de lungime P.
b) Suma maximă a elementelor de pe o coloană a blocului după N rostogoliri de lungime P.
c) Dacă liniile blocului le privim ca pe nişte numere cu P cifre, să se afle cel mai mic dintre aceste numere ale blocului obţinut după N rostogoliri de lungime P.
Date de intrare
Fişierul de intrare bloc.in conţine pe prima linie numerele K, P şi N ce reprezintă cifra maximă din şirul iniţial, lungimea secvenţei care se rostogoleşte, respectiv numărul de rostogoliri.
Date de ieșire
Fişierul de ieşire bloc.out va conţine pe prima linie suma elementelor blocului după N rostogoliri, pe a doua linie suma maximă a elementelor unei coloane a blocului după N rostogoliri, iar pe a treia linie numărul minim format din cifrele unei linii a blocului după N rostogoliri.
Restricții și precizări
1 ≤ K ≤ 91 ≤ P ≤ 1001 ≤ N ≤ 1.000.000- Prima cerinţă se notează cu
40p, a doua cu40p, iar a treia cu20p
Exemplu
bloc.in
9 3 4
bloc.out
66 23 123
Explicație
Datele corespund exemplului de mai sus. La pasul 4 suma elementelor blocului este 66, coloana a treia a blocului are suma 1+4+3+9+6=23 care este maximă, iar cifrele de pe linia a treia a blocului formează numărul minim 123.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema bloc:
//sol. Bunget Mihai
#include <fstream>
using namespace std;
ifstream f("bloc.in");
ofstream g("bloc.out");
long long k,p,n,nrcif,rest,grupe,suma,d,b,r,mc,s,m,c,a[101],u;
long long maxim,i,dir,inv,j,gr,t,sum[101],nr[101],nr1[101];
int main()
{
f >> k >> p >> n ;
//cerinta a)
nrcif = (n+1)*p ;
rest = nrcif % k ;
grupe = nrcif / k ;
suma = grupe * k * (k+1) / 2 + rest * (rest+1) / 2 ;
g << suma << "\n" ;
// cerinta b)
d = k ;
b = p ;
r = d % b ;
while ( r!=0 )
{
d = b ;
b = r ;
r = d % b ;
}
mc = (k*p)/b ;
s = mc / p ;
gr = ( n+1 ) / s ;
rest = ( n+1 ) % s ;
for ( i=1 ; i<=s ; i++ )
{
if ((s-i)%2==0)
for ( j=1 ; j<=p ; j++ ) if ( (p*(i-1)+j)%k==0 ) a[j] += k ;
else a[j] += (p*(i-1)+j)%k ;
else
for ( j=1 ; j<=p ; j++ ) if ( (p*(i-1)+j)%k==0 ) a[p+1-j] += k ;
else a[p+1-j] += (p*(i-1)+j)%k ;
}
if ((gr*s+rest)%2==0)
if (s%2==0) {dir=gr ; inv=0; }
else if (gr%2==0) {dir=gr/2 ; inv=gr/2; }
else { dir=gr/2 ; inv=(gr+1)/2; }
else if (s%2==0){ dir=0 ; inv=gr; }
else if (gr%2==0) {dir=gr/2 ; inv=gr/2; }
else {dir=(gr+1)/2 ; inv=gr/2; }
for (j=1 ; j<=p ; j++ ) sum[j]+=dir*a[j]+inv*a[p+1-j] ;
for ( i=1 ; i<=rest ; i++ )
{
if ((rest-i)%2==0)
for ( j=1 ; j<=p ; j++ ) { if ( (p*(i-1)+j)%k==0 ) sum[j] += k ;
else sum[j] += (p*(i-1)+j)%k ;
}
else
for ( j=1 ; j<=p ; j++ ) { if ( (p*(i-1)+j)%k==0 ) sum[p+1-j] += k ;
else sum[p+1-j] += (p*(i-1)+j)%k ;
}
}
maxim=0 ;
for ( i=1 ; i<=p ; i++ )
if ( sum[i]>maxim ) maxim = sum[i] ;
g << maxim << "\n";
//c
if ( n<s)
{
if ( n%2==0)
for ( i=1 ; i<=p ; i++ )
if(i%k==0) nr[i]=k ;
else nr[i]=i%k ;
else
for ( i=1 ; i<=p ; i++ )
if(i%k==0) nr[p+1-i]=k ;
else nr[p+1-i]=i%k ;
for ( i=2 ; i<=n ; i++ )
{
if ((n-i+1)%2==0)
{
for ( j=1 ; j<=p ; j++ )
if((p*(i-1)+j)%k==0) nr1[j]=k ;
else nr1[j]=(p*(i-1)+j)%k ;
u=1;
while((nr[u]==nr1[u])and(u<p))u++ ;
if (nr[u]>nr1[u])
for ( j=1 ; j<=p ; j++ ) nr[j]=nr1[j] ;
}
else
{
for ( j=1 ; j<=p ; j++ )
if((p*(i-1)+j)%k==0) nr1[p+1-j]=k ;
else nr1[p+1-j]=(p*(i-1)+j)%k ;
u=1;
while((nr[u]==nr1[u])and(u<p))u++ ;
if (nr[u]>nr1[u])
for ( j=1 ; j<=p ; j++ ) nr[j]=nr1[j] ;
}
}
}
else
{
if ((n%2==0)or((n-s)%2==0))
for ( i=1 ; i<=p ; i++ )
if(i%k==0) nr[i]=k ;
else nr[i]=i%k ;
else
for ( i=1 ; i<=p ; i++ )
if(i%k==0) nr[p+1-i]=k ;
else nr[p+1-i]=i%k ;
for ( i=2 ; i<=s ; i++ )
{
if (((n-i+1)%2==0)or((n-i+1>=s)and((n-i+1-s)%2==0)))
{
for ( j=1 ; j<=p ; j++ )
if((p*(i-1)+j)%k==0) nr1[j]=k ;
else nr1[j]=(p*(i-1)+j)%k ;
u=1;
while((nr[u]==nr1[u])and(u<p))u++ ;
if (nr[u]>nr1[u])
for ( j=1 ; j<=p ; j++ ) nr[j]=nr1[j] ;
}
if (((n-i+1)%2==1)or((n-i+1>=s)and((n-i+1-s)%2==1)))
{
for ( j=1 ; j<=p ; j++ )
if((p*(i-1)+j)%k==0) nr1[p+1-j]=k ;
else nr1[p+1-j]=(p*(i-1)+j)%k ;
u=1;
while((nr[u]==nr1[u])and(u<p))u++ ;
if (nr[u]>nr1[u])
for ( j=1 ; j<=p ; j++ ) nr[j]=nr1[j] ;
}
}
}
for ( j=1 ; j<=p ; j++ ) g << nr[j] ;
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1968 bloc
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1968 bloc de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!