23ος ΠΔΠ (Πανελλήνιος Διαγωνισμός Πληροφορικής)

[kernelpanic]

Χεχε, ψυχανεμίζομαι οτι μου θυμίζει αμυδρά κάτι στα έγκατα του υποσυνείδητού μου... Αλλά τί;

Αλλά και πάλι, εκατό ΕΚΑΤΟΜΜΥΡΙΑ;!

Παρεμπιπτόντως Θάνο, δε νομίζω να κάνουν το θέμα δυσκολότερο στις επόμενες εκδόσεις· απλά θα προσθέσουν λεπτομέρειες για ειδικές εκδόσεις, περιορισμούς κτλ.(Έχει δυσκολέψει ποτέ το πρόβλημα; )

[thanos713]

Αύριο είναι η μεγάλη μέρα, χεχε.

Btw καλωσόρισες στο forum

[Off-topic]

Spoiler: show

Είσαι εσύ ο thanos713 από το insomnia.gr ή όχι?

[/Off-topic]

Έλα ρε man, ναι, εγώ είμαι, για πες δικό σου username... Καλώς σας βρήκα!

Παρεμπιπτόντως Θάνο, δε νομίζω να κάνουν το θέμα δυσκολότερο στις επόμενες εκδόσεις· απλά θα προσθέσουν λεπτομέρειες για ειδικές εκδόσεις, περιορισμούς κτλ.(Έχει δυσκολέψει ποτέ το πρόβλημα; )

Α, δηλαδή να αρχίσω να το λύνω;

[pman]

δηλαδή να αρχίσω να το λύνω;

Ναι... οι επόμενες εκδόσεις απλώς θα είναι σε .pdf ή σε άλλη έκδοση απλά και θα δίνουν μία ή δύο περισσότερες πληροφορίες ή και καμία.

Spoiler: show

Το έλυσα

[chris]

Απλό είναι, και 100 εκατομμύρια δεν είναι πολλά για το πρόβλημα. Πάω στοίχημα ότι τα μισά testcases δεν θα έχουν N μεγαλύτερο του ~50 000. Πάντως μ'αρέσει σαν θέμα! Αλήθεια, ποιοί τα γράφουν;

[compileGuy]

Απλό είναι, και 100 εκατομμύρια δεν είναι πολλά για το πρόβλημα. Πάω στοίχημα ότι τα μισά testcases δεν θα έχουν N μεγαλύτερο του ~50 000. Πάντως μ'αρέσει σαν θέμα! Αλήθεια, ποιοί τα γράφουν;

Δεν θα το ξεκινησω ακομα καθως έχω πολλα διαβάσματα ( αν και αρχή της χρονιάς ). Παντως σίγουρα 100 εκατομμύρια δεν είναι και μικρός αριθμος . Ισως και να μην είναι πολλα για το πρόβλημα αλλα δεν το έχω πιάσει ακομα .

[pman]

Απλό είναι, και 100 εκατομμύρια δεν είναι πολλά για το πρόβλημα. Πάω στοίχημα ότι τα μισά testcases δεν θα έχουν N μεγαλύτερο του ~50 000. Πάντως μ'αρέσει σαν θέμα! Αλήθεια, ποιοί τα γράφουν;

Η Οργανωτική επιτροπή αναλαμβάνει να γράψει τα θέματα της Α και Β φάσης.

[pman]

Έφτιαξα ένα test case genenator .

1ο τεστ

Spoiler: show

