126 Lungimi de interval

[•Bluedrop_demon]

Nu stiu daca e cea la care te gandesti si nici de ce crezi ca ar fi neortodoxa. Insa am de facut o observatie: Ordonare in O(n*log n) si parcurgere/comparare in O(n) inseamna O(n + n*log n ) si nu O( n*n log n ) deci pana la urma e mai buna decat rezolvarea mea si ar putea obtine un timp mai bun!

[•ctes]

  intr-adevar...

[•Florian]

Rezolvarea pare ok si ar trebui sa se incadreze in timp. Numai sa nu fi gresit ceva la implementare. Depinde si ce sortare ai folosit. Complexitatea ar trebui sa fie maxim n^2 pe 3 sec. Nu cred sa intre n^3. Incearca alta metoda de sortare, poate o scoti la capat 

Ms mult...am folosit bubble sort..voi incerca quicksortul...

[•wefgef]

Quick-sort nu e cea mai rapida, doar ca la raportul timp/memorie e cea mai buna. Dar memorie e suficienta si pentru Interclasare.

Sort-ul din STL are complexitatea pe cazul defavorabil O(N log N) si merge in practica mai bine decat orice algoritm scris de mana.

[•Florian]

Ai putea sa mi detaliezi kum sta treaba cu " sort-ul din STL "? adik as vrea sa-mi explici putin...k nu stiu ce trebuie sa fac...(gandeste-te k e prima data knd aud expresia asta)

[•pauldb]

In principiu, primul lucru ar trebui sa lucrezi in C++. Tre sa bagi "#include <algorithm> si using namespace std;" la inceputul sursei. Apoi daca vrei sa sortezi vectorul a crescator, faci asa: sort(vector+pozitiestart,vector+pozitiefinal+1); [de exemplu sort(a+1,a+n+1);].

Daca vrei sa sortezi dupa alt criteriu poti face asa: sort(a+1,a+n+1,functie); si mai faci o functie cu criteriul respectiv de sortare care primeste doi parametrii. De exemplu:

int functie(int i,int j)
{
     return i>j;
}

Asta le sorteaza descrescator. Atentie! Nu pune si "=". Poti sa ai probleme.

Ah da...Nu exista asa ceva in Borland.

[•nash]

da .. dar in borland ai qsort ..

[•bogdan2412]

Nu prea as compara performanta unui compilator modern pe 32 biti cu unul pe 16 biti facut pt 386...

Oricum sort e mai rapid ca orice, inclusiv qsort

[•skyel]

apropo de stl, are careva un help in care sa fie explicate sintaxele si functiile(cum e cel de borland), ca din cate am observat versiunile de rhIDE nu au help iar Dev imi prind urechile urat de tot prin al help.
PS. ma refer exclusiv la windows(in linux n-am trecut de freecell  )
PPS. sorry pt offtopic

[•wefgef]

http://www.sgi.com/tech/stl/

[•nash]

 Nici nu am zis ca e mai rapid qsort decat sort din stl .. dar .. exista si solutia asta pentru borland .. asta daca nu vrei sa implementezi manual sortarea ....

[•Florian]

Lucrez in c++..insa in borland......multumesc pt ajutor...

[•Robytzza]

iar apelez la problema reactivi  nu se face lafel numai ca in loc sa numeri carte intervale gasesti numeri lungimea lor?? 

[•Florian]

Pai iti merge? Sa ai grija si ce sortare faci... 

[•ciprianf]

Mai...nu ma prind la exemplu:
intre -5 si 5 avem 11 nr noi(-5,-4...,0,...,4,5)
intre 0 si 3 avem 0 nr noi(au fost include in intervalul [-5,5])
intre 2 si 8 avem 3 nr noi(6,7,8)
intre 10 si 13 avem 4 nr noi(10,11,12,13)
intre 11 si 15 avem 2 nr noi(14,15)
intre 100 si 100 avem 1 nr nou(100)
 daca adunam :11+3+4+2+1=21

[•astronomy]

Citeste si tu toate posturile inainte.. La intrebarea ta gasesti raspunsul pe prima pagina, al treilea post.

[•ciprianf]

Ups, srry, nu m-am uitat ...dar oricum mi se pare putin cam ciudat ca nu e b-a+1

Intrebare: cum face evaluatorul online?  asteapta ca programul sa se incheie si apoi verifica ce este in .out sau verifica in timp ce programul ruleaza, iar in caz ca a afisat ceva gresit se opreste?

[•bogdan2412]

verifica la sfarsit, dupa ce s-a incheiat / a fost incheiat.

[•gabor_oliviu1991]

tot timpul asta mi se intampla...cand nu imi iasa o problema cer teste asa ca indraznesc la bunovointa voasta pt un test mai mare..

P.S.: pt testele mici imi iasa

[•fireatmyself]

Cod:

1
544
-873345 788007
-692110 207152
-94465 24653
-257215 405023
92809 139474
361686 396503
435859 444935
151831 174707
244333 259535
481994 496112
384878 420775
400840 424333
491070 533077
166125 177070
352835 400986
155282 182868
302803 338406
368261 401516
489988 508109
271273 276557
234764 272211
167500 216030
64356 97742
9523 17908
301329 312407
258218 299643
126630 163977
385213 418577
395798 415007
221707 265204
280593 301270
95311 142491
228732 268122
371445 399771
137553 154844
-588473 31004
-214733 685815
-144744 358243
-141595 558264
-371812 439210
-393338 613454
-308277 945311
-930815 674463
-788896 473118
-369187 333336
-667110 940362
-615149 486431
-327062 365057
-328000 937506
-313355 386190
-776667 720007
-535756 998642
-916011 205446
-963053 946012
-47625 547297
-17747 982486
-767986 107299
-349042 604624
-412223 959396
-849503 648673
-106441 425632
-36271 640592
-825863 710785
-374826 17823
-284617 387182
-92379 12614
-988287 635700
-461740 205132
-759039 84450
-888988 463776
-333019 718977
-742905 763855
-452833 631270
-250375 792216
-363644 585021
-830541 178005
-648955 526664
-38786 616727
-863686 778494
-824006 631685
-817363 419391
-943236 903217
-125638 333588
-913587 284125
-746196 429308
-625239 578191
-272620 742025
-679008 717687
-514266 283106
-70537 675705
-987972 346425
-899518 7314
-250380 671262
-710914 946802
-704131 483987
-589954 965032
-908832 157202
-150992 403640
-6088 364814
-666047 274366
-843566 456717
-60221 424013
-294129 402515
-587785 918108
-170609 904475
-163763 121526
-946825 329971
-978712 547870
-146627 595701
-777352 489624
-517116 976042
-117641 8070
-928611 235197
-360034 637599
-517962 527061
-612382 534964
-721182 236060
-150025 198509
-815755 45739
-806945 542294
-957137 435265
-265022 594387
-390959 447233
-345862 59305
-162455 762970
-79379 951247
-862035 289346
-243052 956301
-914578 172237
-673037 42353
-410719 634133
-474200 867646
-200577 96510
-106396 543666
-274290 363753
-628383 608022
-152059 899942
-954605 577916
-163682 605375
-133800 758327
-783398 136363
-929225 84433
-339845 189278
-489378 880722
-928567 668725
-677788 76485
-66024 475761
-784086 630154
-420339 196314
-376804 562166
-642436 426087
-301576 493164
-669218 267063
-226218 925452
-380760 597531
-611439 675587
-491021 975785
82196 106105
434261 436335
128004 176059
286330 323596
316645 339510
377142 420995
446035 489215
287216 306283
58491 104689
136272 184950
298458 300364
175622 199996
138940 148784
321222 368802
81163 108266
130219 138471
-922737 431339
-648817 734271
-495592 701823
-740609 698321
-286504 990906
-851815 922424
-591367 583711
-80172 327032
-744813 734440
-67968 844162
-551528 72191
-520686 298839
-144782 408509
-931750 348258
-257843 591924
-199859 583186
-192167 907402
-780028 581418
-639523 957516
-732975 988979
-649471 632128
-350140 852847
-902739 253186
-736461 187938
-689905 172517
-348848 36905
-614831 391643
-171740 49136
497166 508168
37618 86425
306835 340350
370796 419375
290481 337383
423767 453460
72629 119003
211554 260299
405732 443649
291626 324235
105870 131954
127062 132813
136970 179404
239980 270856
478819 506951
402541 404771
154090 200333
118898 138580
161859 175352
455393 503773
499506 539033
312888 339945
275132 322245
339443 382325
41005 82781
302928 349867
-526803 828336
-917414 701911
-339829 673774
-383701 469272
-374040 388407
-430942 615189
-896608 628936
-724893 767218
-117310 28665
-202131 260027
-425989 319078
-362172 758743
-836952 124488
-97965 354631
-131430 250613
-14330 45417
-946228 41626
-621032 742761
-183314 590668
-247391 861776
-14364 292952
-647156 91564
-168101 115341
-223390 881790
-53424 116556
-332262 393454
-674461 805477
-593111 20183
-518999 877981
-209815 740439
-325477 860609
-477569 40262
273955 285787
160549 168001
4802 6069
410769 453528
224314 263469
250853 292158
48231 49287
144905 151722
45884 90996
408718 446790
149605 198538
21832 57348
458609 482496
433437 451308
329607 372233
8941 50103
119576 121915
300543 340888
316157 348496
142856 179891
3913 41055
64348 66357
472190 505976
174609 175784
17320 60425
69692 116957
404002 404773
132480 170002
330068 374919
300816 304103
234358 252334
403646 405815
244212 250761
27963 50584
286575 293357
-301568 967200
-613178 702065
-295446 85522
-490263 526666
-451523 953814
-716146 151767
-807645 527867
-607362 560635
-907504 726845
-706938 672120
-820098 510287
-397125 665020
-694977 92324
-260894 167985
-80856 563829
-121356 245328
-753665 211234
-270761 832110
-964679 578861
-982709 848421
-176394 82535
-598171 16158
-636821 719270
-920666 244222
-524162 449163
-990900 600992
-931633 900159
-216948 981196
-483482 34163
-172697 758347
-929019 72004
-888557 509392
-376324 100642
-345105 375736
-167823 471361
-960428 807481
-647622 206142
-274343 589326
-260176 892223
-971651 857424
-97781 784648
-651829 457773
-753964 438060
-71067 365610
-5760 145951
-734972 414725
-957987 433940
-783849 368756
-384434 928026
-130549 461502
-483319 486386
-174869 257003
-73703 530801
-117116 904906
-160894 547061
-606098 958829
-772977 991781
-453847 792019
-728887 187341
-332374 507206
-216569 141115
-203325 80898
-217487 643707
-840453 195550
-599812 368447
-124776 987179
-541309 901509
-463287 384212
257751 284098
316882 362776
262435 282974
269128 298724
57660 67874
98823 126827
349724 361374
127232 143965
72051 95804
182774 226496
364257 391012
416840 420121
444940 467871
262730 281875
385355 386474
157275 186901
267242 271798
108440 154806
216941 229308
380014 403031
12399 51954
105225 141516
262204 301233
415040 419076
278221 282720
256451 281669
36192 47950
367307 374110
191074 207025
487239 533181
185427 194352
175579 183000
86677 134690
126521 157391
237884 267744
443831 475627
425601 449554
473068 503440
475339 480841
93470 106190
279055 308266
135293 175537
60531 92689
-530414 237906
-912764 38389
-951100 323594
-780371 749195
-244304 612530
-855793 18896
-448618 860108
-248948 356898
-548061 17412
-967112 940326
-508126 448432
-853298 248030
-590657 643367
-149577 939369
-299051 806975
-268402 154956
-118201 949966
-162474 159170
-367442 940122
-486192 423996
-52418 160202
-774794 310556
-788447 885875
-298799 78888
-1976 410685
-91786 652153
-465426 506429
-194564 518274
-813083 688582
-182092 216013
-899978 634016
-544650 781506
-956580 652650
-974033 66585
-949766 433505
-588444 391349
-365409 399956
-252634 832460
-20130 428108
-192044 741279
-442862 461070
-878644 393858
-323564 529145
-221377 468495
-227415 753854
-541100 563963
-547793 458896
-867418 186372
-156694 698178
-529661 384900
-780637 808543
-729736 357666
-753331 816867
-174315 852262
-139642 147279
-307500 165354
-846643 38836
-946652 856795
-230507 391311
-919013 878299
-887471 503136
-622696 471589
-550645 308474
-60272 166530
-342030 324693
-676783 612986
-418100 233946
-397358 811339
-679231 694503
-625739 473326
-823064 320760
-546500 62666
-940920 56697
-177633 905599
-498546 616953
-626722 916616
-432213 527779
-190581 440248
-116573 850273
-394487 459126
-143899 677416
-941636 216471
-286987 687781
-589912 501433
-162434 658920
-298509 713864
-964721 922427
-136755 82597
-789863 432930
-510682 882033
-769223 414297
-508096 475391
-589920 19526
-709721 781095
-640405 580526
-948582 144410
-478558 271607
-773398 784698
-879326 157696
-91663 135238
-700779 779539
-147985 418983
-567824 537809
-975946 879858
-575941 875482
-781382 399344
-412825 871663
-911936 49559
-668743 797245
-553639 350816
-42187 863189
-68320 309108
-336807 714124
-923801 438505
-449587 197978
-805578 765488
-313530 621686
-834763 789170
-806982 291595
-336492 238264
-875021 748182
-928914 440134
-886725 862126
-480227 876567
-504322 370382
-758 114618
-369724 319287
-312951 596375
-590464 365097
-984983 667322
-365095 590845
-104833 854269
-84503 477433
-578721 746814
-488944 845955
-365813 591612
-943622 269465
-219268 767758
-392385 988986
-765077 907778
-242531 937701

lungimea este 1989542.

[•gabor_oliviu1991]

am observat ca in exemplul tau, mi-ai dat 546 de intervale... acuma ce sa inteleg: ca trebuie eleminate doua intervale de acolo, sau n=544  lamureste-ma plz

[•gabitzish1]

Daca pui exemplul exact asa cum e acolo, o sa se ia in considerare doar primele 544 intervale. Raspunsul ar trebui sa fie acelasi.

[•gabor_oliviu1991]

da, aia am inteles, dar daka eu mai pun un test...pica...o sa imi citesca n=-700000 ceva pe acolo...si din aia nu eram lamurit

[•fireatmyself]

imi cer scuze, am numarat prost  . si cu n=544 si cu n=546 iti da acelasi raspuns, 1989542. sper sa te ajute 

[•gabor_oliviu1991]

am reusit pana la urma sa o rezolv.. merci mult