714 - Copying Books

viniciusweb · Post by **viniciusweb** » Wed Aug 22, 2007 9:02 pm

Thanks Jan! I got AC after fixing some problems with overflow...

coze · Post by **coze** » Fri Aug 08, 2008 5:53 pm

I've got the right output for the simple input, but the result of submission is WA.

Can you tell me what is your output with this input ?

Input:

Code: Select all

3
12 5
48 65 53 3 90 3 90 30 52 75 54 22
10 4
82 36 6 11 33 33 25 79 9 7
9 5
64 16 75 91 1 71 43 81 13

My WA output:

Code: Select all

48 65 / 53 3 90 / 3 90 30 / 52 75 / 54 22
82 / 36 6 11 / 33 33 25 / 79 9 7
64 / 16 75 / 91 1 / 71 43 / 81 13

viniciusweb · Post by **viniciusweb** » Fri Aug 08, 2008 6:13 pm

coze, my AC code produces the same output.

coze · Post by **coze** » Fri Aug 08, 2008 10:53 pm

Thank you, viniciusweb. I got AC now.

bourne · Post by **bourne** » Mon Sep 22, 2008 2:41 am

I am getting correct result for all the test cases posted in this thread. Still I am getting WA at the judge. I used the binary search + greedy approach as discussed in this thread. Can someone figure out my mistake or post some more tricky cases?

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<sstream>
#include<map>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
using namespace std;
#define PB push_back
#define vi vector<int>
#define LL long long
#define all(v) v.begin(),v.end()
#define GI ({int t ; scanf("%d",&t);t;})

int M,K;
int A[500];
bool go(LL maxsum)
{
	LL sum=0;
	int k=1;
	for(int i=0;i<M;i++)
	{
		if(sum+A[i]>maxsum){
			sum=A[i];
			k++;
		}
		else
			sum+=A[i];
	}
	return (sum<=maxsum && k<=K);
}
void print(LL maxsum)
{
	int k=1;
	vi res;
	res.PB(A[M-1]);
	LL sum=A[M-1];
	for(int i=M-2;i>=0;i--)
	{
		if(sum+A[i]>maxsum){
			res.PB(-1);
			res.PB(A[i]);
			sum=A[i];
			k++;
		}
		else{
			res.PB(A[i]);
			sum+=A[i];
		}	
	}
	reverse(all(res));
	

	while(k<K)
	{
		for(int i=1;i<res.size();i++)
			if(res[i-1]!=-1 && res[i]!=-1){
				res.insert(res.begin()+i,-1);
				k++;
				break;
			}	
	}

	printf("%d",res[0]);
	for(int i=1;i<res.size();i++)
	{
		if(res[i]==-1)
			printf(" /");
		else
			printf(" %d",res[i]);
	}
	printf("\n");		
}
int main()
{
	int t=GI;
	while(t--)
	{
		M=GI; K=GI;
		for(int i=0;i<M;i++) A[i]=GI;
		
		LL lo=0,hi=1LL<<40;
		for(int i=0;i<50;i++)
		{
			LL mid=(lo+hi)/2;
			if(go(mid))
				hi=mid;
			else
				lo=mid;
		}
		print(hi);
	}
}

Angeh · Post by **Angeh** » Sat Sep 18, 2010 3:19 am

1
6 3
8 3 5 4 1 10

Angeh

ss89162504 · Post by **ss89162504** » Sat May 07, 2011 6:46 pm

please help me debug

my method is binary serch

i thought i have trouble on mark the splash character

(the bool array anw[10000] : if anw ==true means that is should print '/' before x)

thx=)

Code: Select all

#include<iostream>

using namespace std;

int N,m,k;
int x[10000];
int L,H,M;
bool anw[10000];
bool check(int a)
{
     int tmp=0,q=1;
     for(int i=m;i>=1;i--)
     {
          tmp=tmp+x[i];
          if(tmp>a)
          {
               q++;
               tmp=x[i];
          }
     }
     if(q<k)return true;
     else   return false;
     
}

main()
{     
     while(cin>>N)
     {
          while(N--)
          {
               cin>>m>>k;
               L=100000000;
               H=0;
               for(int i=1;i<=m;i++)
               {
                    cin>>x[i];
                    H=H+x[i];
                    if(x[i]<L)L=x[i];
               }
               while(L<=H)
               {
                    M=(L+H)/2;
                    if(check(M))H=M-1;
                    else        L=M+1;
               }
               for(int i=1;i<=m;i++)anw[i]=false;
               int tmp=0,q=1;
               for(int i=m;i>=1;i--)
               {
                    tmp=tmp+x[i];
                    if(tmp>M)
                    {
                         anw[i+1]=true;
                         q++;
                         tmp=x[i];
                    }
               }
               int c=1;
               while(q<k)
               {
                    if(!anw[c])
                    {
                         anw[c]=true;
                         c++;
                    }
                    q++;
               }
               cout<<x[1];
               for(int i=2;i<=m;i++)
                    if(anw[i])cout<<" / "<<x[i];
                    else      cout<<" "<<x[i];
               cout<<endl;
          }
     }
}

sohel · Post by **sohel** » Sat May 07, 2011 10:53 pm

Use the search option located at the top right corner to find existing discussions.
Don't create a new thread for a problem that already exists! Make your post on an existing one.

brianfry713 · Post by **brianfry713** » Wed Oct 10, 2012 10:44 pm

Input:

Code: Select all