4824
40 582 722 368 549 249 5 942 182 936 835 373 814 194 732 491 99 400 87 572 615 736 529 32 593 481 93 176 667 455 646 701 853 601 505 938 851 449 102 571 195 924 231 302 449 859 426 432 406 425 620 731 558 254 879 207 985 515 725 127 52 655 5 686 305 842 518 41 956 112 658 438 112 192 277 285 297 77 741 206 651 788 60 643 203 479 819 239 52 226 522 64 182 61 430 113 186 353 738 867 872 334 809 93 164 699 50 666 591 184 862 306 698 249 318 923 896 876 616 225 556 61 883 371 705 223 152 712 505 70 317 226 512 250 716 787 338 991 345 333 89 483 300 926 163 920 483 267 276 946 556 796 401 195 153 441 797 198 660 603 718 48 278 934 778 661 27 693 527 266 824 951 688 551 592 721 879 568 818 380 583 860 183 440 241 317 851 745 538 313 2 672 498 928 821 118 480 639 949 149 148 541 791 263 349 164 529 203 356 242 924 580 657 593 834 109 717 307 370 299 536 330 249 665 499 542 19 218 720 296 947 186 761 488 727 93 863 370 928 885 92 950 112 430 402 320 637 916 381 93 205 431 999 47 194 22 291 2 120 754 740 176 276 532 678 362 984 506 389 185 860 902 29 748 31 335 322 258 439 668 769 794 333 14 271 1 724 877 192 844 243 718 538 95 681 76 428 77 321 181 385 664 958 622 329 116 41 481 753 55 417 333 634 116 65 231 688 696 448 528 204 956 149 23 788 836 466 633 985 127 907 574 138 297 110 38 135 117 605 667 632 399 234 344 942 345 890 810 26 908 534 735 78 345 542 285 921 456 190 179 775 665 781 454 71 842 227 141 502 936 596 397 189 177 347 524 575 426 704 560 54 380 636 648 478 604 461 734 273 979 437 691 436 659 160 131 138 332 14 779 8 109 293 328 793 87 699 393 699 422 274 832 210 129 205 349 587 517 426 380 940 933 817 232 362 965 668 464 426 230 894 32 372 828 617 123 109 487 331 400 628 751 777 755 927 371 711 149 735 148 526 310 922 349 959 634 87 326 32 922 319 274 852 373 834 637 895 222 167 546 235 688 425 179 796 303 78 594 419 985 1 985 561 389 515 461 522 586 669 840 156 451 569 934 432 737 314 432 96 450 297 632 962 793 601 900 556 230 526 790 312 720 681 867 666 791 383 307 952 7 75 953 585 378 224 955 129 221 948 228 828 102 962 616 88 484 886 152 920 599 270 151 471 218 751 755 922 7 486 592 417 441 25 770 39 503 236 281 999 848 88 930 874 90 153 108 678 152 687 832 929 555 912 140 927 663 171 729 48 66 152 596 182 433 687 210 341 243 550 128 891 570 302 794 122 335 768 986 356 653 932 955 495 481 579 190 273 544 118 453 405 82 773 263 462 917 909 619 260 557 780 912 373 803 839 428 174 372 998 331 770 771 693 891 937 377 535 541 125 900 446 15 761 710 110 576 803 992 59 155 667 950 71 856 340 588 697 95 195 209 99 495 822 451 794 358 216 788 875 329 122 307 764 86 755 382 449 488 2 447 649 99 379 468 704 385 177 428 325 877 836 470 695 797 443 332 275 733 467 33 761 266 928 734 129 924 739 611 752 991 118 308 479 923 316 9 485 659 60 523 852 44 847 92 10 599 583 751 625 744 931 280 184 495 464 540 507 743 635 220 969 741 996 918 725 611 805 709 360 342 188 466 924 149 620 250 796 691 987 434 778 471 791 705 272 433 674 317 156 272 304 577 958 202 743 157 83 571 118 318 567 602 249 776 335 168 956 737 477 138 654 807 655 881 104 565 914 1 61 50 242 198 21 363 638 806 789 530 698 330 865 598 484 574 28 205 395 428 599 120 237 508 608 990 857 296 565 427 900 316 618 954 919 491 927 33 992 952 750 236 928 770 595 389 14 900 261 362 98 379 860 279 860 569 667 262 502 922 47 404 319 773 361 869 786 309 809 123 142 849 107 635 815 657 967 841 197 490 475 622 651 819 996 406 267 897 133 63 87 784 294 150 859 267 97 332 890 629 393 481 735 369 292 784 381 576 347 652 368 689 759 681 710 205 670 238 136 731 102 833 165 97 225 403 41 661 890 574 265 83 743 500 555 424 296 434 636 302 439 61 465 880 688 771 914 41 187 822 52 120 463 100 663 127 401 675 983 324 597 755 158 887 405 116 682 661 368 729 499 661 124 853 791 417 95 749 121 791 722 750 896 80 591 161 260 560 253 556 103 592 330 428 497 145 488 343 564 234 547 46 641 363 922 426 946 154 139 399 98 430 860 927 146 363 423 936 854 670 390 184 951 841 992 607 962 312 282 743 713 725 898 616 416 545 528 423 363 684 469 199 901 664 896 568 348 689 151 503 788 847 59 239 913 646 744 6 913 733 19 883 473 295 740 671 159 855 510 561 840 103 757 791 963 475 160 433 181 585 222 712 622 604 917 479 900 89 1 729 926 105 499 483 324 536 186 835 422 901 78 106 242 243 698 46 2 736 993 827 621 780 877 498 132 804 260 442 959 752 276 575 26 473 464 736 507 311 836 429 669 106 613 401 265 136 781 692 651 974 541 133 475 738 379 30 774 737 255 975 972 188 497 272 755 544 837 913 396 454 849 932 652 552 374 566 974 389 749 690 758 535 428 279 153 427 785 867 756 737 783 775 418 221 223 244 34 373 104 598 432 67 410 521 267 365 791 802 727 43 371 391 388 417 613 737 662 319 871 801 734 29 59 9 305 642 966 308 304 599 2 688 192 223 190 299 394 634 168 84 486 411 206 379 355 974 233 60 306 85 740 16 812 493 476 229 777 749 31 975 451 287 66 86 242 498 190 298 129 495 218 700 809 234 535 631 853 908 832 343 525 207 752 625 310 825 833 763 810 340 746 221 813 317 313 80 824 972 129 478 553 203 61 787 90 603 734 50 360 811 825 691 55 363 757 667 765 376 803 948 212 184 462 415 708 225 862 199 473 924 520 728 888 440 456 720 783 501 666 468 38 629 804 358 1 970 696 646 695 316 233 503 856 785 324 84 138 130 474 282 556 908 666 863 879 700 804 723 946 951 451 182 493 961 3 307 761 179 700 227 766 235 844 157 980 687 964 756 854 809 852 17 811 746 361 395 487 600 680 565 234 482 3 111 319 454 291 879 336 952 758 465 928 310 532 948 121 865 573 584 519 855 805 333 269 927 722 765 814 876 765 789 367 590 791 175 555 949 415 660 862 911 817 416 47 604 64 230 952 337 831 646 783 282 317 773 98 515 823 804 254 920 682 555 665 739 474 151 225 102 596 81 236 954 147 761 969 535 385 899 207 317 979 489 277 922 243 889 226 5 832 808 878 939 928 263 280 200 569 46 265 689 861 118 720 479 740 643 992 869 310 161 688 62 977 814 313 265 615 313 485 935 868 770 437 799 407 394 428 678 87 28 131 373 712 60 180 622 917 598 859 800 64 538 561 27 880 487 419 149 107 222 539 271 380 305 437 178 430 275 461 150 522 425 191 707 757 970 311 489 718 627 66 798 510 558 60 710 465 603 107 768 28 871 580 22 72 261 597 181 414 707 27 326 698 566 797 524 245 992 872 454 510 657 789 296 457 899 16 269 531 883 801 200 101 525 704 700 671 646 549 495 486 104 606 422 697 866 517 381 368 582 993 631 614 776 419 773 281 179 324 442 439 509 446 646 684 62 304 248 929 397 445 930 111 428 47 856 620 742 367 889 189 973 97 866 213 1000 798 367 837 165 18 395 37 827 896 657 545 836 370 652 855 377 117 948 464 415 28 850 62 232 580 775 645 477 208 512 444 810 518 564 86 634 657 336 196 645 992 907 325 351 727 862 17 379 845 63 826 648 758 294 708 610 602 422 847 180 486 888 3 845 849 973 627 673 169 443 116 394 559 954 608 813 32 871 470 890 661 441 885 487 118 650 201 540 99 31 84 20 83 820 73 138 512 554 469 682 546 858 183 738 563 175 849 584 771 335 295 558 742 138 968 836 514 815 739 148 645 226 748 940 823 402 398 719 979 155 563 837 148 767 642 501 262 138 145 496 802 718 899 959 318 28 579 447 956 956 546 956 106 679 638 733 826 163 747 246 634 743 430 163 399 552 696 668 822 459 999 995 44 451 643 902 998 405 96 81 283 443 103 180 488 254 962 197 44 671 376 71 614 640 69 459 323 870 102 685 629 641 324 307 712 704 679 282 143 151 68 578 702 450 682 962 321 862 569 750 797 462 100 240 501 284 49 838 241 112 879 163 281 846 671 968 696 147 486 995 791 496 154 88 951 354 578 144 276 841 715 280 934 343 224 731 97 4 650 722 375 408 833 867 364 48 233 288 875 189 496 98 504 561 952 541 901 267 576 725 312 877 295 825 437 92 380 912 880 943 23 81 710 852 796 567 141 112 378 429 801 206 935 342 752 353 934 944 488 573 19 634 535 243 614 132 123 219 151 613 316 439 729 195 135 349 89 118 92 22 809 94 554 381 584 103 457 466 213 618 248 855 44 494 32 98 615 94 641 741 449 364 620 106 199 886 832 235 360 377 681 113 479 764 814 331 718 758 58 610 613 122 781 507 739 857 875 260 883 80 934 410 443 317 615 522 42 292 819 118 976 591 284 379 371 765 861 177 631 306 906 386 757 168 519 583 519 435 816 591 178 75 81 481 557 86 951 541 273 93 479 574 634 472 565 626 486 436 807 309 411 211 571 978 981 708 30 948 592 637 823 380 131 303 228 948 542 985 419 444 781 815 259 682 981 356 564 551 623 726 60 552 403 865 604 994 31 7 411 666 119 798 849 731 551 138 886 537 103 485 27 862 94 228 441 795 762 812 841 738 295 61 933 305 743 821 237 89 752 640 892 72 356 183 524 172 581 894 94 481 271 219 535 549 683 715 904 697 209 799 637 355 885 248 32 634 822 558 454 345 171 263 466 704 278 982 697 815 614 802 262 980 567 281 847 607 125 901 360 212 577 510 174 457 650 103 798 641 56 21 919 656 718 541 566 136 654 317 969 891 841 799 397 274 303 698 619 29 171 25 585 900 378 759 125 221 326 523 272 399 655 313 512 343 929 217 614 913 811 4 82 985 167 436 571 34 582 883 492 159 446 103 491 56 454 60 611 175 216 947 324 252 80 698 562 542 285 347 940 83 30 250 301 337 367 809 456 741 228 718 16 461 749 695 286 945 130 389 734 967 33 591 428 976 54 904 147 44 906 532 398 661 687 494 803 771 626 326 788 540 626 778 496 518 753 210 242 103 993 344 816 365 200 520 583 154 623 52 28 995 551 915 982 169 109 803 283 999 768 172 904 380 952 495 149 36 73 295 535 802 417 223 856 257 710 341 460 339 323 725 414 121 853 720 747 397 721 470 580 84 24 842 738 416 101 70 709 837 662 447 637 818 570 553 837 418 267 206 29 820 947 435 263 343 155 948 580 338 666 953 288 979 35 913 291 839 298 326 825 98 648 472 85 895 109 719 193 441 678 347 553 619 847 87 449 861 138 910 971 488 880 100 214 452 544 735 396 40 254 551 130 882 102 188 549 512 249 336 571 806 159 237 432 264 862 48 594 67 657 766 703 847 325 989 614 463 240 742 19 916 706 658 471 839 665 795 999 190 464 644 603 417 103 731 666 21 393 614 772 936 977 916 464 150 983 630 424 788 450 910 889 99 182 558 143 271 920 195 769 881 711 652 833 690 774 462 783 424 95 10 502 566 2 609 470 871 862 654 868 555 143 989 871 725 233 555 892 836 860 446 493 577 48 454 325 1000 843 837 447 211 649 619 56 635 275 868 305 752 227 694 778 83 927 349 660 434 668 882 213 540 348 76 169 5 483 381 287 540 623 344 386 620 758 521 849 16 981 798 618 970 670 772 810 741 817 366 15 65 318 697 282 280 889 227 631 327 120 918 447 390 65 783 392 395 383 724 51 396 247 46 655 741 966 842 228 785 237 958 298 731 808 859 491 71 931 821 542 45 13 483 981 982 298 499 162 250 44 933 45 817 538 572 265 248 988 784 584 591 253 663 236 48 785 149 448 515 793 89 398 560 781 955 978 636 858 147 150 936 748 11 431 741 261 344 592 717 863 173 343 886 566 488 317 600 386 281 209 866 668 808 527 848 62 606 812 255 616 159 181 404 64 983 489 682 465 715 381 802 744 513 951 56 59 826 933 475 306 126 814 965 691 65 89 548 521 637 4 169 388 816 680 343 279 336 716 342 838 44 742 432 38 236 305 67 714 76 772 497 498 252 751 76 871 260 612 342 77 711 827 752 399 173 901 713 10 486 590 473 707 3 853 503 178 935 54 776 691 718 890 225 938 156 956 743 623 337 688 644 210 884 999 805 513 830 166 978 128 777 808 253 808 41 953 950 155 665 220 855 559 240 407 492 393 261 350 701 4 321 741 839 354 909 458 479 697 4 626 265 762 946 978 672 287 221 649 911 682 874 885 167 758 979 43 330 888 688 531 272 477 243 259 351 803 233 587 744 400 382 568 815 64 960 229 380 925 615 615 24 567 475 272 394 903 582 814 43 470 947 621 126 915 216 634 804 805 696 985 526 638 268 810 229 513 179 599 143 917 607 890 434 801 770 356 102 482 241 641 438 444 784 882 128 294 663 787 325 169 371 238 34 370 743 535 216 773 428 882 546 324 662 810 485 705 298 27 212 161 157 970 757 441 335 564 653 301 320 468 547 727 185 841 900 196 198 759 155 605 922 549 596 621 251 311 329 622 984 692 532 242 145 619 46 814 662 897 503 961 699 566 71 566 834 42 340 125 337 562 693 257 341 55 887 454 695 929 318 921 918 439 222 133 565 466 322 475 759 563 364 241 625 266 999 798 102 305 226 805 408 392 213 768 526 538 897 111 857 32 307 458 187 572 561 723 554 761 337 55 849 921 510 750 1 583 939 561 542 6 13 755 204 529 604 203 476 885 459 986 377 52 121 648 968 843 183 467 327 278 578 283 13 851 331 967 507 900 237 548 561 41 510 672 596 317 722 346 191 664 293 412 511 789 624 931 972 988 142 302 644 699 39 606 794 377 572 549 903 899 971 178 800 218 950 659 233 700 927 844 759 658 703 368 988 339 112 236 231 423 775 964 578 999 982 265 432 42 632 792 958 395 958 425 289 97 378 461 377 455 83 65 269 869 880 467 919 934 688 283 777 317 610 436 744 753 336 755 328 72 265 399 56 731 518 753 295 919 733 462 998 188 789 634 200 281 370 736 425 103 890 351 571 516 758 39 70 603 605 901 40 139 573 947 587 389 707 955 167 138 70 917 984 108 383 735 729 20 139 837 936 972 292 441 964 317 452 500 797 556 492 478 362 433 549 187 25 912 853 775 795 195 796 563 157 256 935 575 959 503 668 74 198 503 439 113 772 305 45 724 939 684 439 823 478 523 537 512 153 676 715 52 922 979 440 935 263 734 22 851 922 826 165 696 267 486 611 414 972 902 7 951 363 659 388 64 731 265 1 953 764 889 95 115 756 56 186 49 750 784 955 586 578 765 885 519 741 83 360 952 235 358 163 668 706 217 20 48 465 427 524 183 264 360 759 547 898 748 266 259 448 405 552 757 816 849 974 838 998 749 669 824 625 63 224 163 922 463 287 952 880 530 44 817 303 495 748 493 947 822 335 859 431 268 363 436 219 820 926 286 29 307 99 686 207 395 24 669 506 563 109 671 641 236 919 576 145 767 69 584 359 261 403 17 387 807 909 414 763 336 126 438 603 111 642 449 132 945 209 826 266 518 374 198 107 499 790 820 597 944 468 13 54 499 828 78 10 589 750 44 657 571 846 511 263 184 26 50 88 985 388 913 323 929 241 476 262 181 488 620 707 235 191 460 649 183 859 490 310 478 414 165 732 615 406 824 633 310 787 680 83 307 681 83 108 458 375 242 91 364 431 617 675 70 991 164 151 945 95 876 142 242 397 177 284 306 549 410 418 409 125 92 894 78 168 664 61 907 408 792 201 879 153 394 174 555 820 853 497 561 490 36 835 409 466 738 306 398 373 173 96 697 279 525 920 524 976 623 7 834 476 909 664 469 776 712 723 320 438 49 622 863 419 108 99 875 126 758 412 162 92 888 693 526 226 12 258 245 890 336 241 473 683 169 712 96 378 898 154 135 37 61 782 59 73 169 425 368 617 709 453 782 43 508 545 776 678 377 467 359 47 820 907 814 404 638 274 935 552 761 307 295 80 924 769 877 765 174 74 216 683 552 434 426 913 160 835 463 315 163 731 435 469 731 462 219 520 937 437 914 313 445 639 463 768 996 232 957 695 17 928 580 804 807 293 710 512 541 219 900 857 243 930 721 764 132 905 415 111 717 218 873 567 37 614 673 37 125 282 459 414 698 106 682 963 481 893 2 766 594 737 765 991 744 409 449 430 496 12 890 761 112 328 636 496 730 774 716 327 720 960 688 364 858 576 347 346 374 27 46 493 64 438 804 374 283 671 836 313 934 175 36 558 586 175 707 13 427 441 288 814 909 464 466 335 81 83 232 175 544 413 642 859 175 449 127 470 803 612 776 150 199 27 309 861 92 559 575 310 369 14 149 177 147 692 299 472 54 218 591 643 372 238 502 616 254 674 376 407 505 593 615 797 682 47 997 696 838 745 710 467 971 974 123 65 611 468 137 575 642 581 282 445 429 75 786 710 37 98 325 353 77 669 215 462 720 492 220 893 591 620 265 987 58 271 402 630 804 310 686 260 116 853 920 247 145 430 407 363 669 248 816 211 534 56 586 937 985 465 698 253 376 73 609 656 325 244 243 760 719 364 328 798 853 257 792 751 672 502 187 993 934 732 288 622 380 899 719 973 860 78 447 79 8 382 324 448 877 770 500 615 139 774 897 583 940 561 252 862 419 419 472 830 488 399 12 963 145 269 589 836 66 755 388 645 24 757 443 388 994 971 94 554 105 306 744 589 34 381 947 220 890 6 516 763 697 479 326 111 146 934 854 212 34 1 735 493 823 102 215 923 291 118 82 211 449 962 365 449 503 574 893 273 540 710 793 263 268 447 933 685 730 55 921 678 533 95 770 136 990 479 639 855 865 187 278 952 258 597 776 379 354 379 706 365 154 211 526 692 847 620 369 804 494 23 342 625 274 165 907 358 669 650 858 102 147 307 404 114 645 836 137 482 468 509 298 647 235 350 82 992 186 96 466 323 65 854 189 335 610 348 628 143 795 534 2 402 746 845 242 73 513 926 360 216 900 291 717 8 848 661 119 300 983 50 960 299 89 564 982 206 765 91 707 747 560 516 950 449 141 481 642 636 255 43 341 923 579 597 539 304 312 843 204 32 35 202 347 364 6 26 689 991 138 922 826 161 413 139 494 220 757 976 818 421 358 827 656 300 608 307 708 895 740 517 353 28 88 817 260 582 282 575 494 866 770 146 728 115 594 107 642 114 354 864 52 474 495 311 561 163 732 150 537 413 268 773 566 711 758 470 161 521 866 243 29 519 108 145 453 839 367 588 386 885 171 764 455 884 665 222 832 680 566 933 96 921 519 322 595 163 69 50 347 484 505 455 679 366 473 850 176 301 786 143 166 635 17 833 507 939 125 216 694 674 903 936 363 524 678 109 568 278 916 987 179 48 500 98 738 638 360 730 139 207 398 563 638 589 643 777 752 966 155 414 49 554 943 592 376 295 952 236 133 377 371 27 615 989 110 221 256 152 138 339 413 764 769 33 906 627 442 379 798 727 826 791 787 848 757 804 473 575 38 201 386 596 915 458 985 123 917 566 191 148 118 236 670 915 260 664 290 677 213 200 389 788 699 323 10 972 826 324 892 911 191 268 872 958 132 646 143 698 529 271 25 218 949 598 647 573 22 496 95 858 861 110 333 918 893 611 272 926 37 217 171 118 156 20 117 377 317 737 83 1 43 936 916 306 991 375 446 458 927 33 303 340 1 64 734 621 17 486 571 366 151 322 445 979 5 577 98 347 103 187 92 826 347 87 706 243 939 297 4 722 177 172 116 713 586 787 601 441 6 940 661 531 871 791 145 551 529 915 240 485 65 530 826 395 120 182 522 446 202 940 785 20 457 272 948 386 280 321 468 353 749 358 205 550 238 89 377 626 80 475 949 63 652 312 5 973 531 604 635 219 523 423 926 514 250 85 201 958 850 785 240 606 694 355 387 903 772 991 236 964 499 856 83 169 951 156 716 559 539 898 535 754 359 410 321 98 522 60 185 543 473 539 422 953 80 707 535 958 560 817 954 597 418 586 713 778 995 767 577 123 129 71 461 595 501 109 772 405 337 572 966 979 732 560 812 879 404 118 497 435 867 431 595 524 260 657 358 756 152 855 107 903 309 523 101 870 918 577 605 339 712 693 55 388 852 367 812 75 417 989 33 405 132 778 55 250 938 222 524 549 501 215 355 108 110 118 55 362 754 877 518 3 455 655 180 544 696 24 421 804 664 343 655 597 436 345 62 783 924 593 162 262 995 948 735 218 588 649 211 976 256 153 270 775 933 619 517 344 537 140 470 993 712 205 555 91 194 165 177 331 177 776 672 46 689 704 496 913 56 531 602 200 848 861 988 997 235 208 689 35 55 634 857 843 154 758 909 783 71 812 326 142 449 709 438 247 120 906 718 913 386 949 778 410 827 466 634 286 8 671 842 755 569 506 845 290 837 578 573 529 67 480 966 199 285 23 60 559 159 594 314 905 169 709 436 869 433 48 695 226 157 487 264 222 40 532 762 542 402 705 156 232 821 833 690 687 949 743 818 496 623 817 794 546 326 549 25 659 10 461 331 905 378 528 993 813 835 801 768 775 513 876 944 454 917 917 920 830 32 123 208 992 664 934 736 532 32 133 975 282 308 107 462 146 854 362

