| ENG RUS | Timus Online Judge |
Обсуждение задачи 1342. Фирма веников не вяжетСтраница 1 Sq1 WA #18 // Задача 1342. Фирма веников не вяжет 24 сен 2016 01:50 try changing the float to long double orbby The cost is not decrease // Задача 1342. Фирма веников не вяжет 31 авг 2012 18:51 After reading the background, I thought it would always be q[i]<=p[i]. But it seems not so, and normal dp is ok... Dereky greed algorithm is wrong [1] // Задача 1342. Фирма веников не вяжет 31 мар 2012 06:42 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 Agibalov Evgeniy Re: greed algorithm is wrong // Задача 1342. Фирма веников не вяжет 2 дек 2019 13:47 Best strategy is 150.00 Edited by author 02.12.2019 13:48 marat Recursion // Задача 1342. Фирма веников не вяжет 22 апр 2011 15:25 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. Turigin Yaroslav wa6 // Задача 1342. Фирма веников не вяжет 7 май 2010 01:02 Кто знает 6 тест напишите пожалуйста Vedernikoff Sergey AC in 0.156 sec. Who is better? (-) [3] // Задача 1342. Фирма веников не вяжет 11 ноя 2006 21:11 Dmitry "Logam" Kobelev [TSOGU] Re: AC in 0.156 sec. Who is better? (-) [2] // Задача 1342. Фирма веников не вяжет 3 авг 2008 17:46 What's your algorithm's complexity? Vedernikoff Sergey (HSE: EconomicsForever!) Re: AC in 0.156 sec. Who is better? (-) [1] // Задача 1342. Фирма веников не вяжет 4 авг 2008 14:44 I don't know - it's iterative heuristic. Actually, I still can speed it up... Edited by author 04.08.2008 14:45 bsu.mmf.team Re: AC in 0.156 sec. Who is better? (-) // Задача 1342. Фирма веников не вяжет 20 июн 2011 19:59 Edited by author 20.06.2011 20:08 Samsonov Alex [USU] Question [1] // Задача 1342. Фирма веников не вяжет 21 сен 2005 19:58 If Ki=1 is that true that Pi=Qi? marat Re: Question // Задача 1342. Фирма веников не вяжет 22 апр 2011 15:13 YES Gheorghe Stefan No subject // Задача 1342. Фирма веников не вяжет 8 мар 2005 17:52 The same C++ source got AC with float type and WA #1 with double type... Fat Peter Help me. [6] // Задача 1342. Фирма веников не вяжет 4 мар 2005 17:27 I got WA,who can give me some tests? ronobe (aka oberon) random tests for you... [4] // Задача 1342. Фирма веников не вяжет 4 мар 2005 19:28 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 ronobe (aka oberon) Re: random tests for you... [2] // Задача 1342. Фирма веников не вяжет 4 мар 2005 19:29 Oh. I mean 776436 Gheorghe Stefan Re: random tests for you... [1] // Задача 1342. Фирма веников не вяжет 8 мар 2005 18:53 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? ronobe (aka oberon) Re: random tests for you... // Задача 1342. Фирма веников не вяжет 8 мар 2005 20:02 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.... Agibalov Evgeniy Re: random tests for you... // Задача 1342. Фирма веников не вяжет 2 дек 2019 14:02 It's uncorrect tests. So first broom always must have hidest cost then last marat Re: Help me. // Задача 1342. Фирма веников не вяжет 22 апр 2011 15:12 Try this one: 2 2 1 5 5 1 4 4 Minimum possible cost: 9.00 Try to use double instead of float. Neumann My pro is a bit slow,it AC in 1.25 sec.How to speed it up? // Задача 1342. Фирма веников не вяжет 2 мар 2005 20:34 thwomass what does this mean ? .... [1] // Задача 1342. Фирма веников не вяжет 21 фев 2005 18:03 what does this mean : "the cost of i-th broom’s production is the linear with respect to i function" ? marat Re: what does this mean ? .... // Задача 1342. Фирма веников не вяжет 22 апр 2011 15:13 S(i) = a*i+b S(i) - cost of i-th broom Страницы: 1
|