11269 - Setting Problems

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Fri Sep 07, 2007 4:31 am

Can anyone give me some test cases?
I use Johnson, but it got WA.

Here is my code:

Code: Select all

#include <iostream>

//#include <conio.h>

using namespace std;

#define FIN "" //"11269.in"
#define FOUT "" //"11269.out"

int n, s[25], g[25], lich[25], dau, cuoi;
int main()
{
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    
    while (1)
    {
        cin >> n;
        
        if (cin.eof()) break;
        
        for (int i=0; i<n; i++)
            cin >> s[i];
        for (int i=0; i<n; i++)
            cin >> g[i];
        
        
        for (int i=0; i<n-1; i++)
            for (int j=i; j<n; j++)
                if (min(s[i], g[i]) > min (s[j], g[j]))
                {
                    int t;
                    t=s[i]; s[i]=s[j]; s[j]=t;
                    t=g[i]; g[i]=g[j]; g[j]=t;
                    //swap(s[i], s[j]);
                    //swap(g[i], g[j]);
                }
                
        //for (int i=0; i<n; i++)
            //cout << s[i] << " " << g[i] << endl;
            
        dau=0;
        cuoi=n-1;
        for (int i=0; i<n; i++)
            if (min(s[i], g[i])==s[i])
            {
                lich[dau]=i;
                dau++;
            }
            else
            {
                lich[cuoi]=i;
                cuoi--;
            }
            
        //for (int i=0; i<n; i++)
            //cout << s[lich[i]] << " " << g[lich[i]] << endl;
            
        int tg1=0, tg2=0;
        
        for (int i=0; i<n; i++)
        {
                tg1+=s[lich[i]];
                tg2=max(tg2, tg1) + g[lich[i]];
        }
        
        
        
        cout << tg2 << endl;
            
    }
    
    fclose(stdin);
    fclose(stdout);
    
    //getch();
    
    return 0;
}

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am

Post by goodwill » Fri Sep 07, 2007 5:45 am

Actually, there are some way to implement Johnson's algorithm.
I used the following :

Code: Select all

1. Make 2 list : A={i|s[i]<=g[i]},B={i|s[i]>g[i]}
2. Sort A increasingly by s. Sort B decreasingly by g
3. Merge A and B

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Sat Sep 08, 2007 7:16 am

Some test cases please, I cannot find what is wrong with my solution!

