TheFoxZoo | Topcoder Archive

Problem Statement

Fox Ciel was hiding in a forest from two brave hunters John and Brus for a long time. Eventually, they caught her, together with some other foxes. Now John and Brus have foxCount foxes and they would like to open a fox zoo in their home city. They are going to put the foxes into cages. Since they are extremely kind to foxes, they won't put more than foxLimit foxes in a single cage. On the other hand, they don't have much money, so they want to minimize the number of cages in the zoo.

The brave hunters believe that if the total number of cages or the number of foxes in some cage is divisible by 4 or 7 (the lucky digits) then the foxes will be lucky enough to escape from the zoo. Of course, they want to prevent this from happening. More formally, if there are n cages in a zoo numbered from 0 to n-1 and the i-th cage contains x[i] foxes, then:

n shouldn't be divisible by 4;
n shouldn't be divisible by 7;
each x[i] shouldn't be divisible by 4;
each x[i] shouldn't be divisible by 7;
each x[i] should be between 1 and foxLimit, inclusive;
the sum of all x[i] should be equal to foxCount;
n should be as small as possible.

You are given the ints foxCount and foxLimit. If it's impossible to satisfy the requirements, return an empty int[], else return a int[] containing n elements. The i-th element should be x[i]. If there are multiple possible answers, return the lexicographically smallest one. If n is greater than 47, return just the first 47 elements of x.

Definition

Class:: TheFoxZoo
Method:: find
Parameters:: int, int
Returns:: int[]
Method signature:: int[] find(int foxNumber, int foxLimit)
(be sure your method is public)

Constraints

foxNumber will be between 1 and 1,000,000,000, inclusive.
foxLimit will be between 1 and 1,000,000,000, inclusive.

Examples

```
16
```
```
3
```
```
Returns: {1, 3, 3, 3, 3, 3 }
```
A greedy approach works for this test case. All cages, except for the first one, will contain exactly foxLimit foxes.
```
14
```
```
1
```
```
Returns: { }
```
Since each cage can contain only one fox, there should be 14 cages and this number is obviously divisible by 7. So it's impossible to achieve our goal here.
```
37
```
```
7
```
```
Returns: {1, 1, 1, 5, 5, 6, 6, 6, 6 }
```
If John and Brus were to distribute the foxes greedily, they would need 7 cages. However, they want to avoid using 7 cages (divisible by 7) or 8 cages (divisible by 4). So the smallest valid number of cages is 9. The return value shows the lexicographically smallest acceptable way of filling 9 cages.

Returns: {1, 17, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.