InputBoxChecker

SRM 310 · 2006-07-06 · by misof

SRM 310 · 2006-07-06 · by misof · Greedy, Simple Math

Show categories

Class Name: InputBoxChecker

Return Type: String[]

Method Name: checkPrefix

Arg Types: (int, int, vector<int>)

Problem Statement

Imagine a simple input dialog box. The user is supposed to enter a positive integer from a given range into the box.

Recently you realized that sometimes you can tell that the user's input is invalid before he finishes entering the number. For example, if the valid range is 300 to 347, and the user wants to enter the number 372, as soon as he types "37" you can be sure that his input won't be valid.

More precisely, we call a number valid if it is a prefix of some number in the given range, and invalid otherwise.

You are given two ints smallest and largest (denoting the range of valid inputs), and a int[] numbers. The range of valid inputs contains all integers between smallest and largest, inclusive.

Write a method that will determine for each number in numbers whether it represents a valid input for the given range. Return a String[] that has the same number of elements as numbers. If the i-th element of numbers represents a valid input, the i-th element of the return value has to be "VALID", otherwise it has to be "INVALID" (quotes for clarity only).

Constraints

smallest is between 1 and 2,000,000,000, inclusive.
largest is between 1 and 2,000,000,000, inclusive.
smallest is less than or equal to largest.
numbers contains between 1 and 50 elements, inclusive.
Each element in numbers is between 1 and 2,000,000,000, inclusive.

Examples

300
347
{37}
Returns: {"INVALID" }

This is the example from the problem statement.

310
320
{3, 31, 317, 3174, 310, 320}
Returns: {"VALID", "VALID", "VALID", "INVALID", "VALID", "VALID" }

Please note that smallest and largest represent an inclusive range.

600
1020
{7, 73, 734, 7349}
Returns: {"VALID", "VALID", "VALID", "INVALID" }

64
78
{1,2,3,4,5,6,7,8,9}
Returns: {"INVALID", "INVALID", "INVALID", "INVALID", "INVALID", "VALID", "VALID", "INVALID", "INVALID" }

1
1234567890
{123, 456, 789, 1234567, 7654321, 3245354, 325432532, 243212}
Returns: {"VALID", "VALID", "VALID", "VALID", "VALID", "VALID", "VALID", "VALID" }

Watch out for the time limit.

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

Coding Area

Language: C++17 · define a public class InputBoxChecker with a public method vector<string> checkPrefix(int smallest, int largest, vector<int> numbers) · 87 test cases · 2 s / 256 MB per case