SelfCatalogue | Topcoder Archive

Problem Statement

A self-catalogue is a sentence that truthfully and comprehensively describes its own composition. In this problem, we are concerned with sentences that count numerals occurring in themselves, such as the following.

This sentence contains 1 occurrence of 0, 2 occurrences of 1, 3 occurrences of 2, and 2 occurrences of 3.

The above is a self-catalogue because it gives an accurate count for each numeral occurring in itself. The following sentence, although accurate in the counts that it gives, is not a self-catalogue because it does not give a count for the numeral 3.

This sentence contains 3 occurrences of 1, 1 occurrence of 8, and 1 occurrence of 9.

A self-catalogue must not give more than one count for the same numeral. Thus, the following is not a self-catalogue.

This sentence contains 4 occurrences of 4, and 4 occurrences of 4.

Given a int[] specifying a count for each of the numerals 0 through 9, try to find a self-catalogue that agrees with these counts. A count of 0 means that the numeral does not appear in the sentence at all, and a specified count of -1 means that any count (including 0) is acceptable. If there is no sentence meeting this specification, return an empty int[]. Otherwise, return a int[] of the same size as the input and containing the same non-negative counts, but with each -1 replaced by an accurate count. If several self-catalogues are possible, choose the one that yields the smallest value in element 0 of the result. If a tie remains, select for the smallest value in element 1; if there is still a tie, select for the smallest value in element 2; and so forth.

Definition

Class:: SelfCatalogue
Method:: construct
Parameters:: int[]
Returns:: int[]
Method signature:: int[] construct(int[] counts)
(be sure your method is public)

Notes

Leading zeros are not permitted for any number appearing in a self-catalogue.

Constraints

counts contains exactly 10 elements.
Each element of counts is between -1 and 100, inclusive.

Examples

```
{1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
```
```
Returns: {1, 2, 3, 2, 0, 0, 0, 0, 0, 0 }
```
The first sentence from the problem statement satisfies the input specification that there be exactly one occurrence of the numeral 0: This sentence contains 1 occurrence of 0, 2 occurrences of 1, 3 occurrences of 2, and 2 occurrences of 3.
```
{100, -1, -1, -1, -1, -1, -1, -1, -1, -1}
```
```
Returns: { }
```
It is impossible to make a self-catalogue with 100 zeros.

{1, 11, -1, -1, -1, -1, -1, -1, -1, -1}

Returns: {1, 11, 0, 1, 1, 1, 1, 1, 1, 1 }

Note that 11 contains two occurrences of 1.

```
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
```
```
Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
```
The following self-catalogue illustrates this degenerate case: This is a sentence.

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.