Problem Brief

Work Schedules (for MTS2)

FULLTIMEOA

An employee has to work exactly as many hours as they are told to each week, scheduling no more than a given daily maximum number of hours. On some days, the hours worked will be given. The employee gets to choose the remainder of their schedule, within the given limits.

A completed schedule consists of exactly 7 digits in the range 0 to 8 that represent each day's work hours. A pattern string similar to the schedule is given, but the scheduled hours are marked by a question mark, ?, (ascii 63 decimal). Given a maximum number of hours that can be worked in a day, replace the question marks with digits so the scheduled hours is exactly the total hours that must be worked in a week.

Determine all possible work schedules that meet the requirements and return them as a list of strings, sorted ascending.

Function Description

Complete the function findSchedules in the editor.

findSchedules has the following parameter(s):

1. int work_hours: the hours that must be worked in the week
2. int day_hours: the maximum hours that may be worked in a day
3. String pattern: the partially completed schedule

Returns

String arr[]: represents all possible valid schedules (must be ordered lexicographically ascending)

1Example 1

Input

work_hours = 24, day_hours = 4, pattern = "08??840"

Output

["0804840", "0813840", "0822840", "0831840", "0840840"]

Explanation

There are 2 days on which they must work 24-20=4 more hours for the week. All of the possible schedules are listed below: 0804840 0813840 0822840 0831840 0840840

2Example 2

Input

work_hours = 56, day_hours = 8, pattern = "???8???"

Output

["8888888"]

Explanation

There is only one way to work 56 hours in 7 days of 8 hours.

3Example 3

Input

work_hours = 3, day_hours = 8, pattern = "??2??00"

Output

["0020100", "0021000", "0120000", "1020000"]

Explanation

work_hours = 3 day_hours = 2 pattern = '??2??00' They only need to schedule 1 more hour for the week, and it can be on any one of the days in question.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ work_hours ≤ 56
1 ≤ day_hours ≤ 8
| pattern | = 7
Each character of pattern ∈ {0, 1, ..., 8}
There is at least one correct schedule.