Minimum Swaps

Problem Description

A shopkeeper in HackLand assigns each item in a shop a unique popularity rating. To order the items in decreasing popularity from left to right, the shopkeeper can swap any 2 items in one operation. Determine the minimum number of operations needed to reorder the items correctly.

Function Signature

def minimumSwaps(popularity: List[int]) -> int:

Parameters

• int popularity[n]: an array of integers that represents the popularity of each item

Returns

• int: the minimum number of swaps to order the items properly

Constraints

• 1 ≤ n ≤ 2 × 10^5
• 1 ≤ popularity[i] ≤ n

Input Format

• The first line contains an integer n, the size of the array popularity.
• Each of the next n lines contains an integer popularity[i] where 0 ≤ i < n.

Example

Input

4
3
4
1
2

Output

2

Explanation

First switch 3 and 4 to get [4, 3, 1, 2].
Then switch 1 and 2 to get [4, 3, 2, 1].
The array is reordered in 2 operations.

---

Delivery Management System

Problem Description

A manufacturing company is located in a certain city. Their goods need to be shipped to other cities that are connected with bidirectional roads. Though some cities may not be accessible because roads don't connect to them.

The order of deliveries is determined first by distance, then by priority (city number ascending). Given the number of cities, their connections via roads, and what city the manufacturing company is located in, determine the order of cities where the goods will be delivered.

Function Signature

def order(cityNodes: int, cityFrom: List[int], cityTo: List[int], company: int) -> List[int]:

Parameters

• int cityNodes: the number of cities
• int cityFrom[n]: the first city node where there is a bidirectional edge
• int cityTo[n]: the second city node where there is a bidirectional edge
• int company: the node where the route starts

Returns

• List[int]: the cities where the goods will be delivered in the order visited

Constraints

• 2 ≤ cityNodes ≤ 10^5
• 1 ≤ n ≤ min((cityNodes × (cityNodes - 1)) / 2, 10^5)
• 1 ≤ cityFrom[i], cityTo[i], company ≤ n
• cityFrom[i] ≠ cityTo[i]

Input Format

• The first line contains two space-separated integers: cityNodes and n, the number of roads.
• Each of the next n lines contains two space-separated integers cityFrom[i] and cityTo[i].
• The next line contains an integer company.

Example

Input

4 3
1 2
2 3
2 4
1

Output

[2, 3, 4]

Explanation

• City 2 is 1 unit from the company.
• Cities 3 and 4 are 2 units away.
• Delivery order: 2 → 3 → 4

---

Binary Circuit

Problem Description

An engineer is working to build an integrated binary circuit that takes input a binary string s. A binary string consisting of only 0s and 1s can be segregated by moving all the 1s towards the end of the string. In a single operation, any "1" can be moved to the right until it reaches the end or another "1".

The cost of the operation is 1 + the number of places the 1 is moved. It is mandatory to move a 1 to the maximum possible position to the right. Given a binary string s, find the maximum number of operations possible to segregate the given string.

Function Signature

def getMaxCost(s: str) -> int:

Parameters

• string s: The given binary string

Returns

• long: the maximum possible cost for segregating the given string

Constraints

• 1 ≤ length of s ≤ 10^5
• Each character of the string is either '0' or '1'

Input Format

• A single line that contains the string s

Example

Input

110100

Output

13

Explanation

The final string should be "000111".
Steps:

1. Swap the second and third characters → "101100" (cost 2)
2. Swap first and second → "011100" (cost 2)
3. Move the 1s to the end:
   • Three 1s move 2 places each → 3 * 3 = 9
     Total cost = 2 + 2 + 9 = 13

---

我们长期稳定承接各大科技公司如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.