10
68 26
31730 22830 3272 4144 16256 20385 2435 13740 20324 10870 27414 4722 11245 10638 15417 29839 19155 4537 26608 21387 25380 26684 21840 20034 3058 27140 29714 10883 6590 15014 1497 12906 26275 1822 12355 2942 28994 6212 9137 25481 32369 4365 25303 3899 10659 21639 30466 30333 4117 20370 7468 27286 702 8799 14273 16896 27380 26026 4399 22024 19934 1975 15152 15912 6813 32014 5847 25893
89 76
20828 21479 16461 25010 24999 19995 3955 5245 21150 7306 7277 3399 26158 8503 15640 5678 23835 4411 18449 8891 28552 28769 15908 23265 16966 10881 7801 22966 25820 26269 20861 7150 9306 28605 22161 23068 16094 20362 8309 19113 17379 30381 19571 1936 11597 3813 8267 5087 32053 21226 31458 15597 27764 2053 9129 21340 30193 30060 9422 30669 19115 30047 7205 30566 31365 31747 11989 29701 24021 12289 3010 21569 2987 28894 10430 14117 26849 26393 9839 26539 7143 31238 1790 3066 29003 18285 9093 3167 32011
45 20
28173 1178 4834 16202 7573 32180 6578 25264 25891 11746 10231 27762 2686 14028 21270 26087 20670 6978 31050 13723 22986 2313 21894 7166 9112 29541 29968 20175 7460 19051 27353 24390 3885 23299 23711 22276 21682 9151 17857 14267 7984 10847 3045 18845 17048
12 12
25734 17682 21193 12528 8168 11892 24691 4195 5498 21377 29723 29542
64 34
7401 23884 21657 27108 8765 3085 27498 24311 11903 22825 8078 20450 23203 19522 5722 19911 26239 15224 12594 16603 10700 5508 9070 9697 2558 12691 31498 10091 196 16616 2063 3792 32605 15920 20165 18668 15009 30372 28822 31386 11210 2273 14272 24818 20999 30087 12738 31043 191 7571 1156 11471 18085 19069 27204 31817 14720 7185 69 26383 12984 30734 21558 2600
91 14
23651 13052 4229 3549 18077 25045 30074 26082 18922 30745 12257 12331 26349 3652 10681 8085 17172 11688 23467 3924 2691 27108 28371 3795 1220 5670 12111 20302 18475 4640 7048 20273 14346 27339 7235 24368 14746 19166 12646 23843 19364 30477 8075 16551 27890 20994 27206 21877 32121 9244 10038 16256 1603 8938 30158 9425 5150 29798 10209 6435 4359 10737 26351 10045 18516 28434 25137 5139 419 26606 20838 14236 24197 31623 22620 1906 26347 1461 5949 12075 28748 11492 29599 21113 19356 22419 26185 21764 26093 32136 22982
10 1
20691 26028 15772 8151 31370 29353 29185 17105 26430 4946
26 5
24383 7596 260 25581 26260 20854 30896 1061 8377 5948 23480 13477 13334 9245 29283 24007 26948 3671 23141 29138 511 7831 19525 32043 1001 27139
51 21
29444 259 1560 6687 14317 16083 17878 24339 11737 1482 23035 19868 5201 29799 2741 1911 24749 24352 11238 2884 11090 6891 708 32754 13483 25737 26928 19178 15848 28821 19160 23803 12665 28752 22539 25096 22345 5929 2655 16243 4283 27919 22277 3400 22629 31095 10983 30249 399 4908 3206
50 46
24794 32662 20313 23568 22104 1622 8106 5951 15032 23729 6694 17621 785 18710 31096 19211 3591 7960 22566 16497 3103 20421 12226 31149 8388 9158 7893 14067 2072 31547 8587 11587 19836 12115 10526 26470 24286 29103 15875 15014 2245 17780 6359 19280 10014 28210 24072 23786 5828 28792

AC output:

Code: Select all

