11057 - Exact Sum

[richatibrewal]

Hii, i m not getting the output for this code. Plz help me with the solution:

Code: Select all

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
int arr[10001];
int a=0,b=0,d=INT_MAX,n,m;
int used[10001];
void bs(int f,int l)
{
    int i=f,j=l-1,sum,mid;
    sum=m-arr[l];
        while(i<=j)
        {

            mid=(i+j)/2;
            if(arr[mid]>sum)
                j=mid-1;
            else if(arr[mid]<sum)
                i=mid+1;
            else break;
        }
    if(!used[mid])
    {
        used[mid]=1;
        if(i<=j)
        {

            if((arr[l]-arr[mid])==0)
            {
                a=arr[mid];
                b=arr[l];
                return ;
            }
            if(d>(arr[l]-arr[mid]))
            {
                d=arr[l]-arr[mid];
                a=arr[mid];
                b=arr[l];
            }
            bs(f+1,l-1);
        }
        else
            bs(f,l-1);
    }
}
int main()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&arr[i]);
        scanf("%d",&m);
       sort(arr,arr+n);
        memset(used,0,sizeof(used));
        bs(0,n-1);
        printf("Peter should buy books whose prices are %d and %d.\n\n",a,b);
    }
    return 0;
}

[lighted]

Code: Select all

Use code tags. Like this. It is difficult to read your code.

Hii, i m not getting the output for this code. Plz help me with the solution:}

I don't understand your question.

It is safe to read input this way

Code: Select all

while(scanf("%d",&n) == 1)

You are not initializing variables after first case. Add lines

Code: Select all

a = b = 0;
d = INT_MAX;

bs(0,n-1);

Input:

Code: Select all

2
40 40
80

5
10 2 6 8 4
10

4
4 6 2 8
10

3
1000000 100000 1
1100000

AC output:

Code: Select all

Peter should buy books whose prices are 40 and 40.

Peter should buy books whose prices are 4 and 6.

Peter should buy books whose prices are 4 and 6.

Peter should buy books whose prices are 100000 and 1000000.

Here is your updated code for input above. It fails second test case. http://ideone.com/V3DjHt

[lobato]

Why do I get Wrong Answer, I have already compared my output to all the outputs in the board saving them on a text file and using the Diff command in terminal to verify my output and the board output. It was always the same

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <math.h>
#include <limits.h>

struct mon{
	long int i, j, val;
};
int compare(const void *a, const void *b) {
	return *((long int*)a) - *((long int*)b);
}

int binary(long int *arr,long int size, long int key) {
	long int mid,i,j;
	i = 0;
	j = size;
	while( i <= j) {
		mid = (i+j)/2;
		if( arr[mid] == key ) return mid;
		if( key > arr[mid-1] ) return mid+1;
		if( arr[mid] < key ) i = mid+1;
		if( arr[mid] > key ) j = mid;	
	}
	return -1;
}


struct mon* find_min_sum(long int *arr, long int i , long int j, long int sum, long int tot) {
	long int k,z, size = j+1;
	struct mon *min = (struct mon*)malloc(sizeof(struct mon));
	min->i = -1;
	min->j = -1;
	min->val = INT_MAX;
	for( k = i ; k < size ; k++){
		for( z = size - 1  ; z > k ; z-- ){
			if( arr[k] + arr[z] == sum ) {
				if(  arr[z] - arr[k] < min->val ) {
					min->val = arr[z] - arr[k];
					min->i = z;
					min->j = k; 
				}
			}
		}
	}

	if( min->i  == -1 ) {
		min->i = i;
		min->j = tot-1;
		return min;

	}else {
		return min;
	}
	
}



int main(int argc, char *argv[]) {
	
	long int N,Q,i,j;

	while( scanf("%li", &N) != EOF ) {
		long int *precios = (long int*) malloc(sizeof(long int)*N);

		for( i = 0 ; i < N ; i++){ 
			scanf("%li", &precios[i]);
		}
		scanf("%li", &Q);
		qsort(precios,N,sizeof(long int),compare);
	
		i = 0;
		j = binary(precios,N,Q);
		struct mon *min = find_min_sum(precios,i,j,Q,N);
		if( min->i > min->j ) {
			long int temp = min->j;
			min->j = min->i;
			min->i = temp;
		}

		printf("Peter should buy books whose prices are %li and %li.\n\n", precios[min->i], precios[min->j] );
		free(min);
	}

	return 0;
}