Output
1000.000

[thetrojan01]

@sotiris: σε μια στιγμή νόμισα ότι θα έδινες κώδικα για γεννήτρια αρχείων .in

Θα αρχίσω να γράφω το βράδυ (πιστεύω... έχω κάτι διαβάσματα)

[pman]

@sotiris: σε μια στιγμή νόμισα ότι θα έδινες κώδικα για γεννήτρια αρχείων .in

Θα αρχίσω να γράφω το βράδυ (πιστεύω... έχω κάτι διαβάσματα)

Εάν το θέλετε πάρτε το

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdlib.h>
#include <cstdlib>
#include <ctime> 

#define MAX 1000
#define MAXP 100000000

int i , P , temp;

int main(){
 FILE*fout=fopen("profit.in","w");
 srand((unsigned)time(0));
 P = (rand()%MAXP)+1; 
 fprintf(fout,"%d\n",P);
 for(i=0;i<P;++i){
 temp = (rand()%MAX)+1;
 fprintf(fout,"%d ",temp);
 } 
 fprintf(fout,"\n");
 fclose(fout);    
 return 0;   
}

[thetrojan01]

ευχαριστούμε

[thanos713]

Spoiler: show

Το έλυσα

Me too!!!!

[thetrojan01]

Spoiler: show