31730 / 22830 / 3272 4144 16256 20385 / 2435 13740 20324 10870 / 27414 4722 11245 10638 / 15417 29839 / 19155 4537 26608 / 21387 25380 / 26684 21840 / 20034 3058 27140 / 29714 / 10883 6590 15014 / 1497 12906 26275 / 1822 12355 2942 28994 / 6212 9137 25481 / 32369 / 4365 25303 3899 10659 / 21639 30466 / 30333 / 4117 20370 7468 / 27286 702 8799 14273 / 16896 27380 / 26026 4399 22024 / 19934 1975 15152 15912 / 6813 32014 / 5847 25893
20828 / 21479 / 16461 / 25010 / 24999 / 19995 / 3955 / 5245 / 21150 / 7306 / 7277 / 3399 / 26158 / 8503 / 15640 / 5678 / 23835 / 4411 / 18449 / 8891 / 28552 / 28769 / 15908 / 23265 / 16966 / 10881 / 7801 / 22966 / 25820 / 26269 / 20861 / 7150 / 9306 / 28605 / 22161 / 23068 / 16094 / 20362 / 8309 19113 / 17379 / 30381 / 19571 / 1936 11597 3813 8267 5087 / 32053 / 21226 / 31458 / 15597 / 27764 2053 / 9129 21340 / 30193 / 30060 / 9422 / 30669 / 19115 / 30047 / 7205 / 30566 / 31365 / 31747 / 11989 / 29701 / 24021 / 12289 / 3010 21569 / 2987 28894 / 10430 14117 / 26849 / 26393 / 9839 / 26539 / 7143 / 31238 / 1790 3066 / 29003 / 18285 9093 3167 / 32011
28173 / 1178 4834 16202 / 7573 32180 / 6578 25264 / 25891 11746 10231 / 27762 2686 14028 / 21270 26087 / 20670 6978 / 31050 13723 / 22986 2313 21894 / 7166 9112 29541 / 29968 / 20175 7460 / 19051 27353 / 24390 3885 / 23299 23711 / 22276 21682 / 9151 17857 / 14267 7984 10847 / 3045 18845 17048
25734 / 17682 / 21193 / 12528 / 8168 / 11892 / 24691 / 4195 / 5498 / 21377 / 29723 / 29542
7401 23884 / 21657 / 27108 / 8765 3085 27498 / 24311 / 11903 22825 / 8078 20450 / 23203 / 19522 / 5722 19911 / 26239 15224 / 12594 16603 10700 / 5508 9070 9697 2558 12691 / 31498 / 10091 196 16616 / 2063 3792 32605 / 15920 20165 / 18668 15009 / 30372 / 28822 / 31386 11210 / 2273 14272 24818 / 20999 / 30087 / 12738 / 31043 / 191 7571 1156 11471 / 18085 19069 / 27204 / 31817 / 14720 7185 / 69 26383 12984 / 30734 / 21558 2600
23651 13052 4229 3549 18077 25045 / 30074 26082 18922 30745 12257 / 12331 26349 3652 10681 8085 17172 11688 23467 / 3924 2691 27108 28371 3795 1220 5670 12111 20302 / 18475 4640 7048 20273 14346 27339 7235 / 24368 14746 19166 12646 23843 19364 / 30477 8075 16551 27890 20994 / 27206 21877 32121 9244 10038 16256 / 1603 8938 30158 9425 5150 29798 10209 6435 4359 10737 / 26351 10045 18516 28434 25137 5139 / 419 26606 20838 14236 24197 31623 / 22620 1906 26347 1461 5949 12075 28748 11492 / 29599 21113 19356 22419 26185 / 21764 26093 32136 22982
20691 26028 15772 8151 31370 29353 29185 17105 26430 4946
24383 7596 260 25581 26260 / 20854 30896 1061 8377 5948 23480 / 13477 13334 9245 29283 24007 / 26948 3671 23141 29138 / 511 7831 19525 32043 1001 27139
29444 259 1560 6687 / 14317 16083 17878 / 24339 11737 / 1482 23035 19868 / 5201 29799 / 2741 1911 24749 / 24352 / 11238 2884 11090 / 6891 708 32754 / 13483 25737 / 26928 19178 / 15848 28821 / 19160 23803 / 12665 28752 / 22539 25096 / 22345 5929 2655 16243 / 4283 27919 / 22277 / 3400 22629 / 31095 10983 / 30249 399 4908 3206
24794 / 32662 / 20313 / 23568 / 22104 / 1622 / 8106 / 5951 / 15032 / 23729 / 6694 / 17621 / 785 / 18710 / 31096 / 19211 / 3591 / 7960 / 22566 / 16497 / 3103 / 20421 / 12226 / 31149 / 8388 / 9158 / 7893 / 14067 / 2072 / 31547 / 8587 / 11587 / 19836 / 12115 / 10526 / 26470 / 24286 / 29103 / 15875 / 15014 / 2245 17780 6359 / 19280 10014 / 28210 / 24072 / 23786 5828 / 28792

ree975 · Post by **ree975** » Sun Apr 06, 2014 4:22 pm

Jan wrote:My accepted code returns..

Output

My ans is different from yours, but I also get AC.

Take a look~

Code: Select all

9 8 / 1 7 6 / 2 3 4 5
1 / 2 1
10 / 2 10 2 15 / 20 / 1 30
46 18 71 6 35 / 59 35 52 83 / 62 85 71 / 72 88 46 / 100 8 5 89 / 85 61 80 / 59 43 39 51 31 / 100 90 40
198429 225879 / 591107 583645 268500 151557 563518 / 248740 722030 674754 235494 / 165111 4520 807760 7269 710494 636769 / 334106 963142 541561 171837 78214 / 5965 883949 226710 299323 900222 / 102726 122447 163449 307908 873977 702390 / 901413 140877 843943 / 656618 304012 907339 / 34834 658439 148739 243226 352932 473060 122583 / 390594 545667 566414 769880 / 54794 927040 819584 / 300102 761380 412128 566990 / 766983 318949 691513 377512 / 157581 131870 155107 47900 261108 618196 849399 / 78421 650093 429882 664391 / 80298 592935 628864 370927 214123 / 492610 978070 61186 297876 235107 170694 / 414682 523083 901046 437256 / 306467 573591 359337 875292 / 778025 470884 701014 / 31795 345026 324202 791498 696259 / 900218 333581 770868 / 976227 701569 / 204631 312424 590689 135264 31786 850965 / 100374 642051 278100 311220 364042 446340 / 711410 5176 68123 756459 13430 189598 323062 / 63556 177330 535293 506933 866114 / 302950 30504 680091 868833 / 319799 503602 319554 961825 227936 / 774472 167523 456540 768584 / 831825 957276 / 292280 773926 128255 881208 / 991461 358430 762594 148155 / 225787 23283 46559 549856 505529 960914 / 242559 755090 753257 / 164380 608422 329481 922946 / 179008 203746 221602 476370 250162 493750 / 721156 595250 774471 / 135868 631691 960930 / 134439 152474 580281 869130 427253 / 894328 852244 275992 304562 / 228685 825766 165977 337864 608874 / 77083 83037 959566 836837 / 791824 454050 561105 / 776791 834506 480150 / 966327 281397 319832 395378 / 771665 442373 970685 / 467177 439158 159457 75347 935617 / 539027 343771 179989 418739 137422 529877 / 141552 174986 492927 177445 598931 232239 377814 / 661774 339044 361603 979889 / 820655 568922 662296 / 910813 894657 538153 / 203560 333530 625555 61562 510683 477338 / 255431 166783 836501 85264 83957 719628 / 101784 281429 443673 955446 / 780613 787113 / 243172 892947 612250 16267 419960 / 946403 279025 965493 / 749942 431565 409349 585400 93642 / 618251 749098 980731 / 685603 415042 976746 / 475490 660470 578759 / 487447 271643 638432 393958 / 891775 767131 676623 / 535567 232413 700618 348825 / 971863 445381 296164 2629 59751 431585 / 673073 864507 758631 / 785422 325968 140684 657034 355143 / 509594 636610 950725 / 932263 444819 516898 / 542988 834674 865585 / 881331 16093 963873 / 718120 796405 / 553691 331891 718001 51733 290238 80315 / 459943 376249 545094 433518 508487 / 386036 683954 860464 313346 / 120405 114055 268164 594847 122581 239915 658833 / 7172 568797 215259 428107 532799 55728 / 911849 475560 240223 698220 / 886813 455973 392124 / 270443 224029 661415 865820 / 739092 136893 551824 692232 / 841494 971008 / 280350 638878 448007 741625 / 968839 336399 302198 613335 / 154362 808391 497471 557747 / 847473 772339 37606 286386 / 618458 764286 777064 / 399574 301393 437041 185330 470170 129889 59897 23952 20660 / 210430 860125 593983 682568 / 196016 590736 790523 209102 / 302526 5104 996233 920238 / 681565 182650 683855 / 626972 880027 830125 / 695347 780381 201717 195558 289103 / 735989 755440 810417 / 701663 60882 900789 / 127515 223784 563781 937038 / 343232 730319 325741 883902 / 942707 297927 680658 299050 / 753989 12233 797143 604734 / 129908 536677 324282 496847 702928 / 452511 434497 244819 571622 / 365775 871803 115496 909997 / 293049 16069 759937 524808 447231 125365 / 487528 298355 674720 35886 750638 / 349355 138458 311402 36476 360745 668991 / 770441 990497 / 353708 21727 204313 330968 486560 / 938009 427241 582572 / 396421 52658 507560 51008 205684 573839 / 834945 411782 780269 / 161774 355807 250602 238580 637995 / 637956 642036 968597 / 489363 953260 / 910383 776319 / 17240 566176 672394 704016 / 928455 666896 557124

