Connection Status:
Competition Arena > SelfCatalogue

SelfCatalogue

SRM 254 · 2005-07-26 · by lbackstrom

SRM 254 · 2005-07-26 · by lbackstrom · Brute Force, Recursion
Class Name: SelfCatalogue
Return Type: int[]
Method Name: construct
Arg Types: (vector<int>)
Problem Statement

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.

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
0)
{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.

1)
{100, -1, -1, -1, -1, -1, -1, -1, -1, -1}
Returns: { }

It is impossible to make a self-catalogue with 100 zeros.

2)
{1, 7, 3, -1, -1, -1, -1, -1, -1, -1}
Returns: {1, 7, 3, 2, 1, 1, 1, 2, 1, 1 }

This sentence contains 1 occurrence of 0, 7 occurrences of 1, 3 occurrences of 2, 2 occurrences of 3, 1 occurrence of 4, 1 occurrence of 5, 1 occurrence of 6, 2 occurrences of 7, 1 occurrence of 8, and 1 occurrence of 9.

3)
{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.

4)
{-1, 11, -1, -1, -1, -1, -1, -1, -1, -1}
Returns: {0, 11, 1, 1, 1, 1, 1, 1, 1, 1 }
12)
{-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.

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

Coding Area

Language: C++17 · define a public class SelfCatalogue with a public method vector<int> construct(vector<int> counts) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous