StockHistory
SRM 232 · 2005-02-23 · by lbackstrom
Problem Statement
You have recently been given a one-time bonus at work, along with a pay raise. In the interest of putting your new found money to good use, you have decided to invest in the stock market. To learn about recent market history, you have acquired historical data on several stocks you might be interested in purchasing.
For experiment's sake, you want to evaluate the potential performance of your selected stocks. What you are wondering is how much money you could have made if, at the beginning, you had an initial investment of
You are given a
You are to return an
Constraints
- initialInvestment will be between 0 and 10000, inclusive.
- monthlyContributon will be between 0 and 1000, inclusive.
- stockPrices will contain between 2 and 50 elements, inclusive.
- Each element of stockPrices will contain between 1 and 50 characters, inclusive.
- Each element of stockPrices will be formatted as a space delimited list of positive integers.
- Each integer represented in an element of stockPrices will be between 1 and 999, inclusive.
- Each element of stockPrices will represent the same number of integers.
- The result prior to rounding will not be within 0.01 of x.5, where x is an integer.
1000
0
{"10 20 30", "15 24 32"}
Returns: 500
Clearly the first stock is a bigger gain than either of the others. We go all in on it.
1000
0
{"10", "9"}
Returns: 0
We're best off not buying any shares, rather than buying and losing money.
100
20
{"40 50 60",
"37 48 55",
"100 48 50",
"105 48 47",
"110 50 52",
"110 50 52",
"110 51 54",
"109 49 53"}
Returns: 239
Remember that we can't sell any shares until the beginning of the last month. So, let's work backwards, and figure out what the best way to invest our money is. During the second to last month (month 6), the stock prices are 110, 51 and 54, all higher than the prices that we would sell at, so we don't buy anything during that month. At the beginning of month 5, the price of the third stock is a little lower than its final price, so we invest our 20 in that, and make a meager 20*((53/52)-1). The prices are the same at the beginning of month 4, so we do the same thing. At the beginning of month 3, the prices have changed, but it is still best to invest in the third stock. Note that the profit we make investing in the third stock during month 3 is larger than it is if we save our money and invest later. Hence, we make a profit of 20*((53/47)-1) on our 20 from month 3. At the beginning of month 2, it is best to save all of our money, and then invest in the third stock during the next month when the price is lower. At the beginning of month 1, you should clearly invest in the first stock. You should save all of your money from the initial investment until the price of the first stock goes down a little. So, to summarize: month | action ------+------- 0 | save 1 | buy stock 0 (120/37 shares) 2 | save 3 | buy stock 2 (40/47 shares) 4 | buy stock 2 (20/52 shares) 5 | buy stock 2 (20/52 shares) 6 | save 7 | sell (3.243 shares of stock 0, 1.620 shares of stock 2) Total sales price : 439.389 Total investment : 200 Profit : 239.389 Notice that you always either invest all of your money at the beginning of a month, or else save all of it. When you know the future prices, there is no reason to invest only some of your money.
1616
689
{"708 683 777 381 103 776 924 909","851 777 429 124 280 525 338 187","963 104 962 484 808 610 573 516","376 170 355 37 464 202 613 447","934 937 221 434 789 178 330 859","502 321 317 906 591 616 989 462","454 688 40 763 442 298 746 288","186 360 927 892 180 208 145 204","604 110 158 259 409 35 622 399","635 665 50 406 998 669 5 895","717 207 562 955 585 705 10 41","306 867 796 108 69 941 744 11","374 233 492 139 116 876 208 310","906 844 532 905 658 216 789 270","407 692 437 343 395 364 768 554","394 724 869 962 288 933 815 648","899 338 133 354 67 236 492 371","973 886 671 686 726 786 749 367","182 175 569 206 27 806 430 609","105 960 52 738 993 716 766 898","837 456 983 185 419 642 882 366","492 825 373 28 359 913 293 966","697 686 865 825 637 561 401 987","95 609 249 716 343 820 4 543","843 618 952 913 328 628 785 74","119 691 544 213 713 128 824 850","609 257 233 484 384 162 87 472","21 700 369 178 490 777 931 363","575 856 944 821 949 725 606 278","509 515 90 522 943 960 750 800","574 919 576 462 421 138 893 841","539 265 318 404 593 118 957 138","687 201 866 190 441 464 751 758","319 328 917 236 209 942 478 597","248 703 803 41 905 22 229 878","305 335 1 677 808 374 487 651","837 682 625 299 958 376 627 297","206 163 932 637 662 605 412 23","288 641 820 501 993 344 497 363","976 940 325 278 291 77 927 683","680 334 126 432 657 992 640 674","824 49 42 7 462 481 960 856","349 764 532 126 842 636 106 79","208 115 196 486 198 757 685 16","874 186 276 867 694 844 196 672","833 18 152 625 764 100 528 881","88 103 845 194 607 430 461 804","657 887 521 585 684 947 165 429","74 270 979 889 226 463 701 72","886 102 168 775 725 992 522 878"}
Returns: 4863440
4258
70
{"444 257 968 323 979 290 205","855 907 177 774 704 935 616","146 777 408 379 563 654 641","331 996 735 501 692 348 629","226 554 903 790 510 646 35","414 830 354 155 577 24 978","918 624 116 257 678 812 397","126 186 201 754 737 544 789","247 728 413 913 936 728 460","880 961 132 67 861 868 111","277 34 190 882 5 969 271","223 485 277 349 232 977 493","880 353 717 218 121 633 122","514 950 244 244 539 953 243","469 443 747 592 477 504 560","421 439 520 57 545 472 452","420 231 343 311 677 207 421","302 278 937 882 211 922 132","160 50 643 511 649 943 126","827 662 271 293 125 627 59","131 256 545 618 767 652 689","437 800 332 564 322 874 173","100 786 511 423 116 692 187","469 14 142 657 849 738 615","542 524 976 366 148 386 610","57 546 28 423 653 905 759","50 561 67 870 182 22 372","150 17 748 740 646 968 819","1 689 611 818 467 153 891","224 764 966 574 50 913 889","949 738 650 520 786 299 12","561 532 696 160 342 770 498","460 574 918 758 811 378 188","162 221 539 779 412 638 29","343 878 25 768 676 476 690","644 679 816 865 777 559 594","532 32 282 225 502 785 272","739 744 947 374 925 962 216","48 713 424 603 823 822 37","195 8 646 681 165 635 397","783 49 669 494 145 250 457","208 24 810 434 544 457 427","76 392 846 715 100 908 777","722 920 165 106 700 352 31","280 113 560 320 921 907 267","180 654 28 203 729 180 180","811 953 606 850 200 841 30","566 345 779 357 417 542 186","388 816 114 410 143 518 360","867 438 884 759 430 717 396"}
Returns: 5440815
Submissions are judged against all 19 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StockHistory with a public method int maximumEarnings(int initialInvestment, int monthlyContribution, vector<string> stockPrices) · 19 test cases · 2 s / 256 MB per case