brianfry713 · Post by **brianfry713** » Mon Jun 09, 2014 11:06 pm

Input:

Code: Select all

3
459 251
7569184 5882487 6410068 4803758 1651606 528544 5199435 5091223 6199923 1220462 841672 1764693 6583622 6996188 8517072 8931298 3410482 684741 616687 5457537 8866815 3532222 874843 7244092 6526517 504253 7932159 9941819 2733645 1948779 3214578 2818966 347403 2140783 7622723 1999008 5185463 5338295 9606367 1385386 9074894 448039 3150079 5658516 9960363 1667151 7105952 5886983 4868029 238776 1344520 3734844 3770997 2219363 3495074 297515 5239752 1427233 2755471 7973397 5892148 8486185 792363 8755687 626968 931224 754695 5812430 6269518 2877199 9713953 5344412 5841374 2864032 3519066 5801738 7047319 625018 4204858 1915348 3379930 5549377 5650192 7150927 7768739 9145265 9964578 3008492 3088635 2720049 981889 8980782 3722371 4290388 7736469 4349338 5221611 1007301 2677905 4007267 6400636 4907995 1867816 2242010 7772026 7903018 559885 4819346 8528035 4764742 9250830 1907966 314120 4901022 1575030 598996 6562424 1539608 3607487 2167196 6775793 7105512 3664115 498164 1395901 3916721 7363638 9133648 4924021 2557680 3140915 3840794 7465675 7524868 6082804 7753838 5427886 9158825 5089321 6472059 3923568 4340152 896162 6753824 1757311 2471191 7352819 8319735 6526935 3476444 3003068 5818865 3098093 6667183 6317028 7010130 583904 6196803 6143779 8024062 1270620 1800831 1864856 1252432 9325698 463797 9006270 7269722 9622622 4095591 3741781 6062327 8435742 4637942 2816151 193054 9625269 2685107 1028926 6152204 6161550 4031993 1971069 9259643 699176 804234 6269773 3799217 9517173 4929689 1823279 787793 9246657 3688134 2040225 8572355 4151931 3562632 8358214 6290690 174360 2099995 2353017 8610102 9254073 7685304 1319293 8879342 370411 4864355 7547683 9048098 1412485 2034889 8307741 4627798 2839122 7093651 8427014 4872432 4539478 250293 5660225 3786135 6454563 216587 4874627 3122631 6295355 3232842 9413320 6469714 7848973 4282474 5079816 7103047 1967778 8915245 5982389 2338189 6295737 6046210 3902424 7708222 8081098 2210165 2336020 3436358 1819953 763034 8308789 8875567 3529463 3969014 2661702 9984025 6701737 7536329 5622794 2997092 3285308 7552251 9466806 1134281 4350863 7062759 8237327 6318640 8494142 6735854 1172966 4789879 2782064 5075389 2498101 3379299 9801690 4834120 6815656 4137781 8113290 5124446 3013348 1642753 1609597 5675050 4142916 8311334 5727516 2281847 3824563 1528961 9834097 5807506 2663241 4184960 2870266 3416706 3019738 3880545 2668697 6708840 8670423 7966897 1784230 3684662 1346196 4102057 1034919 8161852 8239837 9148209 5802435 3769323 3307099 7412031 1960510 7450014 5723365 7688025 9731860 2064066 1733123 2082096 7871571 6912500 8783192 3257974 329206 4319067 7138518 5514039 1027908 8325079 3480936 5328274 2009741 7343269 1946468 5560796 8021258 186306 4709005 3823693 6471765 8016104 1235724 8432274 7982255 9475226 6120299 230254 4055429 369559 2312349 1927000 7282058 3611678 7701111 127402 7930745 7355766 5641440 1474790 5680845 1638514 6803063 206723 1497920 8749530 5767519 9519177 1451973 2992661 5859007 7923737 1008765 7094730 6356011 1507158 9086093 4992447 1737411 3141522 5362005 6565896 7584659 2644064 177574 5285770 2771465 624456 5157673 929042 2099245 3354656 2567555 1418445 3561378 6581611 2684113 1845034 6100788 4136085 7353832 1959795 4575960 878734 1570663 3448108 2385891 656756 956693 4123301 6314415 6318697 689197 6415211 1478898 3382908 1700981 6766499 6523500 6858653 211679 1138883 213309 5295370 2557327 6290824 1876982 7757576 651995 7977769 4409799 521964 2453702 8985758 1400698 4024364 2433866 3786588 7197256 3390558 426027 6027808 2225393 3631360 2443019 6220427 9530404 4143999 5503064 6053905 3518790 5714742 7192787 6248235 1010112
138 79
2887093 23828 8223328 3381000 4433626 8745291 5834701 5935521 2662126 2375202 885524 8964851 9572457 6792219 9390877 5600266 9017611 5538374 8043284 7754175 5068779 4703421 3257239 3638821 738348 1488118 3347745 9502719 2498230 5613995 7074053 7901459 8153959 5297381 3798596 2587585 6558809 9633296 8523105 9220935 4524635 1924767 8185786 4097093 8716985 92801 2213496 250734 5631174 2772917 8004908 3216090 9992474 3778285 6854910 3246959 5266402 202655 5265816 280769 8332787 2339869 8182228 6486746 7637249 1980824 1590469 6712195 4130258 113574 5933130 8654892 4554477 4118916 5268122 3271462 4211716 9997754 3522195 2359028 5286809 4043241 5575117 7795420 7821525 2430028 1042380 3087927 5148819 6308195 3368696 3481606 8648063 4067061 9968352 8801449 8564021 1558821 5513644 2694279 4188531 3962912 3865309 8743008 8081827 1649568 4530607 4809681 1647323 8052802 9684845 9450268 2096043 5259962 7245688 9917567 206127 804205 5521631 7871083 7112399 8890326 1352689 8276599 5473524 1321041 9594185 4037546 5395998 5107830 6731824 2100667 9070741 3113270 843675 9668705 4762838 7890418
432 43
5943220 6679368 892703 555400 4455468 8138390 472967 7177731 8942595 8510735 5048814 8571131 7401061 6401503 9363868 5390723 238681 8958053 9428268 8150816 6582020 8676229 251483 5652761 1789500 3611294 7837604 9068474 1501712 4832127 510909 7444932 4027633 1403611 516469 8483100 2058138 989436 8176968 3516870 9500170 3225783 2088002 9417368 9627285 1451870 4808091 2382103 2926060 6752496 532919 9508080 5428726 3300538 5160841 9734362 6911831 5514582 8802836 8413543 346710 9313744 8374612 6890479 3233492 8891080 7889716 5291629 2396653 6066684 8808499 4412960 9292466 3412638 6346466 1435889 7380644 3670694 6334129 306704 423191 6867047 9814783 8368053 2683723 7491762 8102415 9595553 3006344 6905251 525234 5869190 8735132 1415983 2759669 4484761 2823201 3165522 2292527 7735990 9232206 3617163 2148951 1040810 7029800 1011554 4992836 4410444 7198384 1326965 7233285 7621574 710149 7048068 8505764 3393871 7055967 6608179 2989425 62312 6029567 6030795 8447638 7280836 9962915 3723445 1765597 2786116 6888966 4058124 522106 6121172 191424 5187193 9678119 7221224 8714883 4670955 4147805 5913268 5997919 1381090 6050979 6708067 945296 4556744 101939 8001262 1164923 5607500 579711 7194490 4154432 1543487 6991463 4117347 5266931 1273198 9419599 2155897 7847458 2457843 793207 8038881 161173 471326 5260105 8876056 7658417 1924048 4789324 3656336 3305137 840303 2880540 6766569 7913183 5498615 7283969 9078106 3622252 379817 8788733 7776684 1923303 5780196 4410168 9706370 7053393 6345905 4378405 7416988 8803747 5171611 5455870 8964919 8159073 715975 7840975 5817490 2640022 5146436 1989963 8461296 8502876 4870502 7744002 6416059 369118 5027971 8010302 6507506 7923925 9315172 4284190 9847227 7611506 1210496 2069736 7181036 7556400 6448140 4598025 8876284 1619751 53895 7841203 2294961 3286006 8198316 628588 5926028 5860889 2618550 6903461 4363765 5189 4647463 3295962 2890443 2191572 3822401 9397949 115497 3137574 6198276 2478861 3265217 7408771 7064733 446253 7481308 3512873 5044277 6357592 7648760 7614308 4198796 9943720 900315 4913249 572308 9342479 774138 5706994 6245940 7654040 5712183 3409540 3466139 8602625 8117248 7288539 8000574 748882 2942250 4198851 5743880 8723603 4123759 2808613 9169856 1605068 6321486 6730270 7962659 3970246 4344579 4677592 6430104 5244893 9590840 9518548 7103509 2881116 5225543 5865586 535156 3453863 9275125 6517431 2056488 9908511 6322107 2573200 3173530 1780495 9288187 8917409 504098 3411946 4242160 9673953 7533150 3079783 8920361 5495810 9566165 3264940 2689539 5996269 1025970 4796517 5514818 8129478 7677632 3256498 3995064 728925 6710360 5786326 7246355 1282985 8210974 6084599 3856184 1384505 7865093 3144371 2818051 885329 9072454 7060210 559282 6605604 2656130 1995780 4617551 2222296 5260719 7307090 734702 8802825 2103607 8765656 6932303 2297376 2022154 3443504 5542437 1248651 9229830 2788792 2531636 7440804 1389528 8903956 1341446 1770759 4564465 4159497 2656087 6153056 3735844 5731505 2758660 6391974 7727285 7376211 1130407 2988004 7199438 1865108 4306967 1819182 3146902 1239270 4116557 7685192 7198911 9658993 8933843 6428741 4963922 3981616 6385682 8869586 5401709 7727128 640345 9966173 1886625 3296431 6119229 8138605 9027936 1394027 7046716 6755221 1286375 8177122 2259362 8485812 2558368 6566328 2821131 5705269 321736 9453824 3390461 7520646 9112817 4840441 6465524 6592876 8822056 2851206 7978599 4223766 578334 8618944 6706076

