1. Monsoon Umbrellas

Umbrellas are available in different sizes that are each able to shelter a certain number of people. Given the number of people needing shelter and a list of umbrella sizes, determine the minimum number of umbrellas necessary to cover exactly the number of people given and no more. If there is no combination of umbrellas of the same or different sizes that covers exactly that number of people, return -1.

Example 1

requirement = 5
sizes = [3, 5]

One umbrella can cover exactly 5 people, so the function should return 1.

Example 2

requirement = 8
sizes = [3, 5]

It is possible to use 1 umbrella of size 3 and 1 umbrella of size 5 to cover exactly 8 people, so the function should return 2.

Example 3

requirement = 7
sizes = [3, 5]

There is no combination of umbrellas that cover exactly 7 people, so the function should return -1.

Function Description

Complete the function getUmbrellas in the editor below.

getUmbrellas has the following parameter(s):

• int requirement: the number of people to shelter
• int sizes[n]: an array of umbrella sizes available

Returns

• int: the minimum number of umbrellas required to cover exactly requirement people, or -1 if it is impossible

Constraints

• 1 ≤ requirement, n, sizes[i] ≤ 1000

Sample Case 0

Input

requirement = 4
sizes[0] size n = 2
sizes = [2, 4]

Output

1

Explanation 0

The first size of umbrella can cover sizes[0] = 2 people, and the second size can cover 4 people. Since one umbrella of size 4 is sufficient to cover 4 people, the function should return 1.

---

2. Good Binary Strings

Two definitions follow:

• A binary string consists of 0s and/or 1s. For example, 0101, 1111, and 00 are binary strings.
• The prefix of a string is any of its substrings that include the beginning of the string. For example, the prefixes of 11010 are 1, 11, 110, 1101, and 11010.

A non-empty binary string is good if the following two conditions are true:

Conditions

1. The number of 0s is equal to the number of 1s.
2. For every prefix of the binary string, the number of 1s is not less than the number of 0s.

For example, 11010 is not good because it does not have an equal number of 0s and 1s, but 11001100 is good because it satisfies both conditions.

A good string can contain multiple good substrings. If two consecutive substrings are good, then they can be swapped as long as the resulting string is still a good string. Given a good binary string, binString, perform zero or more swap operations on its adjacent good substrings such that the resulting string is the largest possible numeric value. Two substrings are adjacent if the last character of the first substring occurs exactly one index before the first character of the second substring.

Example

binString = 1010111000

There are two good binary substrings, 1010 and 111000, among others. Swap these two substrings to get a larger value: 1110001010. This is the largest possible good string that can be formed.

Function Description

Complete the function largestMagical in the editor below.

Function Parameters

str binString: a binary string

Returns

str: the largest possible binary value as a string

Constraints

• Each character of binString ∈ {0,1}
• 1 ≤ |binString| ≤ 50
• binString is a good string

Sample Case 0

Input

binString = "11011000"

Output

11100100

Explanation 0

Choose two adjacent good substrings to swap: 10 and 1100. The resultant string, str = 11100100.

Sample Case 1

Input

binString = "1100"

Output

1100

Explanation 1

The only good substring of binString is 1100. No operations can be applied to the string.

Sample Case 2

Input

binString = "110010011000"

Output

1100101100

Explanation

The only consecutive good substrings are 110010 and 1100. Note that 100 is not a good substring because it contains more zeroes than ones. If they are swapped, it results in a numerically smaller string. Thus, binString is already the numerically largest good string that can be formed.

---

3. Almost Sorted

An array of integers is almost sorted if at most one element can be deleted from it to make it perfectly sorted, ascending. For example, arrays [2, 1, 7], [13, 9, 2] and [1, 5, 6] are almost sorted because they have 0 or 1 elements out of place. The arrays [4, 2, 11, 7], [1, 2, 6, 4] are not because they have more than one element out of place. Given an array of n unique integers, determine the minimum number of elements to remove so it becomes almost sorted.

Example

arr = [3, 4, 2, 5, 1]

Remove 2 to get arr' = [3, 4, 5], or remove 1 to get arr' = [3, 4, 2, 5], both of which are almost sorted. The minimum number of elements that must be removed in this case is 1.

Function Description

Complete the function minDeletions in the editor below.

Function Parameters

int arr[n]: an unsorted array of integers

Returns

int: the minimum number of items that must be deleted to create an almost sorted array

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁹
• All elements of arr are distinct

Sample Case 0

Input

arr[] size n = 5  
arr = [1, 2, 6, 4, 3]

Output

1

Explanation

One can remove for example 4 to get [1, 2, 6, 3] which is almost sorted. Other choices are to remove 6 or 3. The minimum number of elements that have to be removed in this case is 1.

---

4. Copy Assignment Operator: Swapping Objects

Given a Contest class, create two instances of the class and initialize them with lists of scores data. Swap the scores data between the two objects. When you instantiate each object, a before sentence will print. After your swap routine is run, the after sentences are printed.

Your completed function must perform the following sequence of actions:

Steps

1. Instantiate a Contest object named first_contest with the scores provided by the array named first.
2. Instantiate a Contest object named second_contest with the scores provided by the array named second.
3. Swap the scores of the Contest objects.

Function Description

Complete the function swap_scores in the editor below.

Function Parameters

first[first[0]...first[n-1]]: an array of integers  
second[second[0]...second[m-1]]: an array of integers

Locked code stub in the editor defines the Contest class. It has a private data member, vector<int> scores describing the scores of all the challenges featured in a contest. It handles all data output.

Constraints

• 0 ≤ first[i], second[i] ≤ 100
• 1 ≤ |first|, |second| ≤ 10

Sample Case 0

Input

3  
1  
2  
3  
3  
2  
3  
4

Output

Before swapping the scores: 1 2 3  
Before swapping the scores: 2 3 4  
After swapping the scores: 2 3 4  
After swapping the scores: 1 2 3

Explanation 0

Given first = [1, 2, 3] and second = [2, 3, 4], we instantiate the first_contest object with scores = [1, 2, 3] and the second_contest object with scores = [2, 3, 4].

After swapping the scores, the first_contest object's scores become [2, 3, 4] and the second_contest object's scores become [1, 2, 3].

---

5. Drawing Edge

Given a number of vertices, determine the number of ways these vertices can form a graph. The graph may be disjoint, so it is not necessary to connect all vertices. The answer may be very large, return its value modulo (10⁹ + 7).

Note: Two ways of drawing edges are considered different if at least one pair of vertices has a different connection or the number of edges is different.

Example

n = 4  (number of vertices)

From four vertices, 64 graphs are possible. Sixteen of them are shown.

Function Description

Complete the function drawingEdge in the editor below.

Function Parameters

int n: the number of vertices

Returns

int: the number of graphs that can be constructed using n vertices, modulo (10⁹ + 7)

Constraints

• 1 ≤ n ≤ 10⁹

Sample Case 0

Input

n = 2

Output

2

Explanation 0

There is one way to connect two vertices:

• A — B
• A B

Non-connected vertices are considered one way as well.

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.