10535 - Shooter

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

Moderator: Board moderators

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

right.

Post by sohel » Sun Nov 21, 2004 4:21 pm

My AC program also produces 4.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue Nov 23, 2004 5:58 pm

Can anybody check this input/output?
i always got WA and i do'nt know why?
input:
  • 42
    8467 6334 6500 9169
    5724 1478 9358 6962
    4464 5705 8145 3281
    6827 9961 491 2995
    1942 4827 5436 2391
    4604 3902 153 292
    2382 7421 8716 9718
    9895 5447 1726 4771
    1538 1869 9912 5667
    6299 7035 9894 8703
    3811 1322 333 7673
    4664 5141 7711 8253
    6868 5547 7644 2662
    2757 37 2859 8723
    9741 7529 778 2316
    3035 2190 1842 288
    106 9040 8942 9264
    2648 7446 3805 5890
    6729 4370 5350 5006
    1101 4393 3548 9629
    2623 4084 9954 8756
    1840 4966 7376 3931
    6308 6944 2439 4626
    1323 5537 1538 6118
    2082 2929 6541 4833
    1115 4639 9658 2704
    9930 3977 2306 1673
    2386 5021 8745 6924
    9072 6270 5829 6777
    5573 5097 6512 3986
    3290 9161 8636 2355
    4767 3655 5574 4031
    2052 7350 1150 6941
    1724 3966 3430 1107
    191 8007 1337 5457
    2287 7753 383 4945
    8909 2209 9758 4221
    8588 6422 4946 7506
    3030 6413 9168 900
    2591 8762 1655 7410
    6359 7624 537 1548
    6483 7595 4041 3602
    -1 -1

    1
    291 836 9374 1020
    -1 -1

    47
    4021 7348 3199 9668
    4484 8281 4734 53
    1999 6418 7938 6900
    3788 8127 467 3728
    4893 4648 2483 7807
    2421 4310 6617 2813
    9514 4309 7616 8935
    7451 600 5249 6519
    1556 2798 303 6224
    1008 5844 2609 4989
    2702 3195 485 3093
    4343 523 1587 9314
    9503 7448 5200 3458
    6618 580 9796 4798
    5281 9589 798 8009
    7157 472 3622 8538
    2292 6038 4179 8190
    9657 7958 6191 9815
    2888 9156 1511 6202
    2634 4272 55 328
    2646 6362 4886 8875
    8433 9869 142 3844
    1416 1881 1998 322
    8651 21 5699 3557
    8476 7892 4389 5075
    712 2600 2510 1003
    6869 7861 4688 3401
    9789 5255 6423 5002
    585 4182 285 7088
    1426 8617 3757 9832
    932 4169 2154 5721
    7189 9976 1329 2368
    8692 1425 555 3434
    6549 7441 9512 145
    8060 1718 3753 6139
    2423 6279 5996 6687
    2529 2549 7437 9866
    2949 193 3195 3297
    416 8286 6105 4488
    6282 2455 5734 8114
    1701 1316 671 5786
    2263 4313 4355 1185
    53 912 808 1832
    945 4313 7756 8321
    9558 3646 7982 481
    4144 3196 222 7129
    2161 5535 450 1173
    -1 -1

    17
    2044 1659 6292 6439
    7253 24 6154 9510
    4745 649 3186 8313
    4474 8022 2168 4018
    8787 9905 7958 7391
    202 3625 6477 4414
    9314 5824 9334 5874
    4372 159 1833 8070
    7487 8297 7518 8177
    7773 2270 1763 2668
    7192 3985 3102 8480
    9213 7627 4802 4099
    527 2625 1543 1924
    1023 9972 3061 4181
    1003 7432 7505 7593
    2725 3031 8492 142
    7222 1286 3064 7900
    -1 -1

    38
    8360 2413 974 4270
    9170 235 833 9711
    5760 8896 4667 7285
    2550 140 3694 2695
    1624 8019 2125 6576
    1694 2658 6302 7371
    2466 4678 2593 3851
    5484 1018 8464 1119
    3152 2800 8087 1060
    1926 9010 4757 2170
    315 9576 227 2043
    2758 7164 5109 7882
    7086 9565 3487 9577
    4474 2625 5627 5629
    1928 5423 8520 6902
    4962 123 4596 3737
    3261 195 2525 1264
    8260 6202 8116 5030
    326 9011 771 6411
    5547 1153 1520 9790
    4924 188 1763 4940
    851 8662 3829 900
    7713 8958 7578 8365
    3007 1477 1200 6058
    6439 2303 2760 9357
    2324 6477 5108 1113
    4887 9801 2850 4460
    2428 2993 7384 9405
    6540 1111 8704 2835
    2356 6072 9350 8823
    4485 556 3216 1626
    9357 8526 3357 9337
    3271 3869 9361 2896
    3022 9617 112 2717
    8696 1585 4041 4423
    4129 4229 4565 6559
    8932 2296 9855 2053
    6962 3584 9734 6654
    -1 -1

    23
    1457 4369 2532 2963
    2607 2483 911 1635
    67 2848 4675 2938
    2223 2142 3754 6511
    2741 175 1459 7825
    3221 7870 1626 1934
    5205 1783 3850 7398
    2279 2701 2193 2734
    1637 6534 5556 1993
    176 5705 6962 548
    5881 300 4413 6641
    9855 4855 3142 1462
    7611 877 424 2678
    1752 8443 8296 2673
    40 9313 875 72
    2818 610 1017 4932
    8112 695 3169 3831
    40 6488 8685 9090
    9497 2589 5990 5145
    9353 9314 8651 6740
    2044 1258 335 8759
    1192 7605 5264 2181
    8503 3829 3775 608
    -1 -1

    43
    5997 7549 9556 5561
    1627 6467 9541 6129
    1240 7813 9174 601
    6077 215 8683 8213
    3992 5824 5601 3392
    5759 2670 6428 8027
    4084 75 8786 5498
    4970 6287 3847 2604
    503 1221 2663 5706
    2363 9010 2171 7489
    8240 2164 5542 7619
    913 7591 6704 1818
    9232 750 5205 4975
    1539 303 1422 1098
    1247 3584 3648 2971
    7864 2913 1075 1545
    8712 7546 8678 1769
    5262 8519 3985 8289
    5944 2865 8540 3245
    5508 8318 7870 9601
    8323 1132 4472 7152
    5087 8570 9763 9901
    7103 4423 3527 1600
    6969 4015 5565 28
    1543 5347 2088 2943
    2637 2409 6463 5049
    4681 1588 1342 608
    2060 1221 1758 9954
    888 4146 690 7949
    2843 1430 5620 748
    7067 4536 783 8035
    2226 5185 7038 9853
    5629 1224 5748 9923
    3359 2257 4766 4944
    4955 3318 2726 5411
    1025 355 1001 2549
    9496 8584 9515 7964
    3342 8075 7913 6142
    1196 1948 5072 426
    4606 6173 4429 2404
    6705 626 9812 9375
    93 6565 6036 4736
    9141 814 5994 8256
    -1 -1

    3
    3936 838 482 1355
    1015 1131 8230 7841
    4625 2011 2637 4186
    -1 -1

    41
    1650 5662 1634 893
    353 1416 3452 4008
    7262 2233 5454 6303
    6634 6303 4256 148
    1124 2317 4213 7109
    4028 9200 1080 1318
    6858 4050 4155 1361
    5264 1903 3676 9643
    6909 4902 3561 8489
    4948 1282 3653 674
    2220 5402 6923 3831
    9369 3878 259 9008
    2619 3971 3 1945
    9781 6504 2392 2685
    5313 6698 5589 2722
    5938 9037 6410 1461
    6234 2508 9961 3959
    6493 1515 5269 4937
    8869 58 4700 3971
    6264 5117 6215 4555
    7815 8330 3039 212
    9288 8082 1954 6085
    710 4484 4774 8380
    9815 5951 6541 8115
    1679 7110 5898 3073
    788 3977 8132 9956
    8689 6113 8 2941
    5790 1723 1363 28
    5184 4778 7200 5071
    1885 1974 1071 1333
    2867 6153 4295 2168
    825 9676 5629 8650
    2598 3309 4693 4686
    80 116 2249 6667
    1528 6679 7864 9421
    8405 8826 6816 7516
    7726 8666 9087 7681
    9964 1340 5686 6021
    1662 4721 6064 9309
    415 7902 9873 7124
    3941 2745 1762 8423
    -1 -1

    32
    4806 2268 9318 5602
    1907 4307 3481 1012
    1136 6630 4114 6809
    4084 3556 2290 1293
    9996 9152 1054 5345
    4708 248 7491 3712
    5131 114 6439 7958
    4722 9704 6995 1052
    5269 7479 8238 6423
    7918 866 7659 2498
    8486 1196 7462 6633
    2158 2022 1146 8392
    3037 3925 647 9458
    6602 807 4098 7830
    9292 4600 7278 799
    8352 448 3882 540
    8315 4575 8762 9567
    2336 8397 1418 9897
    5828 3851 6816 4230
    4449 6925 658 229
    4520 940 9560 5147
    5162 1655 675 792
    2361 1754 6398 3146
    8714 6946 1188 9569
    8638 7663 5075 4515
    1521 475 5615 528
    3234 2570 905 9464
    9557 8962 4161 524
    2549 7469 330 1923
    8350 4333 2925 910
    9737 6336 8337 1278
    2393 7636 714 8164
    -1 -1
    0