AC output:

Code: Select all

7569184 / 5882487 / 6410068 4803758 / 1651606 528544 5199435 / 5091223 6199923 / 1220462 841672 1764693 6583622 / 6996188 / 8517072 / 8931298 / 3410482 684741 616687 5457537 / 8866815 / 3532222 / 874843 7244092 / 6526517 / 504253 7932159 / 9941819 / 2733645 / 1948779 3214578 2818966 347403 2140783 / 7622723 1999008 / 5185463 5338295 / 9606367 / 1385386 9074894 / 448039 3150079 5658516 / 9960363 / 1667151 7105952 / 5886983 4868029 / 238776 1344520 3734844 3770997 2219363 / 3495074 297515 5239752 1427233 / 2755471 7973397 / 5892148 / 8486185 / 792363 8755687 / 626968 931224 754695 5812430 / 6269518 2877199 / 9713953 / 5344412 / 5841374 2864032 / 3519066 5801738 / 7047319 / 625018 4204858 1915348 3379930 / 5549377 5650192 / 7150927 / 7768739 / 9145265 / 9964578 / 3008492 3088635 2720049 / 981889 8980782 / 3722371 4290388 / 7736469 / 4349338 / 5221611 1007301 2677905 / 4007267 6400636 / 4907995 1867816 / 2242010 7772026 / 7903018 / 559885 4819346 / 8528035 / 4764742 / 9250830 / 1907966 314120 4901022 / 1575030 598996 6562424 / 1539608 3607487 / 2167196 6775793 / 7105512 / 3664115 498164 1395901 / 3916721 7363638 / 9133648 / 4924021 2557680 3140915 / 3840794 7465675 / 7524868 / 6082804 / 7753838 / 5427886 / 9158825 / 5089321 / 6472059 / 3923568 4340152 / 896162 6753824 1757311 / 2471191 7352819 / 8319735 / 6526935 3476444 / 3003068 5818865 / 3098093 6667183 / 6317028 / 7010130 / 583904 6196803 / 6143779 / 8024062 / 1270620 1800831 1864856 / 1252432 9325698 / 463797 9006270 / 7269722 / 9622622 / 4095591 / 3741781 6062327 / 8435742 / 4637942 2816151 / 193054 9625269 / 2685107 1028926 6152204 / 6161550 / 4031993 1971069 / 9259643 699176 / 804234 6269773 3799217 / 9517173 / 4929689 1823279 / 787793 9246657 / 3688134 / 2040225 8572355 / 4151931 3562632 / 8358214 / 6290690 174360 2099995 / 2353017 8610102 / 9254073 / 7685304 / 1319293 8879342 / 370411 4864355 / 7547683 / 9048098 1412485 / 2034889 8307741 / 4627798 / 2839122 7093651 / 8427014 / 4872432 / 4539478 250293 5660225 / 3786135 6454563 / 216587 4874627 3122631 / 6295355 3232842 / 9413320 / 6469714 / 7848973 / 4282474 5079816 / 7103047 / 1967778 8915245 / 5982389 / 2338189 6295737 / 6046210 3902424 / 7708222 / 8081098 / 2210165 2336020 3436358 / 1819953 763034 8308789 / 8875567 / 3529463 3969014 2661702 / 9984025 / 6701737 / 7536329 / 5622794 2997092 / 3285308 7552251 / 9466806 1134281 / 4350863 7062759 / 8237327 / 6318640 / 8494142 / 6735854 / 1172966 4789879 2782064 / 5075389 2498101 3379299 / 9801690 / 4834120 / 6815656 4137781 / 8113290 / 5124446 3013348 1642753 1609597 / 5675050 4142916 / 8311334 / 5727516 / 2281847 3824563 / 1528961 9834097 / 5807506 / 2663241 4184960 2870266 / 3416706 3019738 3880545 / 2668697 6708840 / 8670423 / 7966897 / 1784230 3684662 1346196 4102057 / 1034919 8161852 / 8239837 / 9148209 / 5802435 3769323 / 3307099 7412031 / 1960510 7450014 / 5723365 / 7688025 / 9731860 / 2064066 1733123 / 2082096 7871571 / 6912500 / 8783192 / 3257974 329206 4319067 / 7138518 / 5514039 / 1027908 8325079 / 3480936 5328274 / 2009741 7343269 / 1946468 5560796 / 8021258 / 186306 4709005 / 3823693 6471765 / 8016104 / 1235724 8432274 / 7982255 / 9475226 / 6120299 / 230254 4055429 369559 2312349 / 1927000 7282058 / 3611678 7701111 / 127402 7930745 / 7355766 / 5641440 / 1474790 5680845 / 1638514 6803063 / 206723 1497920 8749530 / 5767519 / 9519177 / 1451973 2992661 5859007 / 7923737 / 1008765 7094730 / 6356011 / 1507158 9086093 / 4992447 / 1737411 3141522 5362005 / 6565896 / 7584659 / 2644064 177574 5285770 2771465 / 624456 5157673 929042 2099245 / 3354656 2567555 1418445 3561378 / 6581611 2684113 1845034 / 6100788 4136085 / 7353832 / 1959795 4575960 / 878734 1570663 3448108 2385891 656756 / 956693 4123301 6314415 / 6318697 689197 / 6415211 1478898 3382908 / 1700981 6766499 / 6523500 / 6858653 / 211679 1138883 213309 5295370 / 2557327 6290824 / 1876982 7757576 / 651995 7977769 / 4409799 521964 2453702 / 8985758 / 1400698 4024364 2433866 / 3786588 7197256 / 3390558 426027 6027808 / 2225393 3631360 / 2443019 6220427 / 9530404 / 4143999 5503064 / 6053905 / 3518790 5714742 / 7192787 / 6248235 1010112
2887093 23828 8223328 / 3381000 4433626 / 8745291 / 5834701 / 5935521 2662126 / 2375202 885524 8964851 / 9572457 / 6792219 / 9390877 / 5600266 / 9017611 / 5538374 / 8043284 / 7754175 / 5068779 4703421 / 3257239 3638821 738348 1488118 3347745 / 9502719 2498230 / 5613995 7074053 / 7901459 / 8153959 / 5297381 3798596 / 2587585 6558809 / 9633296 / 8523105 / 9220935 / 4524635 1924767 / 8185786 4097093 / 8716985 / 92801 2213496 250734 5631174 2772917 / 8004908 3216090 / 9992474 / 3778285 / 6854910 3246959 / 5266402 202655 5265816 / 280769 8332787 / 2339869 8182228 / 6486746 / 7637249 / 1980824 1590469 6712195 / 4130258 113574 5933130 / 8654892 / 4554477 / 4118916 5268122 / 3271462 4211716 / 9997754 / 3522195 2359028 5286809 / 4043241 5575117 / 7795420 / 7821525 / 2430028 1042380 3087927 5148819 / 6308195 3368696 / 3481606 8648063 / 4067061 / 9968352 / 8801449 / 8564021 / 1558821 5513644 / 2694279 4188531 3962912 / 3865309 8743008 / 8081827 / 1649568 4530607 4809681 / 1647323 8052802 / 9684845 / 9450268 2096043 / 5259962 7245688 / 9917567 / 206127 804205 5521631 / 7871083 / 7112399 / 8890326 / 1352689 8276599 / 5473524 / 1321041 9594185 / 4037546 / 5395998 5107830 / 6731824 2100667 / 9070741 3113270 / 843675 9668705 / 4762838 7890418
5943220 6679368 892703 555400 4455468 8138390 472967 7177731 8942595 8510735 / 5048814 8571131 7401061 6401503 9363868 5390723 238681 8958053 / 9428268 8150816 6582020 8676229 251483 5652761 1789500 3611294 7837604 / 9068474 1501712 4832127 510909 7444932 4027633 1403611 516469 8483100 2058138 989436 8176968 3516870 / 9500170 3225783 2088002 9417368 9627285 1451870 4808091 2382103 2926060 6752496 532919 / 9508080 5428726 3300538 5160841 9734362 6911831 5514582 8802836 / 8413543 346710 9313744 8374612 6890479 3233492 8891080 7889716 / 5291629 2396653 6066684 8808499 4412960 9292466 3412638 6346466 1435889 / 7380644 3670694 6334129 306704 423191 6867047 9814783 8368053 2683723 7491762 / 8102415 9595553 3006344 6905251 525234 5869190 8735132 1415983 2759669 4484761 2823201 / 3165522 2292527 7735990 9232206 3617163 2148951 1040810 7029800 1011554 4992836 4410444 7198384 / 1326965 7233285 7621574 710149 7048068 8505764 3393871 7055967 6608179 2989425 / 62312 6029567 6030795 8447638 7280836 9962915 3723445 1765597 2786116 6888966 / 4058124 522106 6121172 191424 5187193 9678119 7221224 8714883 4670955 4147805 / 5913268 5997919 1381090 6050979 6708067 945296 4556744 101939 8001262 1164923 5607500 579711 7194490 / 4154432 1543487 6991463 4117347 5266931 1273198 9419599 2155897 7847458 2457843 793207 8038881 / 161173 471326 5260105 8876056 7658417 1924048 4789324 3656336 3305137 840303 2880540 6766569 / 7913183 5498615 7283969 9078106 3622252 379817 8788733 7776684 / 1923303 5780196 4410168 9706370 7053393 6345905 4378405 7416988 / 8803747 5171611 5455870 8964919 8159073 715975 7840975 5817490 / 2640022 5146436 1989963 8461296 8502876 4870502 7744002 6416059 369118 5027971 / 8010302 6507506 7923925 9315172 4284190 9847227 7611506 / 1210496 2069736 7181036 7556400 6448140 4598025 8876284 1619751 53895 7841203 / 2294961 3286006 8198316 628588 5926028 5860889 2618550 6903461 4363765 5189 4647463 3295962 2890443 / 2191572 3822401 9397949 115497 3137574 6198276 2478861 3265217 7408771 7064733 446253 7481308 / 3512873 5044277 6357592 7648760 7614308 4198796 9943720 900315 4913249 / 572308 9342479 774138 5706994 6245940 7654040 5712183 3409540 3466139 8602625 / 8117248 7288539 8000574 748882 2942250 4198851 5743880 8723603 / 4123759 2808613 9169856 1605068 6321486 6730270 7962659 3970246 4344579 4677592 / 6430104 5244893 9590840 9518548 7103509 2881116 5225543 5865586 535156 / 3453863 9275125 6517431 2056488 9908511 6322107 2573200 3173530 1780495 9288187 / 8917409 504098 3411946 4242160 9673953 7533150 3079783 8920361 / 5495810 9566165 3264940 2689539 5996269 1025970 4796517 5514818 8129478 7677632 / 3256498 3995064 728925 6710360 5786326 7246355 1282985 8210974 6084599 3856184 / 1384505 7865093 3144371 2818051 885329 9072454 7060210 559282 6605604 2656130 1995780 4617551 2222296 / 5260719 7307090 734702 8802825 2103607 8765656 6932303 2297376 2022154 3443504 5542437 / 1248651 9229830 2788792 2531636 7440804 1389528 8903956 1341446 1770759 4564465 4159497 2656087 6153056 / 3735844 5731505 2758660 6391974 7727285 7376211 1130407 2988004 7199438 1865108 4306967 1819182 / 3146902 1239270 4116557 7685192 7198911 9658993 8933843 6428741 4963922 / 3981616 6385682 8869586 5401709 7727128 640345 9966173 1886625 3296431 6119229 / 8138605 9027936 1394027 7046716 6755221 1286375 8177122 2259362 8485812 / 2558368 6566328 2821131 5705269 321736 9453824 3390461 7520646 9112817 4840441 / 6465524 6592876 8822056 2851206 7978599 4223766 578334 8618944 6706076