My implementation:
Sort tasks accroding to min(s, g)
for i=0 -> n-1
if (min(s, g = s)
add task i to the end of list A
else
add task i to begin of list B
merge A B

Thank you!

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sat Sep 08, 2007 9:22 am

Code: Select all

10
5 7 63 1 48 2 9 5 7 10
5 2 7 4 1 3 6 4 8 2
20
5 3 9 7 1 6 8 4 2 3 6 5 4 7 1 2 3 6 8 7
6 4 2 9 8 7 3 1 4 7 2 5 6 5 7 1 3 5 7 4

Code: Select all

158
98
Hope it helps

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Sat Sep 08, 2007 4:30 pm

My above program outputs it correctly :(

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sat Sep 08, 2007 6:25 pm

ok.. Let's try again :)

Code: Select all

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

Code: Select all

105
106

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am

Post by goodwill » Sun Sep 09, 2007 5:31 am

I think your program is OK.
May be it got WA because of your loop condition.
Try this :
while (cin>>n)

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Sun Sep 09, 2007 11:45 am

Still correct and still got WA :-(
I tried while (cin >> n) also

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Sun Sep 09, 2007 12:18 pm

Ohh... i changed it to pascal
and when changing
while not eof
to
while not seekeof
it got accept
What's equivalent in C++?
Can someone explain me why?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Sep 09, 2007 1:02 pm

paulmcvn wrote: while not seekeof
So seekeof is allowed in new judge? That's great~

Seekeof skips spaces. Eof doesn't. It was a "Restricted Function" in old judge.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11269 - Setting Problems

Post by Jehad Uddin » Fri Sep 25, 2009 4:47 am

Hello everyone,i m getting wa in this problem,i used greedy approach,i have tested all the I/O s from the board and it seems ok;

Code: Select all

#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;

struct ary
{
 int sultan,golapi;
 double rate;
};

ary array[40];


int mn(int a,int b,int c,int d)
{
 int x,y;
 if(a<b) x=a; 
 else x=b;
 if(c<d) y=c; 
 else y=d;
 if(x<y) return x; else return y;
}

int cmp(const void *a,const void *b)
{
 ary *x=(ary *)a;
 ary *y=(ary *)b;
 
  if(mn(x->sultan,y->sultan,x->golapi,y->golapi)==x->golapi) return 1;
  else if(mn(x->sultan,y->sultan,x->golapi,y->golapi)==y->golapi) return -1;
  else if(mn(x->sultan,y->sultan,x->golapi,y->golapi)==x->sultan) return -1;
  else if(mn(x->sultan,y->sultan,x->golapi,y->golapi)==y->sultan) return 1;
 
 
 
 return 0;

} 



int main()
{
  
 int n,i,j,k,t1,t2,t3;
 while(cin>>n)
 {
  for(i=0;i<n;i++)
  
   cin>>array[i].sultan;
   
  for(i=0;i<n;i++)
  
   cin>>array[i].golapi;
   for(i=0;i<n;i++)
   
   array[i].rate=double(array[i].sultan)/double(array[i].golapi);
   
  
  
  qsort(array,n,sizeof(ary),cmp);
 
  
  
  
  t1=0;
  t2=0;
  for(i=0;i<n;i++)
  {
   t1+=array[i].sultan;
   
   if(i!=n-1) t2+=array[i].golapi;
   
  }
  
  t3=t1-array[0].sultan;
  
  if(t2-t3>0) t1+=t2-t3;
  t1+=array[n-1].golapi;
  cout<<t1<<endl;
 }

 return 0;
}
pls help,

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 11269 - Setting Problems

Post by anacharsis » Sat Aug 22, 2015 3:57 am

Some IO

In:

Code: Select all

20
283 341 34 47 398 313 402 482 262 304 208 138 372 459 149 25 250 28 43 453 
154 397 70 59 309 14 234 162 200 278 411 346 382 373 285 185 304 136 290 272 
20
450 218 5 259 404 227 404 262 173 205 330 343 419 310 175 121 200 109 249 240 
154 165 6 308 127 187 236 349 379 292 285 52 46 426 475 327 221 10 47 94 
20
429 376 463 238 473 399 134 312 438 415 269 479 292 251 355 104 255 477 185 271 
7 366 372 362 106 196 136 274 41 170 111 186 371 190 416 84 257 119 250 19 
20
118 122 289 91 199 319 475 377 306 192 299 70 489 197 75 76 126 60 152 212 
343 261 136 417 133 131 120 266 101 102 236 371 395 56 100 264 18 198 189 100 
20
152 320 178 308 281 221 105 307 494 338 497 209 312 206 5 92 108 275 335 417 
21 76 459 412 354 446 488 434 433 62 290 76 341 497 90 308 309 371 323 313 
20
314 201 301 145 59 410 303 287 328 430 105 23 476 314 233 393 476 464 104 421 
341 398 74 74 117 318 499 154 395 377 280 190 150 43 90 28 45 352 310 461 
20
492 463 382 341 270 467 132 6 323 414 17 381 113 238 189 241 180 196 141 86 
355 61 265 185 29 234 330 482 113 52 185 154 58 107 35 160 272 431 488 84 
20
72 239 13 102 130 203 378 57 382 159 281 272 136 467 446 355 333 154 364 399 
243 170 53 279 469 42 134 366 57 266 486 203 315 288 318 264 31 168 221 424 
20
70 491 310 92 434 409 275 403 292 445 240 135 196 270 289 388 188 307 405 109 
22 365 78 30 296 361 302 211 293 101 384 44 462 168 491 426 82 297 195 366 
20
59 489 350 498 187 241 435 496 193 368 175 223 286 491 192 337 442 86 335 428 
431 243 97 481 252 485 291 326 323 179 111 443 351 363 395 76 13 62 365 199 
20
298 75 488 198 457 180 71 369 107 42 400 469 65 177 413 456 425 95 491 376 
158 153 454 415 250 423 310 321 185 322 271 254 208 45 293 201 168 85 464 410 
20
362 419 57 359 428 211 283 184 41 306 456 252 186 13 253 262 201 301 186 270 
480 451 106 429 195 342 68 495 358 105 406 207 262 359 47 386 267 257 408 494 
20
369 13 183 98 499 450 284 107 492 245 81 221 144 395 334 487 295 53 123 182 
259 388 94 301 445 251 452 214 250 152 320 486 51 490 490 474 186 140 183 478 
20
39 162 334 91 372 350 55 389 396 252 216 305 404 138 112 263 117 278 382 100 
470 326 178 22 63 43 99 9 30 452 309 40 161 65 166 337 465 342 176 418 
20
26 177 21 303 297 496 24 82 363 362 392 162 187 494 451 157 207 165 253 417 
176 361 127 325 456 310 487 345 441 181 162 379 53 361 445 74 405 241 249 309 
20
399 469 38 374 432 165 307 53 350 456 284 247 191 159 428 364 159 496 46 456 
472 130 384 275 177 419 496 169 56 110 395 205 49 280 116 194 297 405 57 379 
20
336 223 500 119 279 18 73 449 161 405 28 247 445 122 31 3 17 45 215 272 
26 413 208 145 449 39 86 15 230 437 330 50 256 488 294 394 153 143 222 293 
20
260 91 244 476 332 47 195 27 367 313 88 386 364 420 398 82 103 273 425 182 
480 281 17 498 352 421 405 446 312 369 342 40 258 391 466 25 26 307 403 214 
20
37 376 149 173 406 354 74 156 351 40 363 93 379 394 360 237 234 155 460 317 
21 464 98 341 120 396 18 84 74 273 369 64 148 46 33 496 83 432 459 357 
20
224 254 22 478 125 75 321 500 131 77 61 353 191 377 274 361 142 64 157 79 
476 342 458 246 293 298 332 7 35 184 154 16 496 420 149 380 285 344 436 78 
20
435 353 215 155 166 331 465 195 156 405 41 192 365 197 217 263 266 58 170 442 
142 468 299 311 445 389 384 442 500 197 138 384 270 353 390 328 175 406 272 496 
20
346 384 220 497 148 478 348 192 232 328 347 417 362 259 165 371 61 55 55 2 
240 439 291 113 124 350 31 162 309 486 351 235 428 453 184 57 170 141 416 197 
20
215 437 80 176 204 22 153 47 386 240 370 402 113 377 223 422 333 160 300 75 
193 192 466 357 166 460 347 447 278 299 8 465 263 16 491 487 150 124 31 419 
20
77 173 382 248 6 151 209 114 93 155 67 454 270 103 104 33 435 84 405 365 
297 323 5 17 439 135 314 194 315 289 206 332 366 398 30 379 391 294 102 399 
20
232 190 79 482 76 303 185 252 33 442 284 370 278 337 219 488 81 68 488 474 
144 113 3 362 85 118 89 451 64 293 465 337 285 126 436 469 188 289 242 398 
20
30 70 261 498 377 493 377 491 307 152 209 429 356 193 230 408 134 39 477 163 
458 444 4 189 150 131 234 390 301 455 191 330 264 484 105 341 439 468 148 189 
20
427 71 137 208 123 464 230 219 85 43 70 317 405 131 180 115 389 281 173 400 
192 155 224 48 389 416 331 142 443 129 248 359 483 169 497 51 58 394 396 2 
20
6 443 322 256 252 267 320 346 360 167 394 65 196 277 384 61 458 13 486 383 
198 352 328 312 385 253 447 154 168 296 404 98 68 495 350 436 283 159 414 374 
20
341 79 88 384 386 95 376 77 303 236 344 63 323 250 265 453 487 256 181 486 
478 433 1 110 9 222 479 233 415 427 263 184 449 391 434 261 357 3 352 159 
20
368 105 49 418 106 174 227 345 278 426 402 137 411 453 448 283 239 397 136 283 
123 199 46 260 388 439 442 399 157 341 79 60 421 496 131 4 356 468 325 469 
20
74 335 30 500 452 468 432 393 460 256 365 154 331 116 356 45 482 105 55 160 
87 179 294 347 30 436 4 249 180 181 456 192 387 326 233 424 364 255 195 86 
20
110 147 186 50 476 205 13 476 419 115 482 435 434 451 229 80 363 358 374 281 
207 3 483 115 85 5 183 487 427 249 330 277 78 414 239 51 105 67 453 260 
20
199 471 29 112 434 416 471 433 251 442 27 372 196 360 56 38 463 234 253 19 
494 218 304 352 268 28 145 33 431 428 343 230 53 87 458 7 464 346 205 483 
20
488 8 286 306 459 296 357 60 351 438 118 322 356 378 435 123 480 50 370 272 
121 418 363 441 35 95 451 196 103 474 134 277 420 428 323 307 305 65 286 193 
20
31 172 153 238 137 130 152 243 38 428 372 80 452 97 475 106 147 145 106 315 
248 83 287 460 40 361 134 59 141 289 208 254 405 478 464 433 146 201 163 264 
20
434 294 258 33 495 259 497 364 315 131 166 132 370 493 448 75 373 12 80 323 
120 47 439 379 171 170 162 417 343 243 187 17 367 284 412 8 462 58 326 480 
20
301 374 55 327 346 449 117 424 93 321 500 85 461 36 471 59 174 357 264 428 
230 449 129 83 63 149 418 439 50 77 461 489 242 302 342 432 171 397 209 299 
20
265 416 301 182 336 166 343 303 495 135 20 460 458 322 84 429 221 266 204 19 
362 40 375 272 298 411 441 351 189 471 229 85 49 464 217 138 154 43 120 278 
20
312 175 16 192 340 302 253 288 40 27 283 116 206 216 432 317 361 232 218 373 
433 359 328 269 173 470 291 418 254 250 109 61 70 179 458 75 298 65 132 499 
20
289 107 413 447 379 212 111 75 87 486 472 464 102 283 135 336 284 470 16 8 
229 500 203 127 212 385 236 427 104 64 460 259 352 288 12 6 485 152 25 82 
20
76 389 211 173 101 321 434 158 48 340 14 29 282 424 462 301 496 374 205 351 
412 38 211 371 358 56 75 403 171 412 238 43 488 33 275 292 493 212 148 118 
20
12 484 430 190 213 114 246 38 225 149 298 191 293 140 254 348 377 300 14 116 
253 181 489 86 138 238 336 498 290 85 235 293 327 97 49 489 463 142 458 335 
20
118 456 233 314 128 304 352 421 338 80 46 490 143 206 203 350 404 31 399 177 
457 210 172 66 298 256 118 476 408 49 211 395 289 209 364 110 243 440 447 459 
20
228 247 137 450 166 111 12 267 492 265 434 458 321 413 330 429 414 377 73 81 
270 458 488 387 128 145 345 278 86 31 396 237 217 351 121 374 178 269 471 287 
20
412 48 463 370 183 326 407 148 165 408 2 418 455 89 26 219 25 304 294 130 
131 38 2 60 288 422 160 124 242 387 477 63 234 52 417 439 126 443 159 436 
20
76 133 102 357 159 119 473 382 398 137 250 482 109 63 22 144 364 309 420 279 
386 173 77 154 183 468 448 131 138 418 464 7 111 375 95 276 33 454 20 280 
20
84 66 405 166 273 488 496 496 303 243 164 378 118 251 97 341 279 122 76 424 
288 410 492 241 494 147 331 414 73 453 244 162 111 193 211 262 173 144 435 116 
20
95 342 129 27 191 6 338 39 102 448 226 344 447 380 396 258 205 197 136 362 
392 493 417 56 83 175 309 322 113 68 136 25 421 248 197 312 457 85 307 45 
20
408 298 452 349 424 382 491 284 332 372 464 374 85 108 414 401 68 247 206 462 
492 55 15 279 62 62 293 311 27 220 118 418 477 466 60 493 346 398 394 202 
20
174 106 387 277 316 264 153 369 221 315 497 74 402 421 195 109 120 264 114 75 
25 60 260 104 52 270 261 50 158 72 233 198 165 381 83 434 370 352 323 50 
AC out:

Code: Select all

5005
5113
6622
4262
6110
5815
5101
4973
5770
6324
5697
6135
6117
4764
5908
5922
4674
6080
5126
5451
6830
5298
5681
5231
5374
5745
5169
5980
5723
5708
5573
5687
5396
5988
5149
5560
5692
5465
5207
5182
5222
5494
5708
5736
4894
4785
5460
4693
6636
4878

Post Reply

Return to “Volume 112 (11200-11299)”