Costel a descoperit intr-o debara servieta cu cifru a tatalui sau. Cifru este compus din patru discuri metalice pe care sunt inscriptionate cifrele de la 0 la 9. Fiecare disc se poate misca individual,de sus in jos si de jos in sus,formandu-se combinatii de cifre.Dataorita comocditatii,combinatia care permite deschiderea servietei este formata din cifre identice 0000,1111,....
Costell isi imagineaza un cifru compus cu N discuri metalice ca cele specificate anterior.
Determinati numarul minim de mutari necesare pentru ca numarul obtinut pe cifru sa fie format numai din cifre identice.


Problema s-a dat anul trecut la faza judeteana a olimpiadei de informatica ,clasa a 6-a;si a venit feciorul meu sa ma intrebe de ce se compara numarul de miscari cu 10( n+1).(Nu stiu de unde a aparut unul acela in plus.)

N sunt este numarul de discuri dar n cine este?

Banuiesc ca este acelasi numar de discuri; alt n nu mai apare in rezolvare...

.

eu solutia asta am vazut-o:
// autor Alin Burtza
#include <fstream>
#define Fin "cifru.in"
#define Fou "cifru.out"

using namespace std;

int main()
{
ifstream IN(Fin);
ofstream OUT(Fou);
int N; //numarul discurilor
int Apar[10]; //Apar = 1 daca culoarea i apare pe cel putin un disc
int MAX; //cifra maxima
int NrMin; //numarul minim de mutari
int Cif; //cifra obtinuta in numarul minim de mutari
int Cate; //numarul posibilitatilor
int i,j, Nr, x;
//initializari
for(i=0;i<=9;i++) Apar = 0;

//citesc datele de intrare si
//determin cifrele care apar initial si cifra maxima
IN>>N; MAX = 0; Cif = -1; Cate = 0;
for(i=1;i<=N;i++)
{
IN>>x;
Apar[x]++;
if(MAX < x) MAX = x;
}
//calculez numarul de mutari pentru fiecare cifra care apare
NrMin = 10 * N + 1;
for(i=0;i<=9;i++)
{
Nr = 0;
for(j=0;j<=9;j++)
if(Apar[j] && j!=i)
Nr += abs(j-i) <= 10 - abs(j-i) ? Apar[j]*abs(j-i) : Apar[j]*(10 - abs(j-i));
if(Nr<NrMin) NrMin = Nr, Cif = i, Cate = 1;
else if(Nr==NrMin) Cate++;
}
OUT<<MAX<<'\n'<<NrMin<<'\n'<<Cif<<'\n'<<Cate<<'\n';

IN.close();
OUT.close();
return 0;
}

Asa cum sunt scrise literele mai sus, nu se intelege nimic.
In orice caz, oricum nu se intelege prea bine enuntul dat.

Iata mai instai "solutia"

[Citat] eu solutia asta am vazut-o:

Sper sa mi se compileze.
Fara comentariu in plus, cele de mai sus nu se inteleg decat in sens reubsist.

Pe pagina
http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1417
am vazut in sfarsit un exemplu si am inteles ce vrea problema de la un elev de clasa a 6-a. Este bine ca matematica este in sfarsit surclasata in acest mod de o alta disciplina in ceea ce priveste cererea unor lucruri supranaturale de la elevi.

Solutia de mai sus o explic pe baza exemplului din link.
Ei bine, sa ne imaginam ca in fisierul de intrare care se afla pe placa sub numele cifru.in si in cod dus de aici mai intai in Fin, apoi in acel IN din

ifstream IN(Fin);

contine urmatoarele date, cinci linii,

4
7
3
9
0

Acest lucru se traduce foarte simplu pentru un elev de clasa a 6-a astfel.
Costel chiar are cifrul de 4 cifre care in momentul in care se uita la el indica numarul
7390,
pe care autorul programului il introduce gata spart in cifre.
De ce nu? Data viitoare elevul poate ca va tipari direct 7390, dar aici ne facem viata cat de cat usoara.

Si ce vrea problema de la noi?

Cel mai "bine" se intelege problema asa.
Avem spatiul metric care este produsul cartezian a patru copii ale multimii cifrelor

I = { 0,1,2,3,4,5,6,7,8,9 } ,

multime pe care introducem metrica urmatoare (este distanta asociata grafului cu numerele de mai sus plasate ciclic in aceeasi ordine pe cerc):

Distanta de la cifra i la cifra j este, in cazul in care i < j
minimul dintre

( j - i ) si

(10+i) - j
De exemplu, distanta de la 2 la 4 este (4-2), distanta de la 9 la 0 este cea de la 9 la (10+0) ...

Elevul de a sasea intelege ca a merge in sus si in jos inseamna a scrie formulele corespunzatoare pentru metrica.

Ce face programul?
Citeste deci 4, vor veni patru cifre, apoi citeste cifrele pe rand, anume 7,3,9,0.

In acest moment, vectorul Apar, numit asa pentru ca orice om intelege ca el contine 10 intrari corespounzatoare celor zece cifre, pe fiecare intrare avem
0, 1, 2, 3 sau 4,
exact numarul de aparente ale cifrei cu pricina. Pentru 7390 (si 9037) avem deci

1,0,0,1,0,0,0,1,0,1 care corespunde pozitiilor:
0,1,2,3,4,5,6,7,8,9

Un lucru nu tocami placut este faptul ca se calculeaza maximul in timpul citirii, astfel de lucruri sunt un cosmar pentru un programator, care vrea separare a tot ce se poate separa in program, anume input, logica, calcul, output, ... in fine, tiparim mai putin. (Industrial inseamna acest lucru asa: cel ce trebuie sa schimbe programul putin dupa cateva luni va folosii imprecatiile specifice.)

In momentul citirii, acel numar maxima care apare va fi deci pe rand:
MAX = 0, intializare bine ascunsa si putin comentata
MAX = 7 dupa ce l-am citit pe 7
MAX = 7 dupa ce l-am citit pe 3
MAX = 9 dupa ce l-am citit pe 9
MAX = 9 dupa ce l-am citit pe 0

Candva la sfarsit il vom printa si pe MAX. In fine, bine ascuns.

Acum ne intrebam pe rand, pentru fiecare element 0000, 1111, ... , 9999 cat de departe se afla numarul dat, 7390.

Aceasta departare este acel numar minim de miscari in sus sau jos cerut.
Este cumva ciudat pentru mine ca putem sa castigam cu mai multe combinatii, dar dupa ce am vazut solutia m-am convins ca este asa. De exemplu, combinatia initiala 1100 castiga fie cu 1111 dupa doua mutari de la 0 la 1 pe ultimele doua locuri, nu stiu daca in sus sau jos, in orice caz in directia care trebuie, fie cu 0000, caz in care facem miscarile pe primele doua pozitii.

In program lasam un i sa se plimbe de la 0 la 9,
pentru fiecare astfel de i ne gandim la combinatia

iiii

si vedem de cate mutari avem nevoie.
Daca de la un pas la altul dam de un numar mai mic de mutari, atunci inlocuim in acel

NrMin

cu noul numar, desigur ca trebuie sa initializam cumva acest NrMin, autorul s-a gandit la 10 N + 1 ca o granita superioara buna si usor de calculat, mai mult oricum niciodata.

(O problema interesant ar fi sa se gaseasca chiar aceasta granita maxima...)

De in program ne dam NrMin = 41.

Ne uitam la 7390 si la 0000 mai intai. Este nevoie de 3 + 3 + 1 + 0 mutari.
Il micsoram pe 41 la 7 .
Tinem minte cifra 0 in "cea mai mica cifra". (Am initializat-o cumva.)
Tinem minte ca pe 7 l-am obtinut o data.

Ne uitam apoi la 7390 si la 1111. Este nevoie de 4 + 2 + 2 + 1 mutari.
Il lasam pe NrMin la 7 .

si asa mai departe.
Sper ca acum totul e clar.
(In link avem si acel output...)