100 εκατομ. N δεν είναι λίγο μπόλικα;
αφού μέσα σε 1s τα καταφέρενει συνήθως 5 εκατομ. Ν?

[chris]

Η Οργανωτική επιτροπή αναλαμβάνει να γράψει τα θέματα της Α και Β φάσης.

H επιστημονική επιτροπή εννοείς. Ρώτησα επειδή στον ΙΟΙ '10 δόθηκε μεγάλη έμφαση στους δημιουργούς των θεμάτων.

Παντως σίγουρα 100 εκατομμύρια δεν είναι και μικρός αριθμος

Το πόσο μικρός είναι ένας αριθμός είναι σχετικό, και εξαρτάται συνήθως από το τι εκφράζει και για πια κλίμακα μιλάμε

Spoiler: show

αφού μέσα σε 1s τα καταφέρενει συνήθως 5 εκατομ. Ν?

έ; Ποιός τα καταφέρνει;

Προφανώς οι αριθμοί και τα όρια χρόμου δεν μπαίνουν στην τύχη.

[pman]

Spoiler: show

100 εκατομ. N δεν είναι λίγο μπόλικα;
αφού μέσα σε 1s τα καταφέρενει συνήθως 5 εκατομ. Ν?

Ναι είναι αρκετά... αλλά σίγουρα θα μας συμβουλέψουν κάπως.....

