Problem 3

[Back]

The elves successfully solve the windows puzzle, and move on to another building. This one seems to have numbered rooms. A lot of numbered rooms. Before you know it, the elves start exploring the building and end up in all sorts of places. You think they can find their way back, but you're not sure, and anyway, some of them might have found something useful. Best to try to figure out where they all are.

After a while, you manage to figure out that the elves started in some group of rooms. Then, for some number of steps, some of the elves in Room x went to Room 3x + 1, and, for even x, some of them also went to Room x / 2. (Some just stayed in Room x, though.) After this number of steps, the elves got tired of moving around and stayed where they were. There are enough elves that any room that could have elves with these rules, does have elves. You want to start by figuring out how many rooms have elves.

For example, if your input were:
2 8 3 5 10 9
Steps: 10
then that would mean elves were initially in rooms 2, 3, 5, 8, 9, and 10, and would take up to 10 steps before getting tired. After one step, elves would be in rooms 1, 2, 3, 4, 5, 7, 8, 9, 10, 16, 25, 28, and 31. After two steps, elves would be in rooms 1, 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 16, 22, 25, 28, 31, 49, 76, 85, and 94. After 10 steps, elves would be in 439 rooms, with the maximum being 620014. (There seems to be no limit to possible room numbers.) So your output is 439 rooms.

To begin, get your problem input. You feel that this problem will take 5 lines of code.

Answer: [Submit]