[brianfry713]

Input:

Code: Select all

2
278 721
999

4
184 609 668 768
793

3
209 72 156
281

10
191 384 120 485 80 517 84 553 125 146
575

14
287 592 207 422 779 369 436 280 38 827 55 703 330 184
879

3
120 755 652
875

13
127 346 373 463 162 419 95 471 137 230 285 442 230
473

2
63 354
417

6
23 23 37 7 2 40
46

14
526 213 690 234 604 330 317 421 228 337 505 300 540 222
739

5
489 395 776 185 260
884

6
530 243 270 323 196 755
773

3
30 950 66
980

9
111 30 59 22 115 2 22 61 23
141

19
410 475 37 842 812 184 526 493 239 75 186 551 410 133 742 746 626 818 254
885

18
70 206 91 249 76 240 212 179 24 184 148 43 37 29 226 96 239 272
276

16
246 407 46 223 389 251 523 571 411 390 347 333 333 104 129 77
653

18
298 317 205 530 176 482 243 125 75 543 428 143 542 29 345 465 184 323
615

6
5 80 75 50 62 40
85

13
3 26 26 11 29 14 29 11 28 9 14 3 9
29

2
143 99
242

10
348 226 22 529 493 221 137 302 364 18
574

17
2 7 5 7 4 8 1 5 1 3 5 4 4 6 1 6 3
9

3
90 1 81
91

13
38 22 52 36 15 47 49 46 42 16 27 21 3
60

16
103 219 141 205 4 269 152 83 212 248 239 142 57 74 277 142
322

10
664 151 405 156 90 662 769 505 545 131
815

5
58 23 22 41 38
81

7
315 335 581 24 147 164 460
650

5
126 12 107 72 96
138

11
644 62 199 703 412 129 551 604 283 570 573
706

19
266 553 317 257 28 105 394 218 494 540 344 797 349 306 679 477 15 37 525
819

16
169 244 142 119 213 252 389 256 248 173 65 133 129 79 173 184
413

20
34 250 50 66 43 101 173 214 9 196 216 62 12 198 137 244 212 161 63 2
284

15
223 134 183 326 62 25 47 8 269 122 156 353 81 87 232
357

19
591 12 17 341 280 376 218 91 554 51 400 404 578 10 514 347 184 600 108
603

21
156 252 242 53 218 346 22 323 280 125 261 233 13 254 226 364 325 233 64 371 344
408

12
758 69 145 570 359 193 621 184 315 473 673 290
827

17
232 429 117 411 16 631 49 625 174 365 366 5 583 515 417 511 90
661

2
15 57
72

8
71 118 89 54 38 165 116 115
189

10
146 346 376 211 47 366 459 220 324 159
492

8
190 71 217 109 205 68 8 105
261

11
394 163 309 259 2 404 531 24 278 178 149
557

20
490 19 25 250 452 171 419 503 192 165 254 445 76 480 207 408 235 279 209 474
509

2
857 23
880

21
480 433 517 290 87 635 124 363 899 663 356 287 663 119 814 492 775 776 884 437 295
913

6
305 302 605 10 304 231
607

14
39 760 294 306 619 152 559 665 403 402 231 528 439 615
799

5
492 374 281 561 794
866

8
547 27 235 562 420 158 25 507
574

2
45 25
70

13
1 13 10 3 2 9 5 10 11 7 12 4 5
14

10
853 20 155 466 761 627 122 390 183 394
873

13
479 102 479 9 114 50 131 32 143 54 538 486 394
581

15
67 93 58 4 2 38 68 150 72 38 37 158 32 107 133
160

19
5 6 11 7 4 1 2 11 4 9 11 8 9 11 8 11 6 1 8
11

13
480 296 345 30 456 150 451 447 344 503 280 57 79
776

