| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Help me. | Fat Peter | 1342. Фирма веников не вяжет | 2 дек 2019 14:02 | 7 |
I got WA,who can give me some tests? Hope this will help.
submission ID of an AC solution is 76436
50 1000
71 742 876
37 913 297
71 517 146
62 734 670
67 122 568
70 521 331
68 529 255
100 831 713
53 946 579
80 72 568
19 338 683
40 914 523
12 339 692
56 111 463
40 376 940
40 387 459
15 767 3
56 408 195
16 778 723
83 245 344
27 376 961
89 639 173
81 139 498
70 345 408
56 555 470
14 572 979
29 426 872
17 340 491
40 153 317
18 368 977
42 124 140
35 20 341
70 77 443
1 914 11
77 948 658
15 100 83
16 197 811
75 308 923
49 691 910
78 698 200
87 789 908
60 905 807
96 55 432
38 31 572
42 948 127
42 545 250
28 514 982
91 102 445
51 679 557
17 873 976
Minimum possible cost: 275665.59
50 1000
45 292 824
20 386 715
71 692 204
71 956 78
82 784 432
10 634 360
79 391 805
41 793 303
77 653 596
81 708 389
95 840 856
22 54 380
60 197 699
1 901 354
64 797 555
37 475 800
18 909 626
46 993 186
88 640 868
32 746 326
8 768 778
91 766 66
24 683 179
33 10 262
100 435 603
57 424 869
59 877 853
54 837 137
27 116 474
34 643 695
28 773 131
81 9 462
65 105 991
5 181 260
76 909 102
85 706 446
5 287 24
58 276 162
35 987 671
39 901 813
58 96 102
55 254 274
87 497 737
41 60 98
18 717 944
85 82 804
42 679 49
68 470 85
82 519 230
24 803 761
Minimum possible cost: 309434.71
50 1000
42 98 421
55 635 989
74 606 405
99 210 617
64 447 485
28 354 110
69 665 789
83 608 917
32 850 117
31 662 314
89 751 17
6 578 799
80 27 100
65 245 812
51 742 312
15 653 987
20 407 806
64 647 342
66 385 980
72 517 237
25 493 663
18 125 802
6 687 408
77 919 715
20 928 977
53 141 966
20 564 412
78 390 441
12 219 163
38 408 65
83 913 630
97 374 693
98 430 739
59 719 237
75 479 934
64 558 505
24 327 633
54 0 114
29 169 48
66 508 661
80 764 669
36 305 61
12 695 840
13 933 813
73 309 268
31 672 838
8 691 964
100 146 620
99 392 729
88 88 691
Minimum possible cost: 291969.15
50 877
89 644 415
29 55 779
45 299 56
44 476 946
85 938 827
71 152 532
26 988 970
40 613 648
90 145 737
41 317 343
50 489 546
96 434 985
39 809 493
55 739 395
59 542 269
72 106 833
17 924 708
66 521 953
78 358 21
44 502 1000
74 546 627
98 337 664
99 251 34
87 610 821
3 714 13
52 280 900
84 261 845
59 56 357
18 613 333
48 71 836
34 367 144
34 28 536
8 219 246
31 999 234
12 100 673
48 88 812
48 850 676
63 245 122
13 641 526
68 660 163
77 327 968
52 480 821
14 739 544
85 206 521
96 724 904
25 863 35
45 14 646
94 347 941
37 879 589
19 852 953
Minimum possible cost: 221384.20
50 534
64 422 648
95 419 88
8 846 911
49 447 706
31 924 619
47 68 151
57 543 99
30 542 338
33 582 546
70 339 610
25 228 180
4 163 502
38 856 823
37 846 775
10 987 290
19 29 435
17 862 744
76 352 355
38 913 134
70 30 182
10 906 226
65 994 391
35 979 889
25 7 788
85 3 482
99 157 468
44 59 879
51 692 318
7 35 835
28 99 610
76 869 845
24 516 223
69 415 144
4 622 490
21 840 877
84 243 806
87 423 534
70 396 847
63 195 365
81 627 808
50 593 375
92 754 251
70 745 514
23 539 395
65 788 739
7 25 615
55 154 269
18 288 33
54 860 760
41 752 72
Minimum possible cost: 102215.67
50 645
72 407 246
20 732 810
45 545 320
26 844 486
68 695 794
77 156 21
71 681 328
76 774 911
81 216 272
19 769 547
25 899 891
28 615 873
2 186 14
69 848 643
90 407 497
75 703 621
61 913 147
7 388 696
93 313 982
7 341 197
66 372 765
10 990 729
80 159 8
57 611 45
87 539 890
91 589 131
24 536 957
53 63 53
54 680 252
41 439 600
18 603 337
33 826 623
80 54 134
13 958 475
76 596 137
19 867 574
86 750 815
96 359 922
59 648 739
88 451 977
6 569 358
71 185 683
76 497 285
57 42 231
5 210 793
47 145 323
46 925 652
78 175 982
15 158 909
26 898 197
Minimum possible cost: 114316.36
50 415
1 468 33
4 964 197
3 44 219
4 190 69
2 657 560
3 541 34
4 934 456
9 976 383
7 887 151
9 859 806
10 130 370
2 289 678
8 842 330
6 732 811
1 499 0
3 384 863
4 411 254
9 480 549
9 838 560
6 920 825
1 971 186
4 907 395
4 493 99
3 490 373
5 653 919
9 924 566
1 134 921
8 311 9
3 249 341
8 925 765
5 444 602
2 790 44
8 635 614
10 206 140
9 744 685
1 896 809
4 847 644
10 44 452
3 820 365
10 570 998
6 221 821
4 234 592
9 464 765
5 613 402
7 224 220
8 179 837
7 498 606
7 739 532
1 854 711
9 855 485
Maximum possible amount: 275
Minimum possible cost: 150432.00 that's strange, my AC program gives at your first 3 tests slightly different results...
you made DP with A[i][j] -> i workshops and j brooms right? Thats really strange 8(.
Anyway I have submitted my program once more. AC. Submission id is 780543. The DP is same as you described... Something fishy.... It's uncorrect tests. So first broom always must have hidest cost then last Try this one:
2 2
1 5 5
1 4 4
Minimum possible cost: 9.00
Try to use double instead of float. |
| greed algorithm is wrong | Dereky | 1342. Фирма веников не вяжет | 2 дек 2019 13:47 | 2 |
there is some problem in greed algorithm,such as
2 2
3 80 80
3 100 0
the best strategy is 100,50 while greed algorithm gets 80,80 Best strategy is 150.00
Edited by author 02.12.2019 13:48 |
| WA #18 | Sq1 | 1342. Фирма веников не вяжет | 24 сен 2016 01:50 | 1 |
try changing the float to long double |
| The cost is not decrease | orbby | 1342. Фирма веников не вяжет | 31 авг 2012 18:51 | 1 |
After reading the background, I thought it would always be q[i]<=p[i]. But it seems not so, and normal dp is ok... |
| AC in 0.156 sec. Who is better? (-) | Vedernikoff Sergey | 1342. Фирма веников не вяжет | 20 июн 2011 19:59 | 4 |
What's your algorithm's complexity? I don't know - it's iterative heuristic.
Actually, I still can speed it up...
Edited by author 04.08.2008 14:45
Edited by author 20.06.2011 20:08 |
| Recursion | marat | 1342. Фирма веников не вяжет | 22 апр 2011 15:25 | 1 |
Let a(n,k) be the cost of n brooms using k factories. S(k, i) the cost of i brooms produced in k-th factory. Then
a(n,k) = { min i from 0 to min n of { a(n-i,k-1) + S(k,i) }, if Kk >= n }
{ 4200000000, otherwise }
Kk - maximal amount of brooms that could be produced in k-th factory. |
| Question | Samsonov Alex [USU] | 1342. Фирма веников не вяжет | 22 апр 2011 15:13 | 2 |
Question Samsonov Alex [USU] 21 сен 2005 19:58 If Ki=1 is that true that Pi=Qi? |
| what does this mean ? .... | thwomass | 1342. Фирма веников не вяжет | 22 апр 2011 15:13 | 2 |
what does this mean : "the cost of i-th broom’s production is the linear with respect to i function" ? S(i) = a*i+b
S(i) - cost of i-th broom |
| wa6 | Turigin Yaroslav | 1342. Фирма веников не вяжет | 7 май 2010 01:02 | 1 |
wa6 Turigin Yaroslav 7 май 2010 01:02 Кто знает 6 тест напишите пожалуйста |
| No subject | Gheorghe Stefan | 1342. Фирма веников не вяжет | 8 мар 2005 17:52 | 1 |
The same C++ source got AC with float type and WA #1 with double type... |
| My pro is a bit slow,it AC in 1.25 sec.How to speed it up? | Neumann | 1342. Фирма веников не вяжет | 2 мар 2005 20:34 | 1 |
|