my output is:
  • 24
    1
    24
    11
    17
    19
    28
    3
    22
    15
Please (if you can) test these test cases. :D

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Nov 23, 2004 6:27 pm

I'll bet you like to hear something else, but your output is correct.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue Nov 23, 2004 6:34 pm

at last i Got Accepted Just now when i reduce my arithmatic precision to 1e-5.
I always in geometry problem use epsilon about 1e-8 but in this problem i should use 1e-5. to get accept
special thanks to little joey :D

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sun Apr 03, 2005 5:32 am

My program passed all the sample input in the board.
But still cannot got AC.
I always got WA!
I will be grateful for any help! :cry:

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sun Apr 03, 2005 7:17 am

Here is the test case that tripped me up. If you draw it out you should see what the answer should be and why it might trip up your algorithm (especially if you were using my method).

Code: Select all

2
0 0 10 0
4 1 6 1
5 2
I'm always willing to help, if you do the same.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sun Apr 03, 2005 7:29 am

My program's output is 2 .
Is it correct ?

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sun Apr 03, 2005 7:46 am

Hello Ryan Pai,

I still cannot find any wrong in my code...
My program passed all the testdata I tested.
But wrong answer again and again~
:cry:

Is it possible that the two walls can be overlay ot intersected ?
:cry:

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sun Apr 03, 2005 7:58 am

Yeah, that's the right answer. In my program, I assumed that it might be the case that walls can overlap or intersect (but since any wall gets destroyed as soon as the laser hits it any hidden walls become visible).

Other than that there isn't anything I can think of. You can describe your algorithm and see if anyone can find out what its doing wrong.
I'm always willing to help, if you do the same.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sun Apr 03, 2005 10:39 am

Hello Ryan Pai,
Finally,I got Accepted !!
Because my program initially consider the two same walls as only one.

now my new program pass the following input:

Code: Select all

2
0 10 10 10
0 10 10 10
0 0 
The correct output is

Code: Select all

1
Thanks a lot!!
I am happy now! :D

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Jul 25, 2005 6:25 am

That's not true. My AC solution treats duplicate walls as different. It would give 2 as the answer to your case.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 105 (10500-10599)”