@chris η επιστημονική επιτροπή αναλαμβάνει τα θέματα της Γ φάσης και του καμπ.

[pman]

Έλυσε κανείς το θέμα σε γραμμικό χρόνο? Καταρχάς λύνεται σε γραμμικό χρόνο?
Εγώ πιστεύω ναι αλλά δύσκολα.

[thetrojan01]

Spoiler: show

αφού μέσα σε 1s τα καταφέρενει συνήθως 5 εκατομ. Ν?

έ; Ποιός τα καταφέρνει;

Προφανώς οι αριθμοί και τα όρια χρόμου δεν μπαίνουν στην τύχη.

Συγγνώμη για τον τρόπο που διατύπωσα τον προβληματισμό μου παραπάνω...

Εννοούσα ότι ένα πρόγραμμα με είσοδο της τάξης των 5 εκατομμυρίων, συνήθως παίρνει 1s σε τέτοιους διαγωνισμούς για να τερματίσει. Άρα δε θα αργεί λίγο ένα πρόγραμμα με είσοδο 100 εκατομ. ακόμα και γραμμικής πολυπλοκότητας;

[compileGuy]

Παντως σίγουρα 100 εκατομμύρια δεν είναι και μικρός αριθμος

Το πόσο μικρός είναι ένας αριθμός είναι σχετικό, και εξαρτάται συνήθως από το τι εκφράζει και για πια κλίμακα μιλάμε

