AlicesBirthday

SRM 790 · 2020-09-09 · by nikhil_chandak

SRM 790 · 2020-09-09 · by nikhil_chandak · Brute Force

Show categories

Class Name: AlicesBirthday

Return Type: int[]

Method Name: partition

Arg Types: (int)

Problem Statement

Alice has invited her two best friends, Charlie and Eric, to her birthday party. She has K boxes containing gifts for them. The boxes are numbered from 1 to K. For each i, box number i contains F_i gifts, where F_i is the i^th Fibonacci number. (F₁ = 1, F₂ = 1, and for each i > 2, F_i = F_{i - 1} + F_{i - 2}.)

Alice likes both of her friends equally, so she wants to distribute these K boxes between them in such a way that both of them get an equal total number of gifts. If that is possible, return a int[] containing box numbers which one of the two friends should receive. Note that all the boxes not chosen for this friend automatically go to the other friend. If there are multiple answers, you may return any of them.

If there is no solution, return the int[] {-1} instead i.e. an array with -1 as its only element.

Notes

The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, ...

Constraints

K will be between 1 and 40, inclusive.

Examples

3
Returns: {3 }

There are K = 3 boxes containing gifts. Box 1 contains F1 = 1 gift, box 2 contains F2 = 1 gift, and box 3 contains F3 = 2 gifts. Giving boxes #1 and #2 to Charlie and box #3 to Eric means that each of them receives two gifts. The returned array represents the numbers of the boxes received by Eric in this solution. {1, 2} and {2, 1} are two other valid return values for this test case.

5
Returns: {5, 1 }

F1 + F5 = 1 + 5 = 6. F2 + F3 + F4 = 1 + 2 + 3 = 6.

1
Returns: {-1 }

Since there is only one box containing a single gift, there is no way for Charlie and Eric to have an equal number of gifts.

8
Returns: {8, 5, 1 }

23
Returns: {23, 20, 17, 14, 11, 8, 5, 1 }

Submissions are judged against all 18 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AlicesBirthday with a public method vector<int> partition(int k) · 18 test cases · 2 s / 256 MB per case