fork download
copy 
  1. program sairsodo;
  2. const MAXN=100000; 
  3. type elenco = array[1..MaXN] of int64;
  4. var N,i,d, idmediana, idmediana1, mediana:int64;
  5.     calcolacosto,calcolacosto1, altezzainiziale, altezzainiziale1:int64;
  6.     costo, costo1, costomin, ricordacostomin:int64;
  7.     H, ricordaltezze: elenco;
  8.     uscita:boolean;
  9. Procedure scambia (var a,b: int64);
  10. var x:int64;
  11. begin
  12.    x:=a;
  13.    a:=b;
  14.    b:=x;
  15. end;  
  16. Procedure ordinamento (estremoi,estremos: int64; var v : elenco; ordinato:boolean);
  17. var inf, sup, medio:int64;
  18.     pivot :int64;
  19. begin
  20.     inf:=estremoi;
  21.     sup:=estremos;
  22.     medio:= (estremoi+estremos) div 2;
  23.     pivot:=v[medio];
  24.     repeat
  25.       if (ordinato) then
  26.          begin
  27.             while (v[inf]<pivot) do  inf:=inf+1;
  28.             while (v[sup]>pivot) do  sup:=sup-1;
  29.          end;
  30.       if inf<=sup then
  31.        begin
  32.          scambia(v[inf],v[sup]);
  33.          inf:=inf+1;
  34.          sup:=sup-1;
  35.        end;
  36.     until inf>sup;
  37.     if (estremoi<sup) then ordinamento(estremoi,sup,v,ordinato);
  38.     if (inf<estremos) then ordinamento(inf,estremos,v,ordinato);
  39. end;
  40.  
  41. begin
  42.    (* assign(input,  'input.txt');  reset(input);
  43.     assign(output, 'output.txt'); rewrite(output);*)
  44. 	readln(N);
  45. 	for i:=1 to N do begin read(H[i]); ricordaltezze[i]:=H[i]; end;readln;
  46. 	costo:=0; costo1:=0; d:=0; costomin:=9223372036854775807; ricordacostomin:=9223372036854775807; uscita:=false;
  47. 	ordinamento (1,N,H, true);
  48. 	if N mod 2 <>0 then 
  49. 	                 begin
  50. 	                   idmediana:=(N+1) div 2;
  51. 	                   altezzainiziale:=H[idmediana]-(idmediana-1);
  52. 	                   if altezzainiziale<0 then altezzainiziale:=0;
  53. 	                   for i:=1 to N do
  54. 	                         begin 
  55. 	                             calcolacosto:=(ricordaltezze[i] - (altezzainiziale +i-1));
  56. 	                             if calcolacosto<0 then calcolacosto:=-calcolacosto;
  57. 	                             costo:= costo + calcolacosto ;
  58. 	                         end;
  59. 	                      writeln(costo);
  60. 	                end
  61. 	              else 
  62. 	               begin
  63. 	                idmediana:= N div 2;
  64. 	                idmediana1:=idmediana+1;
  65. 	                mediana:= (H[idmediana]+ H[idmediana + 1]) div 2; (*altezza che corrisponde alla mediana*)
  66.  
  67.  
  68. 	                while uscita=false do 
  69. 	                                    begin
  70. 	                     	                altezzainiziale:=mediana-idmediana; (*vario di +-1 il valore della mediana finchè trovo il costo minore*)
  71. 	                                        altezzainiziale1:=mediana-idmediana1; 
  72. 	                                        while altezzainiziale<0 do altezzainiziale:=altezzainiziale+1;
  73. 	                                        while altezzainiziale1<0 do altezzainiziale1:=altezzainiziale1+1;
  74.  
  75. 	                                        if altezzainiziale<0 then altezzainiziale:=0;
  76. 	                                        if altezzainiziale1<0 then altezzainiziale1:=0;
  77. 	                                        for i:=1 to N do
  78. 	                                               begin 
  79. 	                                                  calcolacosto:=abs(ricordaltezze[i]-d - altezzainiziale-i+1);
  80. 	                                                  costo:= costo + calcolacosto ;
  81. 	                                                  calcolacosto1:=abs(ricordaltezze[i]+d - altezzainiziale1-i+1);
  82. 	                                                  costo1:= costo1 + calcolacosto1 ;
  83. 	                                             end;
  84.  
  85. 	                                       if (costo>=costomin) and (costo1>=costomin) then begin uscita:=true; continue; end;
  86. 	                                       if costo<costo1 then costomin:=costo
  87. 	                                                       else costomin:=costo1;
  88.  
  89. 	                                      writeln(costo,' ', costo1,' ', costomin,' ', altezzainiziale,' ',altezzainiziale1);
  90. 	                                      costo:=0; costo1:=0; d:=d+1;
  91. 	                                   end;
  92. 	     writeln(costomin);          
  93. 	  end;
  94. end.
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
1000
290852541 66988985 717401112 865455665 182811308 730087285 385463286 531287043 665477002 111229778 137441935 26865323 886053605 671359093 894851842 478150616 183526400 99262092 326652023 913157944 831189951 666778270 422466540 365798622 685286189 667869011 484134620 222111028 100237557 722796575 316858455 243606450 642301912 886775919 109062116 825113221 469379556 347041754 208916616 134856559 310787885 346358552 14238234 49357842 870233997 909090076 527508459 53760398 8352169 854160482 819434694 692058472 373455104 94417587 57857094 58741293 762286598 394508066 133368673 715040508 117304641 450227128 958646958 612122906 189519399 67709074 289752479 658898956 267267181 498669095 793755515 578055066 697543999 660510101 627412908 567777997 422116529 154921367 474054747 282985050 861598202 146005793 975043522 87569658 240423380 32900616 146310952 2709979 279925035 132195977 717750487 249746028 582423106 528913797 861868934 771942505 449139224 4137765 283357813 716406405 355323213 77113328 294461471 52867212 590139781 921874379 473161561 12256311 929312099 947216308 295241361 790910301 93222102 122801236 878479959 186161834 8218204 877307263 188871813 288143239 9503241 759138652 537889268 444442699 288052450 252274554 68901556 737191674 256412320 352259370 306114431 611735533 281889050 600575902 517119097 872028832 374966633 990280659 736801495 156795084 790013319 32042856 947705385 735751773 7360444 678701697 921913608 15578649 408525312 110785421 303721888 270544905 722440426 841611156 567503956 10492876 93885711 636405513 600200902 202814383 841181235 906315333 814549916 123070285 359407587 184185365 847615469 586890572 174466024 436933316 743685657 964479344 321492525 543907394 552747469 328852969 75125443 474661077 344431618 483650756 437962851 648153507 606712013 12919629 489764663 174215970 23412505 436166726 663137835 476129759 638981109 504319070 234961444 306047377 479905707 446885383 490232743 180037529 33775955 664698767 616970845 777461612 481694463 938463370 173885359 34441933 119832692 249010802 361619362 464264310 732661558 652098565 112417817 191889924 665018194 454698833 366105894 540947051 890865559 29243729 17076810 529846669 386079151 104554606 835894046 718501210 551439989 178643141 898538739 437732297 843341909 368025937 67710261 177552724 159005659 241595620 64511009 278838351 490606423 278646724 743102662 75784333 930745289 708036831 267674257 595763484 162735664 633780151 136710535 53601224 515540232 6303698 435964245 754135735 963374656 124374643 472636946 367330998 303017785 223692037 805063295 998876046 444234326 872773556 28945122 603239986 114369177 93456132 734594689 604975600 372102856 330213703 680759933 155364497 38250535 948434191 751127981 53502551 434730694 740354869 107103775 802787279 599174919 395584372 556923014 415065927 372475368 882076312 782396925 675493153 105768350 587460220 526885551 402519028 312750129 555830673 5759014 427119306 649286805 592870056 884611258 873906013 923083759 417887543 29270511 961334294 218838086 632914844 14836846 653568781 225786065 974456973 308872412 824960984 222557698 865795426 92543264 595033066 600388091 874940189 123042571 558672793 314916762 649928122 961191821 627666891 58275147 819467188 54786197 707561953 412337244 791913807 433984318 187937355 209801350 463254829 1788002 428639437 96169674 16624848 934724570 174472091 843598173 243596982 999433076 918672223 961908760 91976340 366221641 562296851 819432881 489264212 120969644 134349643 991708686 934677818 762016534 49983834 754145006 669319083 610062139 18998602 313749242 44046457 206935957 523550593 359817639 208723959 804706382 308503665 77865159 739430952 482975756 773979685 835544286 334925184 692651908 797453046 279417876 58873550 212266250 98850758 400654114 185752246 85716753 244879153 120430064 847733288 294862987 727091422 369568723 904925126 598606376 683317966 801487935 805542334 59384911 161305574 866782645 864091293 469809239 944647805 456038597 952784996 571143842 144099235 140226532 116312102 941552281 419644409 27702004 6334883 518495167 428356119 44603482 604211920 673235272 17549898 304461560 820614611 744641321 526546636 578056089 195764049 62380954 379544024 1306383 121765865 393365951 720605381 838373510 863175190 517769538 146928459 668476538 88913380 291027694 808703071 205225482 85096327 80863832 232927487 91431211 599358999 513799958 136034693 56087271 39551582 153584591 213065184 860166193 750742264 739611820 438222282 946506314 801992774 670282658 800329049 923758639 63648609 520934430 614648501 779340152 38703968 761576960 300333042 980133700 52604654 109036113 37875535 137700981 42416297 270803022 81648544 641775296 784602980 217683237 550378920 824154562 223784181 763444104 536837107 974526445 503055924 975059389 921032759 157565050 497858399 573878161 81323689 561507009 94812591 548488542 193363513 986032912 310065502 493696555 818682964 215186508 455249021 856558499 352887489 497665318 127361521 434536034 139440615 764480853 504735623 542335887 441151767 728519804 305779991 977988874 703046250 661352267 805564615 476595361 818917317 155939367 50473522 752757358 717446376 997802466 301245900 910809889 836351730 463827754 257022796 507551046 679014262 712271817 364109546 31901751 209937136 343987419 318954137 201894103 960984625 823689761 744229990 254652744 404725917 902526333 85157971 107772167 563878600 890722586 436883881 235312269 46661953 339873755 988069627 616624681 190192573 141831879 379950922 879060655 605659633 636973719 386611702 284673895 201761888 603237600 169091998 411699024 947225019 340562488 466109479 760725996 16768601 62855821 15378741 421494518 965382154 100536712 381783038 381777106 843775650 818666919 617089375 742953956 11057026 605159002 212094989 53765952 746990881 592045912 932826607 205166866 81535983 171954661 489840761 283297871 775192261 511449112 547513248 574933633 852011600 13622727 335659629 868780201 76478549 203554722 290274719 41860703 304091434 672057757 276154162 383437 343241028 893243537 743337393 206814407 350918892 955432382 260580359 97909773 399994646 193406966 155592992 481530629 365361628 645433753 617344853 140553889 9399217 164858101 568003874 861410817 30997180 903663504 730191018 107475729 107218226 872982090 1852785 263826013 397556199 278006947 264209450 740797228 23766836 7546843 947611635 374685728 815495577 60708346 325111854 215490224 254115312 480704846 549537205 471993292 126138599 166882058 465063534 135537817 184256511 33067408 849464986 215253692 789247264 432172357 322729421 748981843 305154447 177098558 12807856 702710646 455105505 129533658 296024226 478872342 989596853 96152213 853558070 805092430 156860559 31186276 873099006 263492224 511891122 422636212 735485516 490546074 442034622 200549050 478600243 626291134 86132811 328065229 841544826 875380075 760237586 16790599 624361918 917908385 193889158 489686126 473135384 648994663 471736136 769159610 980383357 461332989 717828176 686457780 118941772 874688735 717644056 992040778 138180959 229535179 267193342 726182828 720081253 709227965 926731878 51197848 188035451 12864689 379263077 29580277 740761117 992017016 46370876 217639387 909925401 240260034 707325514 235577137 741771050 31578002 4736748 722154407 492910992 575081276 261128539 464369116 302286363 978772596 308926246 292983675 60824127 576119589 19166503 780905380 137863906 798414733 832103228 325899357 663795775 63882657 207995986 404556892 55899673 254366862 622196279 818341427 347143249 182038145 53918564 88914299 213616148 911171664 663585058 559043492 338769292 924713598 23412608 641055656 903486194 332338854 934039331 964310321 760974795 953205834 597732053 898838701 604136919 282351633 77254410 267932694 198750642 285250396 525005938 107166668 392133611 147202218 925508095 739276860 181756715 831943011 828191159 247889215 595631028 344292569 806932707 934400320 269006167 830345315 427972328 25008713 15200522 362011659 841835386 776175317 167733845 292083791 527530371 771870765 574435424 457301133 892319811 773186067 742551530 417325750 880352735 134685141 417044320 658377182 726478353 451317387 342836545 407185864 699206603 790983925 751478433 506139310 577900598 20484601 189000978 5872926 898009666 56717852 220400938 739845053 832893169 388134783 31928844 212939892 12521900 458880621 670241026 904841712 84583040 265308908 174683814 817452127 252510401 444244486 328345661 978988754 895561873 671182206 238690970 594768476 314682484 990169403 953424139 892583082 863170356 142425117 898456008 761180023 51659321 118856946 353541428 884552490 359508082 237986624 950008735 224546334 549383597 472766113 129388046 633966637 738075021 156588212 303935116 843101774 600832698 632280777 674606880 348910924 155979336 913297850 943679400 470661820 903467253 749619891 363244902 619153962 744561360 114217262 232850337 796220681 85590561 586391765 533289524 297614995 676894741 483298259 522161329 226278339 956064372 504065728 712761328 546655745 660653940 16696445 242273871 114002991 648977222 916880751 462913915 804956558 830178601 259109667 128134730 586162206 8729559 491379632 57832520 605807271 458113247 290682857 402027953 543703808 877074622 935317477 841318803 406485716 271132088 215996484 632764055 79712812 720062212 198041735 478884909 233232505 214738180 721158780 347235496 716231755 638039531 662665763 373704665 320734484 921775430 501839396 759413042 783021341 993219028 817245563 241344965 303848627 107928420 643372918 847552435 837519395 431206747 541387590 244005111 554855187 757384075 729285518 634567999 329962639 927327253 113452908 563195144 142065434 687128040 910430640 710813541 177683923 425612755 84518206 498418407 199904538 586357602 110347801 982925879 432092983 927593364 76787196 735941610 35521785 720160114 436010398 725557532 3883213 829914340 969562643 558738400 439814767 551364513 45822751 769777407
stdout
copy 
259760653037 259760653037 259760653037 457706690 457706689
259760653037
https://ideone.com/rJkuzH
language:
Pascal (fpc 3.0.4)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!