- Not given, whether points in the input are integers or not (in the case they are not, sample input should reflect this somehow)
- Not mentioned that points in the input may coinside (from the statement it looks like they should not, but in the input they are!!!)

Edited by author 20.01.2014 11:24

There's also a case when a disk is entirely in other, so there's no edge intersection, so be aware :)

Edited by author 19.01.2014 23:19

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n;int m;int inp;
    double a[10001];
    double fr2,fractpart, intpart;
    cin>>n>>m;
    for (int i=0;i<m;++i)
    {
        cin>>inp;
        ++a[inp-1];
    }
    for (int i=0;i<n;++i)
    {
        cout.precision(4);
        fractpart = modf(((a[i]/m)*100.00),&intpart);
        if (fractpart==0) cout<<(a[i]/m)*100.00<<".00%\n";
        else cout<<(a[i]/m)*100.00<<"%"<<"\n";
    }
    return 0;
}

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

The answer is 805627284

Big thanks to author. This is my favourite problem ;)

When I've written bfs I've got TL29, when I've written Kd-tree, I've got TL26 ....
Hey, guys, give me some hints how to solve this problem, please ....

Note Accuracy

I have only one place where i'm dealing with doubles -
trying to check B*B<4*A*C. Can it be a problem? If not, then probably something else is screwed up.

UPD: Yes, in my case it was precision. I got rid of doubles in that check - got AC.

Edited by author 17.01.2014 14:53

My AC program works very slowly on the following test:
12
256 256 256 256 256 256 256 256 256 256 256 1

Can you add it to the testset?

I am getting WA in test#10. Can anyone help me??? Thanks in advance. :)

if you will not send me the answer of this problem i will kick you
out of the contest.!!

Please help me


#include <iostream>
#include <math.h>


using namespace std;

int main(int argc, const char * argv[])
{

    double stack[1000];

    int index = 0;
    while (cin >> stack[index]) {
        index++;
    }


    index--;
    for (; index > 0; index--) {
        printf("%.4lf\n", sqrt(stack[index]));
    }


}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _1542
{
    public class word
    {
        public  string line;
        public  int count;
        public  word(string g="", int f=0)
        {
            line=g;
            count =f;
        }
    }
    class sortim: IComparer<object >
    {
        public int Compare(object x, object y)
        {
            word a, b;
            a = (word)x;
            b = (word)y;
            if (a.count < b.count) return 1;
            else if (a.count > b.count) return -1;
            else return String.Compare(a.line, b.line);

        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            sortim sort = new sortim();
            int n = Convert.ToInt32(Console.ReadLine());
            word[] wor = new word[n];
            for (int i = 0; i < n; i++)
            {
                string[] temp = Console.ReadLine().Split(' ');
                wor[i] = new word(temp[0], Convert.ToInt32(temp[1]));
            }
            int g= Convert.ToInt32(Console.ReadLine());

            for (int i = 0; i < g; i++)
            {
                string request = Console.ReadLine();
                word[] select = Array.FindAll(wor, e => e.line.Substring(0,request.Length)==request );
                Array.Sort(select, sort);
                for (int i1 = 0; i1 < Math.Min(select.Length,10); i1++)
                {
                    Console.WriteLine(select[i1].line);
                }
                if (i!=g-1) Console.WriteLine();
            }
        }
    }
}

p - это суммарная сила всплеска по всем заклинаниям, которую могут выдержать волшебники, или максимальная сила всплеска за одно заклинание (каждый раз одна и та же)?

Please somebody provide some more test cases ...

since X,M,Y in [0,1000]... power(X,N) is very large, we can't to calculate!

f(N) = X^N mod M = Y

then, X^N=k*M+Y

f(N+1) = X^(N+1) mod M
           = (X^N*X) mod M
           =(k*M*X+Y*X) mod M
           =Y*X mod M
           =f(N)*X mod M

example for X,M,Y is 2,6,4.
f(0)=2^0 mod 6    = 1
f(1)=f(0)*2 mod 6 = 2
f(2)=f(1)*2 mod 6 = 4 (ok)
f(3)=f(2)*2 mod 6 = 2
f(4)=f(3)*2 mod 6 = 4 (ok)
f(5)=f(4)*2 mod 6 = 2
f(6)=f(4)*2 mod 6 = 4 (ok)

thanks.

misprint
должен состоять также их одной строки
их->из

Edited by author 12.01.2014 22:05

If your output format differs from the required output format (even by one space).....you will get WA. So be careful.....

suffix array + HESH    = WA 67 , why

please give me some test

Edited by author 08.11.2013 17:06