Αφού μιλάμε για το πρόβλημα, για τι δεδομένα και για τι κλίμακα μιλάω? ( των παρόμοιων προβληματων φυσικα )

Άμα το μέγιστο είναι 100 εκατομμύρια ( στο συγκεκριμένο πρόβλημα ) και o χρόνος στα προβλήματα συνήθως( τουλάχιστον στα junior ) είναι 1 sec , είναι πολλά καθως στην καλύτερη περίπτωση ( αφού δεν θα έχουμε και τρομερά pc ) θα είναι 10 εκατομμυρια πραξεις / 1 sec = 10 secs ( χρόνος που πολύ σπάνια συναντάς ).

Με αυτά τα δεδομένα εύκολα καταλήγεις πως τα 100 εκατομμύρια δεν είναι μικρός αριθμός

[chris]

Παντως σίγουρα 100 εκατομμύρια δεν είναι και μικρός αριθμος

Το πόσο μικρός είναι ένας αριθμός είναι σχετικό, και εξαρτάται συνήθως από το τι εκφράζει και για πια κλίμακα μιλάμε

Αφού μιλάμε για το πρόβλημα, για τι δεδομένα και για τι κλίμακα μιλάω? ( των παρόμοιων προβληματων φυσικα )

Άμα το μέγιστο είναι 100 εκατομμύρια ( στο συγκεκριμένο πρόβλημα ) και o χρόνος στα προβλήματα συνήθως( τουλάχιστον στα junior ) είναι 1 sec , είναι πολλά καθως στην καλύτερη περίπτωση ( αφού δεν θα έχουμε και τρομερά pc ) θα είναι 10 εκατομμυρια πραξεις / 1 sec = 10 secs ( χρόνος που πολύ σπάνια συναντάς ).