9
838 92 876 360 567 601 575 686 803
930

6
375 63 412 301 32 95
438

7
492 253 558 659 69 629 408
745

2
142 745
887

2
12 491
503

21
116 668 144 270 85 782 122 526 782 163 162 95 22 744 120 472 769 624 556 355 588
784

15
832 10 355 51 450 151 686 615 454 114 249 437 234 792 148
842

10
275 581 771 105 526 241 288 677 16 25
856

21
513 91 316 137 475 386 343 433 145 193 353 467 162 202 304 299 305 197 116 238 259
604

16
103 538 593 369 348 577 366 546 78 372 282 348 591 276 622 126
641

13
276 457 60 53 328 81 12 605 77 239 613 415 247
733

11
17 110 41 92 87 127 44 60 127 40 9
127

12
425 16 215 360 74 125 142 75 209 143 426 73
441

20
97 689 685 689 508 70 750 608 467 627 324 681 675 580 171 673 82 388 726 750
786

5
216 129 247 149 208
345

18
22 44 29 25 63 41 26 19 8 21 11 45 29 13 60 14 64 61
66

13
42 89 29 46 45 90 29 33 48 54 89 81 55
131

15
270 12 67 243 120 41 86 158 249 182 199 206 275 246 225
282

4
35 31 54 46
66

13
39 179 109 100 87 118 159 43 24 191 162 140 25
218

5
821 115 586 744 24
936

10
49 40 87 88 31 52 4 33 81 31
89

10
147 366 143 251 460 486 133 255 180 430
513

10
334 16 3 135 110 192 174 345 30 314
350

2
106 142
248

6
110 118 158 118 225 94
228

6
467 78 153 20 494 76
545

15
29 130 86 105 147 42 70 56 49 49 98 110 92 40 146
159

17
13 475 222 149 399 131 70 247 210 104 297 416 450 119 277 183 141
488

8
177 688 713 240 439 747 42 35
865

2
238 264
502

9
152 225 202 298 169 3 1 272 367
377

6
395 319 682 518 685 84
714

18
759 102 310 177 362 165 697 486 104 225 399 144 182 511 165 651 67 459
861

15
194 375 49 287 38 207 422 82 165 7 404 544 257 555 188
569

14
157 181 17 333 132 97 153 210 20 328 253 48 327 49
338

14
252 515 313 558 132 709 761 351 37 225 71 153 165 245
767

6
80 104 69 87 124 55
184

15
630 191 287 485 524 347 161 512 614 445 345 170 358 233 277
821

20
22 138 57 138 137 107 71 61 2 20 25 80 31 127 113 90 148 136 54 69
160

7
180 125 95 161 60 207 235
305

5
138 24 32 73 33
162

AC output:

Code: Select all

Peter should buy books whose prices are 278 and 721.

Peter should buy books whose prices are 184 and 609.

Peter should buy books whose prices are 72 and 209.

Peter should buy books whose prices are 191 and 384.

Peter should buy books whose prices are 287 and 592.

Peter should buy books whose prices are 120 and 755.

Peter should buy books whose prices are 127 and 346.

Peter should buy books whose prices are 63 and 354.

Peter should buy books whose prices are 23 and 23.

Peter should buy books whose prices are 234 and 505.

Peter should buy books whose prices are 395 and 489.

Peter should buy books whose prices are 243 and 530.

Peter should buy books whose prices are 30 and 950.

Peter should buy books whose prices are 30 and 111.

Peter should buy books whose prices are 410 and 475.

Peter should buy books whose prices are 70 and 206.

Peter should buy books whose prices are 246 and 407.

Peter should buy books whose prices are 298 and 317.

Peter should buy books whose prices are 5 and 80.

Peter should buy books whose prices are 3 and 26.

Peter should buy books whose prices are 99 and 143.

Peter should buy books whose prices are 226 and 348.

Peter should buy books whose prices are 4 and 5.

Peter should buy books whose prices are 1 and 90.

Peter should buy books whose prices are 22 and 38.

Peter should buy books whose prices are 103 and 219.

Peter should buy books whose prices are 151 and 664.

