+/foobar

google programming puzzles

git clone https://git.julia.blue/+/foobar

Joseph RyanI made it2e1d345

master
2.5 KiB170 linesraw
1The Grandest Staircase Of Them All
2==================================
3
4With her LAMBCHOP doomsday device finished, Commander Lambda is preparing for her debut on the galactic stage - but in order to make a grand entrance, she needs a grand staircase! As her personal assistant, you've been tasked with figuring out how to build the best staircase EVER. 
5
6Lambda has given you an overview of the types of bricks available, plus a budget. You can buy different amounts of the different types of bricks (for example, 3 little pink bricks, or 5 blue lace bricks). Commander Lambda wants to know how many different types of staircases can be built with each amount of bricks, so she can pick the one with the most options. 
7
8Each type of staircase should consist of 2 or more steps.  No two steps are allowed to be at the same height - each step must be lower than the previous one. All steps must contain at least one brick. A step's height is classified as the total amount of bricks that make up that step.
9For example, when N = 3, you have only 1 choice of how to build the staircase, with the first step having a height of 2 and the second step having a height of 1: (# indicates a brick)
10
11#
12##
1321
14
15When N = 4, you still only have 1 staircase choice:
16
17#
18#
19##
2031
21 
22But when N = 5, there are two ways you can build a staircase from the given bricks. The two staircases can have heights (4, 1) or (3, 2), as shown below:
23
24#
25#
26#
27##
2841
29
30#
31##
32##
3332
34
35Write a function called answer(n) that takes a positive integer n and returns the number of different staircases that can be built from exactly n bricks. n will always be at least 3 (so you can have a staircase at all), but no more than 200, because Commander Lambda's not made of money!
36
37Languages
38=========
39
40To provide a Python solution, edit solution.py
41To provide a Java solution, edit solution.java
42
43Test cases
44==========
45
46Inputs:
47    (int) n = 3
48Output:
49    (int) 1
50
51Inputs:
52    (int) n = 200
53Output:
54    (int) 487067745
55
563:
572,1
58
594:
603,1
61
625:
633,2
644,1
65
666:
675,1
684,2
693,2,1
70
717:
726,1
735,2
744,3
754,2,1
76
778:
787,1
796,2
805,3
815,2,1
824,3,1
83
849:
858,1
867,2
876,3
886,2,1
895,4
905,3,1
914,3,2
92
9310:
949,1
958,2
967,3
977,2,1
986,4
996,3,1
1005,4,1
1015,3,2
1024,3,2,1
103
10411:
10510,1
1069,2
1078,3
1088,2,1
1097,4
1107,3,1
1116,5
1126,4,1
1136,3,2
1145,4,2
1155,3,2,1
116
11712:
11811,1
11910,2
1209,3
1219,2,1
1228,4
1238,3,1
1247,5
1257,4,1
1267,3,2
1276,3,2,1
1285,4,2,1
129
13013:
13112,1
13211,2
13310,3
13410,2,1
1359,4
1369,3,1
1378,5
1388,4,1
1398,3,2
1407,6
1417,5,1
1427,4,2
1437,3,2,1
1446,5,2
1456,4,3
1466,4,2,1
1475,4,3,1
148
14914:
15013,1
15112,2
15211,3
15311,2,1
15410,4
15510,3,1
1569,5
1579,4,1
1589,3,2
1598,6
1608,5,1
1618,4,2
1628,3,2,1
1637,6,1
1647,5,2
1657,4,3
1667,4,2,1
1676,5,3
1686,5,2,1
1696,4,3,1
170