Με αυτά τα δεδομένα εύκολα καταλήγεις πως τα 100 εκατομμύρια δεν είναι μικρός αριθμός

10 εκατομμύρια πράξεις σε ένα δέυτερο; από που βγαίνει αυτό; Αν προλαβαίνεις να διαβάσεις 100 000 000 αριθμούς σε 1-2 δεύτερα, είσαι άνετος.

[thetrojan01]

βγαίνει χοντρικά - εμπειρικά. Αν ένας επεξεργαστής στα 2 GHz κάνει περίπου 14,6 * 10^6 IPS τότε ακόμα και αν σκεφτούμε πως η fscanf είναι 1 instruction, τότε σίγουρα τα 100.000.000 fscanf θα πάρουν παραπάνω από 1 δευτερόλεπτο σε έναν τέτοιο επεξεργαστή.

[Κηπουρίδης]

Επίτηδες είναι ρε παιδιά τεράστιο, πιθανώς κι οι σωστές λύσεις να χάσουν από χρόνο, απλά για να πάρουν παραπάνω βαθμούς όσοι το λύσουν σε O(N). Σωτήρη, με τι πολυπλοκότητα το έλυσες; Γιατί αν όχι με O(N) τότε κοίτα να αλλάξεις τελείως τον αλγόριθμο ( ναι, υπάρχει λύση ) γιατί με ν-τετράγωνο ξεφεύγεις χοντρά...