Peter should buy books whose prices are 23 and 58.

Peter should buy books whose prices are 315 and 335.

Peter should buy books whose prices are 12 and 126.

Peter should buy books whose prices are 62 and 644.

Peter should buy books whose prices are 266 and 553.

Peter should buy books whose prices are 169 and 244.

Peter should buy books whose prices are 34 and 250.

Peter should buy books whose prices are 134 and 223.

Peter should buy books whose prices are 12 and 591.

Peter should buy books whose prices are 156 and 252.

Peter should buy books whose prices are 69 and 758.

Peter should buy books whose prices are 232 and 429.

Peter should buy books whose prices are 15 and 57.

Peter should buy books whose prices are 71 and 118.

Peter should buy books whose prices are 146 and 346.

Peter should buy books whose prices are 71 and 190.

Peter should buy books whose prices are 163 and 394.

Peter should buy books whose prices are 19 and 490.

Peter should buy books whose prices are 23 and 857.

Peter should buy books whose prices are 433 and 480.

Peter should buy books whose prices are 302 and 305.

Peter should buy books whose prices are 39 and 760.

Peter should buy books whose prices are 374 and 492.

Peter should buy books whose prices are 27 and 547.

Peter should buy books whose prices are 25 and 45.

Peter should buy books whose prices are 5 and 9.

Peter should buy books whose prices are 20 and 853.

Peter should buy books whose prices are 102 and 479.

Peter should buy books whose prices are 67 and 93.

Peter should buy books whose prices are 5 and 6.

Peter should buy books whose prices are 296 and 480.

Peter should buy books whose prices are 92 and 838.

Peter should buy books whose prices are 63 and 375.

Peter should buy books whose prices are 253 and 492.

Peter should buy books whose prices are 142 and 745.

Peter should buy books whose prices are 12 and 491.

Peter should buy books whose prices are 116 and 668.

Peter should buy books whose prices are 10 and 832.

Peter should buy books whose prices are 275 and 581.

Peter should buy books whose prices are 299 and 305.

Peter should buy books whose prices are 103 and 538.

Peter should buy books whose prices are 276 and 457.

Peter should buy books whose prices are 40 and 87.

Peter should buy books whose prices are 16 and 425.

Peter should buy books whose prices are 97 and 689.

Peter should buy books whose prices are 129 and 216.

Peter should buy books whose prices are 25 and 41.

Peter should buy books whose prices are 42 and 89.

Peter should buy books whose prices are 12 and 270.

Peter should buy books whose prices are 31 and 35.

Peter should buy books whose prices are 100 and 118.

Peter should buy books whose prices are 115 and 821.

Peter should buy books whose prices are 40 and 49.

Peter should buy books whose prices are 147 and 366.

Peter should buy books whose prices are 16 and 334.

Peter should buy books whose prices are 106 and 142.

Peter should buy books whose prices are 110 and 118.

Peter should buy books whose prices are 78 and 467.

Peter should buy books whose prices are 49 and 110.

Peter should buy books whose prices are 13 and 475.

Peter should buy books whose prices are 177 and 688.

Peter should buy books whose prices are 238 and 264.

Peter should buy books whose prices are 152 and 225.

Peter should buy books whose prices are 319 and 395.

Peter should buy books whose prices are 102 and 759.

Peter should buy books whose prices are 194 and 375.

Peter should buy books whose prices are 157 and 181.

Peter should buy books whose prices are 252 and 515.

Peter should buy books whose prices are 80 and 104.

Peter should buy books whose prices are 191 and 630.

Peter should buy books whose prices are 22 and 138.

Peter should buy books whose prices are 125 and 180.

Peter should buy books whose prices are 24 and 138.

[ehsanulbigboss]

AC! Thanks!

[lighted]

Try to check input in this thread before posting.

After each test case you must print a blank line.

Try this

Code: Select all

5
1 2 3 4 5
3

got wa :\ i was expecting TLE..

It seems that judges input are weak. I changed two lines in your code and got accepted but it was wrong solution.
With current judge's input - solutions with O(N * N) is accepted. My solution is in O(N * logN)