6. Load Balancing

Implement a prototype of a resource allocation in a distributed parallel computing infrastructure.

There are n resources and m tasks to schedule on them where the i th task has a processing time of burstTime[i]. The total load time of a resource is the sum of the total burst times of the jobs assigned to the resources. However, a particular resource can be allocated jobs in a contiguous segment only (i.e., from some index x to some index y [x,x+1,…,y]).

Find the minimum possible value of the maximum total load time of the servers if resources are allocated optimally.

Example

Consider n=3, m=6, [4,3,2,2,2,6] burstTime=[4,3,2,2,2,6].

An optimal resource allocation is shown:

• Server 1: Jobs [4, 3], Total Load Time = 4 + 3 = 7
• Server 2: Jobs [2, 2, 2], Total Load Time = 2 + 2 + 2 = 6
• Server 3: Jobs [6], Total Load Time = 6

It is optimal to allocate the first two jobs to one first resource and the remaining three jobs to the other resource. Total load times are 9 + 2 = 11 and 4 + 4 + 5 = 13.

Sample Case 1

Sample Input For Custom Testing:

cssCopy code

STDIN FUNCTION ----- -------- 3 n = 3 5 burstTime[] size m = 5 4 burstTime = [7, 2, 3, 4, 5] 2 3 4 5

Sample Output 1:

Copy code

9

Explanation:

It is optimal to allocate the first job to the first resource, the last job to the second resource, and the remaining three jobs to the third resource. Total load times are 7, 5, and 2 + 3 + 4 = 9 respectively.

7. Valid Passwords

Hackerbank allows all citizens of the city of Hackerland to maintain their finances.

In order to ensure security, given two integers n and k, a password is valid if:

• The length of the password is (

n ).

• The password consists of lowercase English characters only.
• The password does not contain k consecutive equal characters.

Given the integers n and k, find the number of distinct valid passwords that can be generated. Since the answer can be large, compute it modulo 109+7109+7.

Example

Consider n=2, k=2.

The total number of passwords of length 2 is 26×26=67626×26=676. There are 26 cases where k<2 consecutive characters are the same. Thus, the answer is 26×26−26=676−26=65026×26−26=676−26=650, and 650650 modulo 109+7109+7 is 650650.

Function Description

Complete the function countValidPasswords in the editor below.

Constraints

• 2≤n≤10^5
• 2≤k≤n

Sample Case 0

Sample Input For Custom Testing:

sqlCopy code

STDIN FUNCTION ----- -------- 3 n = 3 3 k = 3

Sample Output:

Copy code

17550

Explanation:

The number of passwords possible of length 3 are 263263. Subtract the cases where all the characters are the same (26 cases). The number of valid passwords is 263−26263−26, and 1755017550 modulo 109+7109+7 is 1755017550.

联系我来获取完整的题目信息和解题思路，我们可以协助您通过任何OA VO