dhruba07 · Post by **dhruba07** » Mon Jun 16, 2014 5:56 pm

Got AC.

There is a problem just like this in the topcoder tutorial of Binary Search.Interested readers can read it : http://community.topcoder.com/tc?module ... narySearch

keerthi100 · Post by **keerthi100** » Mon Dec 15, 2014 3:43 pm

Hi all,
I get a time limit exceded when I run my code. Can someone please suggest some ways to optimize my code.I had used binary search to get the maximum number of pages. Thanks in advance!

Code: Select all

package s43;

import java.util.LinkedList;
import java.util.Scanner;




public class Main {
	
	static int m,k,left,right,mid;
	static LinkedList<Integer> p;
	
	public static int getsum(int a, int b)
	{
		int sum=0;
		for(int i=a;i<=b;i++)
		{
			sum+=p.get(i);
		}
		return sum;
	}
	
	public static int binarySearch(int left, int right)
	{
		int mid;
		int count=1; int sum=0;
		if(left<right)
		{
		mid=(left+right)/2;
		for(int i=m-1;i>=0;i--)
		{
			if((sum+p.get(i))<=mid)
				sum=sum+p.get(i);
			else
			{
				count++;
				i++;
				sum=0;
				if(count>k)
					break;
				
			}
		}
		
		if(count==k)
		{
			int mid1 = binarySearch(left,mid);
			if(mid1<mid)
				return mid1;
			else
				return mid;
						
			
		}
		else
		{
			if(count<k)
				return binarySearch(left,mid);
			else
				return binarySearch(mid+1,right);
		}
		}
		else
			return left;
				
	}



	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner inp = new Scanner(System.in);
		 p=new LinkedList<Integer>();
	
