![]() ![]() ![]() |
![]() ![]() |
Ratio
Solution Judge's input Judge's output Clarifications Comments
Gainers 1498
Losers 902
As a person with a head for numbers, you'll notice that the anchorperson could have said ``Gainers outnumbered losers 5 to 3'', which is a more accurate approximation to what really happened. After all, the exact ratio of winners to losers is (to the nearest millionth) 1.660754, and he reported a ratio of 14 to 9, which is 1.555555, for an error of 0.105199; he could have said ``5 to 3'', and introduced an error of only 1.666667-1.660754=0.005913. The estimate ``5 to 3'' is not as accurate as ``1498 to 902'' of course; evidently, another goal is to use small integers to express the ratio. So, why did the anchorperson say ``14 to 9?'' Because his algorithm is to lop off the last two digits of each number and use those as the approximate ratio.
What the anchorman needs is a list of rational approximations of increasing accuracy, so that he can pick one to read on the air. Specifically, he needs a sequence {a_1, a_2, ..., a_n} where a_1 is a rational number with denominator 1 that most exactly matches the true ratio of winners to losers (rounding up in case of ties), a_{i+1} is the rational number with least denominator that provides a more accurate approximation than a_i, and a_n is the exact ratio, expressed with the least possible denominator. Given this sequence, the anchorperson can decide which ratio gives the best tradeoff between accuracy and simplicity.
For example, if 5 stocks rose in price and 4 fell, the best approximation with denominator 1 is 1/1; that is, for every stock that fell, about one rose. This answer differs from the exact answer by 0.25 (1.0 vs 1.25). The best approximations with two in the denominator are 2/2 and 3/2, but neither is an improvement on the ratio 1/1, so neither would be considered. The best approximation with three in the denominator 4/3, is more accurate than any seen so far, so it is one that should be reported. Finally, of course, 5/4 is exactly the ratio, and so it is the last number reported in the sequence.
Can you automate this process and help the anchorpeople?
The approximations for a pair are printed one to a line, beginning in
column one, with the numerator and denominator of an approximation separated
by a slash (``/''). A blank line separates one sequence of approximations
from another.
2/1
3/2
5/3
48/29
53/32
58/35
63/38
68/41
73/44
78/47
83/50
88/53
93/56
377/227
470/283
563/339
656/395
749/451
int main()
{
int firsttime = 1;
ifstream fin("ratio.inp");
int G, L;
while (fin >> G >> L)
{
if (!firsttime) cout << "\n";
firsttime = 0;
double exact = (double)G/L;
double bestapprox = floor(exact + 0.5);
cout << bestapprox << "/1\n";
for (unsigned i = 2; i <= L; ++i)
{
int estG = exact
* i + 0.5;
double approx
= (double)estG / i;
if (fabs(approx-exact)
< fabs(bestapprox-exact))
{
bestapprox = approx;
cout << estG << "/" << i << "\n";
if (bestapprox == exact)
break;
}
}
}
return 0;
}
2/1
3/2
5/3
48/29
53/32
58/35
63/38
68/41
73/44
78/47
83/50
88/53
93/56
377/227
470/283
563/339
656/395
749/451
1/1
1/2
1/1
1/2
1/1
1/2
2/3
3/5
5/8
8/13
13/21
21/34
34/55
55/89
89/144
144/233
233/377
377/610
610/987
987/1597
1597/2584
287/1
575/2
862/3
1/1
501/500
502/501
503/502
504/503
505/504
506/505
507/506
508/507
509/508
510/509
511/510
512/511
513/512
514/513
515/514
516/515
517/516
518/517
519/518
520/519
521/520
522/521
523/522
524/523
525/524
526/525
527/526
528/527
529/528
530/529
531/530
532/531
533/532
534/533
535/534
536/535
537/536
538/537
539/538
540/539
541/540
542/541
543/542
544/543
545/544
546/545
547/546
548/547
549/548
550/549
551/550
552/551
553/552
554/553
555/554
556/555
557/556
558/557
559/558
560/559
561/560
562/561
563/562
564/563
565/564
566/565
567/566
568/567
569/568
570/569
571/570
572/571
573/572
574/573
575/574
576/575
577/576
578/577
579/578
580/579
581/580
582/581
583/582
584/583
585/584
586/585
587/586
588/587
589/588
590/589
591/590
592/591
593/592
594/593
595/594
596/595
597/596
598/597
599/598
600/599
601/600
602/601
603/602
604/603
605/604
606/605
607/606
608/607
609/608
610/609
611/610
612/611
613/612
614/613
615/614
616/615
617/616
618/617
619/618
620/619
621/620
622/621
623/622
624/623
625/624
626/625
627/626
628/627
629/628
630/629
631/630
632/631
633/632
634/633
635/634
636/635
637/636
638/637
639/638
640/639
641/640
642/641
643/642
644/643
645/644
646/645
647/646
648/647
649/648
650/649
651/650
652/651
653/652
654/653
655/654
656/655
657/656
658/657
659/658
660/659
661/660
662/661
663/662
664/663
665/664
666/665
667/666
668/667
669/668
670/669
671/670
672/671
673/672
674/673
675/674
676/675
677/676
678/677
679/678
680/679
681/680
682/681
683/682
684/683
685/684
686/685
687/686
688/687
689/688
690/689
691/690
692/691
693/692
694/693
695/694
696/695
697/696
698/697
699/698
700/699
701/700
702/701
703/702
704/703
705/704
706/705
707/706
708/707
709/708
710/709
711/710
712/711
713/712
714/713
715/714
716/715
717/716
718/717
719/718
720/719
721/720
722/721
723/722
724/723
725/724
726/725
727/726
728/727
729/728
730/729
731/730
732/731
733/732
734/733
735/734
736/735
737/736
738/737
739/738
740/739
741/740
742/741
743/742
744/743
745/744
746/745
747/746
748/747
749/748
750/749
751/750
752/751
753/752
754/753
755/754
756/755
757/756
758/757
759/758
760/759
761/760
762/761
763/762
764/763
765/764
766/765
767/766
768/767
769/768
770/769
771/770
772/771
773/772
774/773
775/774
776/775
777/776
778/777
779/778
780/779
781/780
782/781
783/782
784/783
785/784
786/785
787/786
788/787
789/788
790/789
791/790
792/791
793/792
794/793
795/794
796/795
797/796
798/797
799/798
800/799
801/800
802/801
803/802
804/803
805/804
806/805
807/806
808/807
809/808
810/809
811/810
812/811
813/812
814/813
815/814
816/815
817/816
818/817
819/818
820/819
821/820
822/821
823/822
824/823
825/824
826/825
827/826
828/827
829/828
830/829
831/830
832/831
833/832
834/833
835/834
836/835
837/836
838/837
839/838
840/839
841/840
842/841
843/842
844/843
845/844
846/845
847/846
848/847
849/848
850/849
851/850
852/851
853/852
854/853
855/854
856/855
857/856
858/857
859/858
860/859
861/860
862/861
863/862
864/863
865/864
866/865
867/866
868/867
869/868
870/869
871/870
872/871
873/872
874/873
875/874
876/875
877/876
878/877
879/878
880/879
881/880
882/881
883/882
884/883
885/884
886/885
887/886
888/887
889/888
890/889
891/890
892/891
893/892
894/893
895/894
896/895
897/896
898/897
899/898
900/899
901/900
902/901
903/902
904/903
905/904
906/905
907/906
908/907
909/908
910/909
911/910
912/911
913/912
914/913
915/914
916/915
917/916
918/917
919/918
920/919
921/920
922/921
923/922
924/923
925/924
926/925
927/926
928/927
929/928
930/929
931/930
932/931
933/932
934/933
935/934
936/935
937/936
938/937
939/938
940/939
941/940
942/941
943/942
944/943
945/944
946/945
947/946
948/947
949/948
950/949
951/950
952/951
953/952
954/953
955/954
956/955
957/956
958/957
959/958
960/959
961/960
962/961
963/962
964/963
965/964
966/965
967/966
968/967
969/968
970/969
971/970
972/971
973/972
974/973
975/974
976/975
977/976
978/977
979/978
980/979
981/980
982/981
983/982
984/983
985/984
986/985
987/986
988/987
989/988
990/989
991/990
992/991
993/992
994/993
995/994
996/995
997/996
998/997
999/998
1000/999