• 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 Bal,Campion 2009

2
  • Publicat de Andrei Avădănei
  • în C/C++
  • — 13 nov., 2009 at 7:18 pm

Un grup de fete si baieti participa la balul bobocilor. Ca sa evite aglomeratia de pe ringul de dans, organizatorii au realizat o programare in care fiecarui participant i se aloca o perioada de timp in care se va afla pe ringul de dans.

Cerinta

Scrieti un program care sa determine numarul maxim de perechi, fata-baiat, care se pot forma cu persoanele aflate pe ringul de dans la un moment dat.

Date de intrare

Fisierul de intrare bal.in contine pe prima linie numerele naturale n si m reprezentand numarul de fete si numarul de baieti participanti la bal. Pe urmatoarele n linii se gasesc cate doua numere naturale xi yi, (1<=i<=n) separate printr-un spatiu reprezentand intervalul inchis de timp in care se va afla pe ring fiecare fata. Pe urmatoarele m linii se gasesc cate doua numere naturale xj yj, (1<=j<=m) separate printr-un spatiu reprezentand intervalul inchis de timp in care se va afla pe ring fiecare baiat.

Date de iesire

Fisierul de iesire bal.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul maxim de perechi determinat.

Restrictii

  • 1 <= n <= 100 000
  • 1 <= m <= 100 000
  • 1 <= xi <= yi <= 1 000 000
  • 1 <= xj <= yj <= 1 000 000

Exemple

bal.in bal.out
3 3
11 16
1 8
6 9
4 20
8 17

13 18

2

Solutia mea

O abordare foarte draguta a problemei consta in crearea a doi vectori sugestivi(B – baieti si F – fete) astfel : pentru fiecare xi,yi (intervalul in care un copil sta pe scena : baiat/fata) B[xi]++,B[yi]– respectiv F[xi]++,F[yi]–. Cu ajutorul unei parcurgeri pana la MAX_N vom avea la fiecare moment numarul de baieti si fete de pe scena (initial fiind 0,adaugam sau scadem in functie de B[pasi]/F[pasi].
Inseamna ca MAX(pasi) = MAX(MAX(pasi-1),MIN(B[pasi],F[pasi]));
Descarcati solutia pentru problema Bal de la Campion 2009.

Etichete: .campionalgoritmicabalinformaticaOJIONIProbleme algoritmicăTehnic

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Problema seti,Campion 2009
  • Articolul următor Problema efort, Campion 2009

2 Comentarii

  1. Andrei Misarca spune:
    noiembrie 13, 2009 la 7:59 pm

    Se mai numeste smenul lui Mars ce ai facut aici. Mi s-au parut marfa problemele de la grupa M, spre deosebire de cele de la L care mi s-au parut niste porcarii.

  2. Avadanei Andrei spune:
    noiembrie 13, 2009 la 8:44 pm

    Sincer nu stiam de aceasta denumire. 🙂 Am mai invatat un lucru nou cu ocazia asta! :))


  • 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
  • august 2022
    L Ma Mi J V S D
    1234567
    891011121314
    15161718192021
    22232425262728
    293031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Problema Bal,Campion 2009
  • 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