Multumim frumos!Cred ca a inteles acum,pentru ca nu a mai intrebat nimic,si de obicei e foarte pisalog. Daca nu va este cu suparare,poate mai cerem ajutorul din cand in cand.

P.S. Solutia pe care am postat-o am luat-o cu copy+ paste; eu nu sunt in stare sa scriu/citesc/descifrez nicio linie de cod

[Citat] eu nu sunt in stare sa scriu/citesc/descifrez nicio linie de cod

Efortul este minim pentru a intelege cele de mai sus,
aici este prilejul unic pentru a tine (inca) pasul cu ce fac "baietii" la scoala.
Dupa parerea mea, C++ nu este limbajul didactic bun de intelegere a programarii.
Motivul este acel "zgomot alb" dintre liniile care conteaza. Eu prefer python, caz in care nu este nevoie de compilare... In limbaj uman:

In C++ se scrie ceva intr-un editor, cele scrise se compileaza mai intai (cutie neagra) iar cele compilate se ruleaza. De obicei pustii vin cu "echipamentul de dezvoltat cod gata fur(niz)at" si nu isi fac nici un fel de ganduri despre dependenta creata. Ar fi interesant de stiut in ce cadru dezvolta codul copiii astia.
In Python avem ceea ce este mai usor (pentru inceput), anume avem un "mancator de cod", tiparim o instructiune in interpreterul python si si vedem ce se intampla dupa ea. Se invata doar mai repede, altfel de la un punct conteaza doar gandirea logica, puterea de a separa calculele si a le face in mod optim, apoi structurarea codului.

Iata cum se calculeaza de exemplu in python distanta dinte
7390 si 4444 sa zicem. O sa dau numerele deja sparte in bucati, ca sa ne scapam de ceva birocratic in plus.


def distanta( cifra1, cifra2 ):
"""se calculeaza distanta dintre cele doua cifre
vazute puse pe graful ciclic cu ciclul 0,1,2,3,4,5,6,7,8,9,0,...
"""
# prefer sa ordonez mai bine
d1 = min( [ cifra1, cifra2 ] )
d2 = max( [ cifra1, cifra2 ] )
return min( [ d2-d1, (10+d1) - d2 ] )


In python putem cere direct duppa ce am tiparit cele de mai sus:

print distanta( 2,4 )
print distanta( 4,2 )
print distanta( 2,9 )
print distanta( 2,8 )


In mancatorul de text lucrurile acestea arata asa:

Asa se invata cel mai usor programarea. (Cu un "mancator de linii" = interpreter, nu cu un compiler la mijloc.)

Acum referitor la problema de mai sus.
Putem sa incercam impreuna si sa reproducem *toti* pasii.
In acelasi timp in python si in C++ .

Daca sunt intrebari cu incredere.

Din punct de vedere matematic, punctul nevralgic al programului este aici:

Si cele de mai sus se explica asa:
Cel mai bine pe caz particular.
N=4,
combinatia pe care o vedem (tot "cifru" pentru mine) este 7, 3, 9, 0.

Initializam NrMin cu 41. Imediat va fi mai mic.
Plecam pe rand cu un i de la 0 la 9.
Deci il facem pe rand pe i egal cu 0,1,2,..,9 .
Ceea ce in matematica este inductia (finita), in informatica este un ciclu.
Nu se poate intelege un lucru fara altul. (Dar se poate folosi, toata industria informatica se bazeaza pe faptul ca nu trebuie sa intelegem, ci trebuie sa scriem si sa testam bine. Cei ce inteleg au totusi nervii nesolicitati.)

Este afacerea cu

for(i=0;i<=9;i++)
{
...
}
Daca intre acolade avem *o singura linie* putem omite acoladele,
altfel nu.
Este un stil urat sa ingramadim cat se poate de multe lucruri pe o linie,
daca putem sa le scriem unul sub altul.

Suntem acum in interiorul acestui ciclu.
Ca sa mai variem, sa zicem ca suntem cu i = 6.

Instantaneu intram intr-un ciclu dupa un j de la 0 la 9.
Notatia este inselatoare.
Daca i este cifra care se refera la combinatia

iiii

