• 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

[ONI][IX] Bere

0
  • Publicat de Andrei Avădănei
  • în Probleme algoritmică
  • — 17 iul., 2009 at 4:31 pm

Am uitat omis cateva zile aceasta sectiune pentru ca sunt putin mai ocupat.De acum revin cu 2 probleme de anul trecut de la ONI ce mi`au placut si sunt relativ simple 🙂 .

N prieteni, numerotati de la 1 la N, beau bere fara alcool la o masa rotunda. Pentru fiecare prieten i se cunoaste Ci – costul berii lui preferate. Din cand in cand, cate un prieten, fie el k, cumpara cate o bere pentru o secventa de prieteni aflati pe pozitii consecutive la masa, incepand cu el, in sensul acelor de ceasornic. El este dispus sa cheltuiasca x bani si doreste sa faca cinste la un numar maxim posibil de prieteni.

Cerinta

Se cere numarul de beri pe care le va cumpara fiecare prieten k in limita sumei x de bani de care dispune. In caz ca x este mai mare decat costul berilor pentru toti prietenii de la masa, se vor achizitiona maxim N beri.

Date de intrare

Prima linie a fisierului de intrare br.in contine doua numere naturale N si T separate printr-un spatiu reprezentand numarul de prieteni si respectiv numarul de prieteni care doresc sa faca cinste prietenilor sai.
A doua linie a fisierului de intrare contine N numere naturale C1, C2 … CN, separate prin cate un spatiu, reprezentand costurile berilor preferate de fiecare prieten. Berea pentru prietenul i are costul Ci.
Fiecare din urmatoarele T linii contine cate doua numere separate printr-un spatiu:
k1 x1
k2 x2
…
kT xT
precizand indicele cate unui prieten care face cinste si respectiv suma de bani de care acesta dispune..

Date de iesire

Fisierul de iesire br.out va contine T linii, fiecare cu un singur numar Di reprezentand numarul de beri pe care le va cumpara prietenul ki cu suma de bani xi in conditiile problemei.

Restricții

  • 1 ≤ N ≤ 15.000
  • 1 ≤ T ≤ 10.000
  • 1 ≤ Ci ≤ 100
  • 1 ≤ ki ≤ N
  • 1 ≤ xi ≤ 3.000.000
  • Un program corect, care se incadreaza in timp pentru T ≤ 4000, va obtine cel putin 30 de puncte
  • Un program corect, care se incadreaza in timp pentru N ≤ 2000, va obtine cel putin 60 de puncte
  • Prietenii beau numai berea lor preferata.

Exemplu

br.in

5 4
10 5 15 22 13
1 32
4 50
1 9
4 200

br.out

3
4
0
5

Timp execuție pe test 0.1 sec
Limita de memorie 16384 kbytes

Explicație

Prietenul 1 cumpara cate o bere pentru el si pentru prietenii 2, 3. Costul celor 3 beri este 30.
Prietenul 4 cumpara 4 beri: cate una pentru el si pentru prietenii 5, 1, 2. Costul celor 4 beri este 50.
Cu 9 bani prietenul 1 nu poate cumpara nici macar berea lui.
Prietenul 4 cumpara 5 beri. Costul celor 5 beri este sub limita de cost 200.

Solutii

Aceasta problema prezinta mai multe solutii ce ar putea fi abordate, toate oferind acelasi punctaj (maxim).Voi descrie o solutie mai lenta( O(n * T) in cazul defavorabil (abordarea mea de la ONI 2009)) si va voi propune o solutie ce se poate face in timp logaritimic(O(T * log n)).

Solutia O(n * T) :
1. Citim initial intr`un vector pret, reprezentand costul berilor celor N prieteni.
2. Pentru a aduce optimizarea ce face diferenta dintre cele 100 de puncte si aproximativ 60-70 de puncte(aceasta solutie fiind cea dorita pentru un semi-punctaj) intr`o situatie similara calculam si suma totala a costurilor berilor.
3. Pentru fiecare i de la 1 la T verificam daca suma totala este depasita de suma prietenului i,atunci afisam valoarea N,daca valoarea este mai mica decat a primului prieten ,iar in caz contrar scadem si ne deplasam la urmatorul prieten(in acelasi timp incrementand o variabila contori).
4. Datorita faptului ca aceasta solutie intra in timp la limita si cu putin putin noroc nu este sugerata, insa se poate aduce o mica optimizare(neimplementata in solutia prezentata).Putem considera faptul ca daca suma prietenului i este aproape de st, sa se construiasca un alt vector ce va pastra suma totala necesara de la primul pana la al i`lea prieten si sa se inceapa de la al n-lea prieten calcularea ultimului prieten ce ii poate oferi bere.

Solutie O(n*T) problema Bere

Solutia O(T * log n)
1. Calculam sirul de sume partiale Sumi = C1 + C2 … + Ci
2. Suma costurilor berilor pe orice interval (i,j) va fi Sumj – Sumi – 1.
3. Folosind cautare binara si folosind vectorul Sum, cauti indicele p pana unde se pot cumpara berile incepand de la pozitia k.
4. Trebuie tinut cont de faptul ca sirul este circular si trebuie sa stabilesti unde se face cautarea binara : fie in intervalul [0,k] fie in intervalul [k+1,n-1]

Etichete: algoritmicaBereC++OlimpiadaONIprobleme informaticaprogramare

— 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 Microsoft vs Apple (again)
  • Articolul următor Dependenta de internet…

  • 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
  • mai 2022
    L Ma Mi J V S D
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Probleme algoritmică
  • [ONI][IX] Bere
  • 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