		int num=inp.nextInt();
		String str="";
		for(int l=0;l<num;l++)
		{
		m = inp.nextInt();
		k = inp.nextInt();
		for(int i=0; i<m; i++)
			p.add(inp.nextInt());
		left=1;  
		right=getsum(0,m-1);
		int maxi = binarySearch(left,right);
		LinkedList<String> finl = new LinkedList<String>();
		
		int sum=0;int count=1;
		for(int i=m-1;i>=0;i--)
		{
			if((sum+p.get(i))<=maxi)
			{
				sum=sum+p.get(i);
				finl.add(Integer.toString(p.get(i)));
			}
			else
			{
				count++;
				i++;
				sum=0;
				if(count>k)
					break;
				finl.add("/");
			}
		}
		
		if(count==k)
		{
		 for(int i=(finl.size()-1); i>=0; i--)
		 {
			str+=(finl.get(i) + " ");
		 }
		 str+="\n";
		 finl.clear();
		}
		else
		{
			finl.clear();
			sum=0;count=1;
			for(int j=m-1;j>=0;j--)
			{
				if((sum+p.get(j))<=maxi)
				{
					sum=sum+p.get(j);
					finl.add(Integer.toString(p.get(j)));
				}
				else
				{
					count++;
					
					sum=0;
					finl.add("/");
					k--;
					m=j+1;
					maxi=binarySearch(1,getsum(0,j));
					int pi=getsum(0,j);
					int si=k;
					j++;
					}
			}
			 for(int i=(finl.size()-1); i>=0; i--)
			 {
				 str+=(finl.get(i) + " ");
			 }
			 str+=("\n");
			 finl.clear();
			
		}
		
		
	finl.clear();
	p.clear();

	}
		System.out.println(str);
	}

}

brianfry713 · Post by **brianfry713** » Mon Dec 15, 2014 10:36 pm

Don't use a package.
Try using BufferedReader and BufferedWriter.

dibery · Post by **dibery** » Tue May 26, 2015 6:39 pm

Just found one bug in my code.
If you solve this problem using DP technique, you have to pay attention to data type.
There may be 5,000,000,000 pages at most, which exceeds INT_MAX.
(Therefore, initializing to INT_MAX is not big enough.)

OJ Board

714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Q714：Copying Books

Re: Q714：Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books

Re: 714 - Copying Books