cifra j se adreseaza tot unei cifre, insa intr-o alta structura.
Anume j este *indexul* din vectorul de aparitii

Apar

care la noi este
1,0,0,1,0,0,0,1,0,1 - unde se corespund pozitiile
0,1,2,3,4,5,6,7,8,9 .

Daca am fi plecat cu 3,6,1,3 in loc de 7,3,9,0, atunci am fi avut:
0,1,0,2,0,0,1,0,0,0 - pe pozitiile
0,1,2,3,4,5,6,7,8,9 .

Acum calculam pe rand distanta de la 7, apoi 3, apoi 9, apoi 0 la acest i=6.
Anume
pentru j=0, si inmultim cu Apar[0] = 1,
pentru j=3, si inmultim cu Apar[3] = 1,
pentru j=7, si inmultim cu Apar[7] = 1,
pentru j=9, si inmultim cu Apar[9] = 1,
in aceasta ordine

si ca sa nu calculam de pomana (optimizare in cod),
am pus conditia

if(Apar[j] && j!=i)

care se adreseaza numai liniei care vine, nu am pus acolade, dar am pus pe linia respectiva cat de mult am putut. (Chestie de gust / stil.)

Ei bine, propun sa rumegam bine impreuna liniile:


if(Apar[j] && j!=i)
Nr += abs(j-i) <= 10 - abs(j-i) ? Apar[j]*abs(j-i) : Apar[j]*(10 - abs(j-i));


stiind ca:

- instructiunea a += b inseamna a = a+b, adica uita-te la a+b, calculeaza asta vazand ce se afla in "sertarele" (registrii) a si b, rezultatul ia-l si baga-l in sertarul a. Pe scurt: a += b inseamna aduna ce e in sertarul a cu valoarea din b.

- instructiunea: <conditie> ? valoareCandConditiaEsteAdevarata : valoareCandConditiaEsteFalsa inseamna ca intai se evalueaza conditia <conditie>, dam de True sau False in C++, depinzand de acest lucru luam valoarea ...

Aici se intelege foarte bine diferenta dintre olimpiada de matematica si cea de informatica. In matematica nu conteaza "drumul scurt" (prea mult), dar argumentarea "drumului" este esentiala. Nici un fel de caz nu trebuie lasat la o parte. In informatica "scriem formula", suntem pe partea pragmatica si lasam apoi formula sa fie testata pe cazurile alese de cei ce testeaza.

(La noi putem sa le programam pe toate... Sunt putine.)
Conteaza ca *rezultatul sa fie bun* .
Probabil ca formula pe care o scriem nu e buna pentru N = 172, dar asta nu se testeaza.

Nu spun ca este bine sau rau, este "alta stiinta", dar intersectia este de asa natura incat

- un matematician care stie sa programeze are un atu puternic in cercetare (in principiu tot ce se poate face cu hartie si creion e daja facut).
In

- un informatician care stie matematica (rigoare, logica, izolartea formulei care trebuie in forma buna) are un atu puternic in gasit loc de munca si facut munca mai putin bruta din informatica. Este o munca bine platita de obicei. (Cei ce vor deja toata viata sa schimbe culoarea unui camp dintr-o masca - sau asa ceva - nu trebuie neaparat sa invete si matematica. Dar vor trebui sa invete o droaie de programe de schimbat culoarea in viata lor de informaticieni. Si cei tineri o vor schimba mereu mai repede. Insa cei ce vor sa programeze jocuri pe calculator e bine sa inteleaga fizica, miscari liniare dupa o ecuatie diferentiala cu derivate partiale implementata folosind metode de aproximare bune, trebuie sa inteleaga miscarile in spatiu, in principiu grupul O(3), si sa foloseasca asa ceva cum trebuie. Inca trebuie stapanite bibliotecile standard si cele ale firmei proprietarea in care are omul sansa sa lucreze.)

Bun, ce facem mai departe?


P.S. A trebuit sa trec la font tiny (mic de tot), altfel nu mi se compileaza pe pagina, latimea este depasita. Rog a se folosi lupa (rotita de la mouse trebuie miscata in timp ce se apasa Control).