Problema Gard
14Am dat zilele trecute peste o problema simpluta si destul de draguta. M-am gandit sa o pun si pe blog, este destinata incepatorilor si nu necesita foarte multe cunostinte de programare … Enjoy ! 😀
Doi copii vopsesc n gard alcatuit din n scanduri (numerotate de la 1 la n, n<=10000) astfel: primul ia o cutie de vopsea rosie cu care vopsesre scandurile cu numarul p, 2p, 3p etc. Al doilea procedeaza la fel, incepe din acelasi capat al gardului, dar ia o cutie de vopsea albastra si vopseste din q in q scanduri. Astfel, cand vor termina de vopsit, gardul va avea multe scanduri nevopsite, unele scanduri vopsite in rosu, altele in albastru, iar altele in violet (scandurile care au fost vopsite si cu rosu si cu albastru).
Cunoscand numerele n, p si q, scrieti un program care sa afiseze:
- cate scanduri raman nevopsite ;
- cate scanduri sunt vopsite in rosu ;
- cate scanduri sunt vopsite in albastru ;
- cate scanduri sunt vopsite in violet .
Vom nota cu rosu numarul scandurilor vospite in rosu, cu albastru numarul celor albastre si cu v numarul celor violete. Cu nev numarul scandurilor nevopsite. Astfel, pentru n=25, p=4, q=6 vom avea:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Culorile spun deja totul. Vom obtine rezultatele:
rosu=4
albastru=2
v=2
nev=15
Cum ajungem la aceasta rezolvare ? Pentru a numara scandurile rosii vom verifica daca numarul „curent” este divizibil cu p, pentru a vefifica daca o scandura este albastra vom verifica daca numarul este divizibil cu q. Daca numarul „curent” este sivizibil si cu p si cu q, scandura va fi violet si vom incrementa valoarea lui v . In final, vom scadea atat din rosu cat si din albastru numarul scandurilor violet.
Numarul scandurilor nevopsite va fi egal cu n- (rosu+albastru) .
Programul este acesta:
#include <iostream.h>
#include <conio.h>
int n=25,i,v=0,albastru=0,rosu=0,nev=0,p=4,q=6;
int main()
{
for (i=1;i<=n;i++)
{
if (i%p==0) rosu++; Â
if (i%q==0) albastru++;
if ( (i%p==0) && (i%q==0) ) v++;
}
nev=n-rosu-albastru;
rosu-=v;
albastru-=v;
cout<<"Numar de scanduri nevopsite: "<<nev<<endl;
cout<<"Numar de scanduri rosii: "<<rosu<<endl;
cout<<"Numar de scanduri albastre: "<<albastru<<endl;
cout<<"Numar de scanduri violet: "<<v<<endl;
getch();
return 0;
}
Numerele n, p si q sunt deja date, pentru a le schimba valorile trebuie doar sa modificati valorile atribuite la declarare.
Problema a fost propusa la Olimpiada Judeteana de Informatica, la gimnaziu. Mie m-i s-a parut tocmai buna pentru incepatori. So, keep programming, it’s cool ! 😉
Problema se mai poate „transforma” putin si se obtine una si mai frumoasa. Nu sunt 2 copii, ci M copii. La fel ca in cazul de mai sus, rezolvarea trebuie sa fie liniara ( O(N), mai precis ).
O sa ma gandesc la asta… Deci sunt M copii si vopsesc cate 2 din q in q si p in p ? 🙂
Din ce am inteles de la el ar fi din a in a,din b in b,din c in c […] din n in n nu ?
Da, adica copii astia vopsesc din X1 in X1, din X2 in X2, din X3 in X3,… din Xm in Xm. Mai precis sunt M valori, nu numa 2 cum erau mai sus (p si q)
Pricepusi acum ! 😀
Rezolvarea cred ca se face defapt in O(m), putem calcula in O(1) cati vom avea din x1 in x1,din x2 in x2…din xm in xm
Practic [LimitMAX/xi] ne va spune cate numere sunt de aceeasi culoare.
Dar nu stiu daca poti face in O(1) toate posibilitatile de a combina cele m numere pentru a vedea daca sunt 2 cate 2 divizibile la un numar i?
M-am exprimat eu putin gresit. Complexitatea ceruta este O(N + M),pentru ca vrand-nevrand trebuie sa si citesti numerele alea.
L.E. : Complexitatea poate ajunge in cazul O(NlogN + M). Scuze de greseala 😀
Eu nu inteleg ce legatura are N aici , practic tot ce va conta va fi acel M.
In O(M) calculam numarul de numere colorate cu culoarea i ale celor M culori.
Ce mai avem de calculat? Combinatiile? Dar cum se formuleaza cerinta? Oricare combinatii 2 cate 2?Asta ar insemna inca 2^M-1 posibilitati. 😕
Explici la ce te`ai gandit? 😀
Ok, hai ca zic solutia mea. Ideea ar fi sa faci cam ca la ciur. Adica iei fiecare numar Xi si sa mergi din Xi in Xi si adaugi cate un unu valorii pe unde ai fost(va trebui tinut si un sir de N elemente in care sa tin minte de cate ori am fost prin fiecare valoare). Solutia mi se pare una chiar foarte simpla, cea cu combintatiile fiind chiar anevoioasa. Acum, de unde N logN. Stim ca X1, X2, …, Xm <= N (altfel nici nu are sens). In cazul in care se repeta o valoare in sirul X, atunci nu are rost sa ma plimb cu ea de 2 ori, ma plimb o singura data si incrementez cu 2.
Asadar, numarul total de pasi este N/X1 + N/X2 + N/X3+ … + N/Xm <= N + N/2 + N/3 + N/4 + … + N/N.
Insa sirul 1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/N – ln N este convergent (parca asa era), prin urmare complexitatea finala este O(N lnN + M).
Sunt un incepator, in clasa a 5-a, ma poate ajuta si pe mine cineva, referitor la problema de mai sus….nu stiu cum sa aflu scandurile vopsite in mov. Doar ca programul pe care-l invat eu este Pascalul.
Aceasta soluție este, după parerea mea, una mult mai eficientă.
http://pastebin.com/wcFpdeUY
nu scrieti problema si in pascal
ca nu reusesc nici cum sa imi dea bine