Cody

# Problem 1900. GJam 2014 China Rd A: Rational Number Tree (Large Values)

Solution 1694186

Submitted on 17 Dec 2018 by William
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

### Test Suite

Test Status Code Input and Output
1   Pass
tic v=[ 2081355757 4898583766 ]; vexp=[uint64(11412103587704585708) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

2   Pass
v=[ 385960903003 298051413714 ]; vexp=[uint64(13079621846505187505) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

3   Pass
v=[uint64(15477096172227810860) ]; vexp=[ 188445238409 450375998772 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

4   Pass
v=[uint64( 6473043965665514375) ]; vexp=[ 109230282567 33788952110 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

5   Pass
v=[uint64(11270280438309969755) ]; vexp=[ 23328302733 8557676614 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

6   Pass
v=[ 6893018069 8719066441 ]; vexp=[uint64( 1875942192845872366) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

7   Pass
v=[uint64( 6566840053865194126) ]; vexp=[ 65441249939 85425641391 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

8   Pass
v=[ 21562167101 16520535073 ]; vexp=[uint64( 956959952027690353) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

9   Pass
v=[ 1684200303 7336396097 ]; vexp=[uint64( 871479491406563248) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

10   Pass
v=[uint64( 2524835851416755114) ]; vexp=[ 28589000023 46221104912 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

11   Pass
v=[ 154908421282 199691474905 ]; vexp=[uint64( 7885684695614904270) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

12   Pass
v=[uint64( 8176570117722182781) ]; vexp=[ 40721598494 22123450931 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

13   Pass
v=[uint64( 9379940828518631730) ]; vexp=[ 37341631466 63773070917 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

14   Pass
v=[ 232141051889 328442531011 ]; vexp=[uint64( 9972945692012784742) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

15   Pass
v=[uint64( 9539984397959825908) ]; vexp=[ 70384313011 178968141063 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

16   Pass
v=[ 421484284721 599703187188 ]; vexp=[uint64(17162693345262485798) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

17   Pass
v=[ 127506314007 35528864794 ]; vexp=[uint64( 4167185002280551319) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

18   Pass
v=[ 11313093168 21049073135 ]; vexp=[uint64(16014443480831614722) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

19   Pass
v=[uint64( 7450646608300783266) ]; vexp=[ 83429116694 148768825269 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

20   Pass
v=[uint64(13305041571212833467) ]; vexp=[ 77301627056 27774083789 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

21   Pass
v=[uint64(13635447149676152154) ]; vexp=[ 90797761304 143479563807 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

22   Pass
v=[uint64(11002893257806672560) ]; vexp=[ 44637053272 195624712811 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

23   Pass
v=[uint64(11051724027090761936) ]; vexp=[ 41361095819 189799709732 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

24   Pass
v=[uint64(16687200783289968235) ]; vexp=[ 552258283575 209936061221 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

25   Pass
v=[ 54164851566 156315474505 ]; vexp=[uint64(13714337615447966724) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

26   Pass
v=[uint64( 7329431770178715643) ]; vexp=[ 13299036287 4535592331 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

27   Pass
v=[uint64(16479631524350748877) ]; vexp=[ 165234451641 96812407705 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

28   Pass
v=[uint64( 6965988866158891263) ]; vexp=[ 21216614218 2585039947 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

29   Pass
v=[uint64( 2910455928437551420) ]; vexp=[ 6642417815 14808129701 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

30   Pass
v=[ 13173276049 27570716815 ]; vexp=[uint64( 4977980945016614908) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

31   Pass
v=[uint64(16721022657493559975) ]; vexp=[ 65473107451 19359384006 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

32   Pass
v=[ 16946040975 10725070912 ]; vexp=[uint64( 6003309882203701925) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

33   Pass
v=[uint64( 2198342485367409266) ]; vexp=[ 23006488657 39032588924 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

34   Pass
v=[ 120013217139 50302005308 ]; vexp=[uint64(14344732783514005715) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

35   Pass
v=[ 57191814347 77886936688 ]; vexp=[uint64( 8056110860202858614) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

36   Pass
v=[uint64( 971778736353519486) ]; vexp=[ 17760921544 20384041659 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

37   Pass
v=[ 129560016431 165770554719 ]; vexp=[uint64(15111464173338859822) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

38   Pass
v=[uint64(17855284157674478998) ]; vexp=[ 215281025997 298483051015 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

39   Pass
v=[ 8822618162 5678585885 ]; vexp=[uint64( 4934822377188433797) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

40   Pass
v=[uint64( 632138406214928188) ]; vexp=[ 1835073727 4084131059 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

41   Pass
v=[uint64(17330627945660580534) ]; vexp=[ 41195382388 56325602793 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

42   Pass
v=[ 6130953526 13549540271 ]; vexp=[uint64( 1896894898836571068) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

43   Pass
v=[ 25774822611 36694510870 ]; vexp=[uint64(15996304402734859814) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

44   Pass
v=[uint64( 9847540446768144862) ]; vexp=[ 31041969169 37560295989 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

45   Pass
v=[uint64(16612432143632526945) ]; vexp=[ 74531365158 60753898717 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

46   Pass
v=[uint64(18413647273680019461) ]; vexp=[ 10651217970 6995653927 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

47   Pass
v=[ 62279662838 47373225825 ]; vexp=[uint64( 9640047776936252913) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

48   Pass
v=[uint64(16583979163800903818) ]; vexp=[ 114249431453 187605944484 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

49   Pass
v=[ 9050571726 1557293089 ]; vexp=[uint64( 9060257062169994207) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

50   Pass
v=[uint64(12613321696385576431) ]; vexp=[ 125835757545 26079146381 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

51   Pass
v=[ 35625689704 19896848117 ]; vexp=[uint64( 4411487194398480861) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

52   Pass
v=[uint64( 3484689439967270015) ]; vexp=[ 38461243033 5285269728 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

53   Pass
v=[ 16085645428 43823408873 ]; vexp=[uint64( 894482490922679460) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

54   Pass
v=[uint64(12060487473657709988) ]; vexp=[ 250877787515 682594856898 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

55   Pass
v=[ 143931327293 76531069545 ]; vexp=[uint64(12786697318005254653) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

56   Pass
v=[uint64(14215963369683634045) ]; vexp=[ 100316121935 54160354223 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

57   Pass
v=[ 6557653153 12053301655 ]; vexp=[uint64( 343376420813762434) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

58   Pass
v=[ 47494216762 112901758075 ]; vexp=[uint64( 3772080181899583404) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

59   Pass
v=[uint64( 6766488059228584288) ]; vexp=[ 8189923863 44106320581 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

60   Pass
v=[ 41526542352 17027036567 ]; vexp=[uint64(17583140790467836275) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

61   Pass
v=[ 7196361275 6496875429 ]; vexp=[uint64( 6443574928762444801) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

62   Pass
v=[uint64(17365843048376429107) ]; vexp=[ 18457341831 7658711707 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

63   Pass
v=[ 78140576077 33767545674 ]; vexp=[uint64( 6098897546038113251) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

64   Pass
v=[ 6734445697 12144787423 ]; vexp=[uint64( 4770215408132554690) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

65   Pass
v=[ 426726665699 126968827572 ]; vexp=[uint64(12995540462042527271) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

66   Pass
v=[uint64( 5523416580603863552) ]; vexp=[ 4255700693 41585972826 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

67   Pass
v=[uint64( 3928457774057619184) ]; vexp=[ 3877602413 16306596859 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

68   Pass
v=[ 136097916108 28801327007 ]; vexp=[uint64( 5984770176263773551) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

69   Pass
v=[uint64(16263054952801281548) ]; vexp=[ 14189368539 34874268638 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

70   Pass
v=[ 662028875555 839442017139 ]; vexp=[uint64(11859750004469197678) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

71   Pass
v=[ 61393402621 332298132605 ]; vexp=[uint64( 7879625004656522848) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

72   Pass
v=[ 1998630709 8715852076 ]; vexp=[uint64( 429234479783941040) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

73   Pass
v=[ 46021740257 21715449429 ]; vexp=[uint64(14347105153381215235) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

74   Pass
v=[uint64( 498971859648614985) ]; vexp=[ 30472124134 22307121041 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

75   Pass
v=[uint64( 6396162213707057064) ]; vexp=[ 26683188512 96283024611 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

76   Pass
v=[ 46925294325 33937979441 ]; vexp=[uint64( 1189627028589296041) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

77   Pass
v=[ 76315837293 99424320902 ]; vexp=[uint64(11656949174638158734) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

78   Pass
v=[ 81880058662 38464981613 ]; vexp=[uint64( 7071867154613101059) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

79   Pass
v=[uint64(10763027175299443277) ]; vexp=[ 330973468653 194345162402 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

80   Pass
v=[ 79087591419 23535674032 ]; vexp=[uint64(15017024826981320231) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

81   Pass
v=[ 241564818347 155909390759 ]; vexp=[uint64(15575297637481852549) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

82   Pass
v=[ 45079186819 295776092742 ]; vexp=[uint64(16532545499676710720) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

83   Pass
v=[ 22268771423 34477255167 ]; vexp=[uint64(11007510539515659130) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

84   Pass
v=[uint64( 5666822869473456046) ]; vexp=[ 28640204779 36488487629 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

85   Pass
v=[uint64(14041232599151835393) ]; vexp=[ 28442192536 25169506635 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

86   Pass
v=[uint64( 9611808239041397120) ]; vexp=[ 1055826287 7876555270 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

87   Pass
v=[ 358405360794 498368744795 ]; vexp=[uint64( 4955841772239017238) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

88   Pass
v=[uint64( 3979638765694296062) ]; vexp=[ 6903410593 7465748396 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

89   Pass
v=[ 151761015812 211325030677 ]; vexp=[uint64( 7987025462351843862) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

90   Pass
v=[ 325266071703 87446899892 ]; vexp=[uint64(16944641327505127607) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

91   Pass
v=[uint64( 3273057505586617135) ]; vexp=[ 124425395619 27124979723 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

92   Pass
v=[ 142722642746 60293518411 ]; vexp=[uint64(10857549622062058131) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

93   Pass
v=[ 379488415355 462240655923 ]; vexp=[uint64(16693497308621268574) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

94   Pass
v=[uint64( 5336487237226370963) ]; vexp=[ 76728175571 32349586492 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

95   Pass
v=[ 366909173981 111494050923 ]; vexp=[uint64(11044880014193584327) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

96   Pass
v=[uint64( 2767480983943234275) ]; vexp=[ 155407720950 67429662431 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

97   Pass
v=[ 4375152441 11923449250 ]; vexp=[uint64(14458798758395123876) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

98   Pass
v=[ 107946470399 33010545783 ]; vexp=[uint64(13708745226178508359) ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

99   Pass
v=[uint64( 546205200272961984) ]; vexp=[ 1773793574 11180737745 ]; vout=Tree_CH(v); assert(isequal(vout,vexp))

100   Pass
v=[uint64( 6791165959744564855) ]; vexp=[ 125726750555 33307435529 ]; vout=Tree_CH(v); assert(isequal(vout,vexp)) toc

Elapsed time is 1.863045 seconds.

101   Pass
% Read of GJam 64 bit data % function z = read_input64(fn) % fid=fopen(fn); % u=textscan(fid,'%u64'); % fclose(fid); % vptr=2; % skip Test case count % dptr=1; % while vptr<size(u{1},1) % if u{1}(vptr)==1 % single N % z{dptr}=u{1}(vptr+1); % vptr=vptr+2; % else % Pair for p/q % z{dptr}=[u{1}(vptr+1) u{1}(vptr+2)]; % vptr=vptr+3; % end % dptr=dptr+1; % end % end %Typical GJam 64 bit data % 100 % 2 2081355757 4898583766 % 2 385960903003 298051413714 % 1 15477096172227810860 % 1 6473043965665514375 % 1 11270280438309969755 % 2 6893018069 8719066441 % 1 6566840053865194126 % 2 21562167101 16520535073 % 2 1684200303 7336396097 % 1 2524835851416755114 % 2 154908421282 199691474905

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!