• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Problema Gard

14
  • Publicat de Coss
  • în Probleme algoritmică
  • — 12 aug., 2009 at 8:32 pm

Am 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 ! 😉

Etichete: divizibilincepator programareOJI GimnaziuOlimpiada InformaticaONIProblema GardProbleme algoritmicăprogram

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior Algoritmul Rabin-Karp pentru potrivirea sirurilor
  • Articolul următor I’m tired of using technology

14 Comentarii

  1. Andrei Misarca spune:
    august 13, 2009 la 11:46 am

    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 ).

  2. miculprogramator spune:
    august 13, 2009 la 11:48 am

    O sa ma gandesc la asta… Deci sunt M copii si vopsesc cate 2 din q in q si p in p ? 🙂

  3. Avadanei Andrei spune:
    august 13, 2009 la 11:52 am

    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 ?

  4. Andrei Misarca spune:
    august 13, 2009 la 11:54 am

    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)

  5. miculprogramator spune:
    august 13, 2009 la 11:54 am

    Pricepusi acum ! 😀

  6. Avadanei Andrei spune:
    august 13, 2009 la 12:01 pm

    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?

  7. Andrei Misarca spune:
    august 13, 2009 la 12:09 pm

    M-am exprimat eu putin gresit. Complexitatea ceruta este O(N + M),pentru ca vrand-nevrand trebuie sa si citesti numerele alea.

  8. Andrei Misarca spune:
    august 13, 2009 la 12:15 pm

    L.E. : Complexitatea poate ajunge in cazul O(NlogN + M). Scuze de greseala 😀

  9. Avadanei Andrei spune:
    august 13, 2009 la 12:28 pm

    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? 😀

  10. Andrei Misarca spune:
    august 13, 2009 la 12:45 pm

    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).

  11. plugaru spune:
    februarie 17, 2012 la 2:56 pm

    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.

  12. Bogdan Condurache spune:
    septembrie 5, 2012 la 3:43 pm

    Aceasta soluție este, după parerea mea, una mult mai eficientă.

    http://pastebin.com/wcFpdeUY

  13. posogan catalin spune:
    februarie 16, 2013 la 2:42 pm

    nu scrieti problema si in pascal

  14. posogan catalin spune:
    februarie 16, 2013 la 2:43 pm

    ca nu reusesc nici cum sa imi dea bine


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • februarie 2021
    L Ma Mi J V S D
    1234567
    891011121314
    15161718192021
    22232425262728
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Probleme algoritmică
  • Problema Gard
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons