You are given a string S and a two-dimensional array of characters of size N×N named grid. Each field in the grid is either empty (denoted by a dot ".") or contains an uppercase English letter. Each particular letter may appear at most twice in the grid.

Your task is to reconstruct string S by visiting fields of the grid. You start the reconstruction with an empty string. You can choose the field in which you want to start. In one move, you can change the current field to an adjacent one (up, down, left, right). If you visit a field containing a letter, you may append this letter to the end of the reconstructed string. Appending a letter is not counted as a move. Each field can be visited, and each letter can be used multiple times during the reconstruction process.

What is the minimum number of moves needed to reconstruct string S?

If it is not possible to reconstruct S, return -1.

Write a function:

def solution(S, grid)

that, given a string S and an array grid, returns the minimum number of moves needed to reconstruct S.

Examples

1. Given S = "ABCA" and grid = [ ".A.C", ".B..", "....", "...A" ] The function should return 6. Optimal movement during the reconstruction process:
   • Start on the field containing "A" in the first row.
   • Move to the adjacent field with "B" in one move.
   • Move to the field containing "C" in three moves.
   • Return to the starting field with "A" in two moves.
   Total moves = 1 + 3 + 2 = 6.

This way, the string "ABCA" is reconstructed in six moves.

---

There is an array A consisting of N integers. Divide them into three non-empty groups. In each group, we calculate the difference between the largest and smallest integer. Our goal is to make the maximum of these differences as small as possible.

For example, given A = [11, 5, 3, 12, 6, 8, 1, 7, 4], we can divide the elements into three groups:

• [3, 1, 4] → the difference between elements is 3;
• [5, 6, 8, 7] → the difference is also 3;
• [11, 12] → the difference is 1.

The maximum difference equals 3, which is the minimum possible result.

Write a function:

def solution(A)

that, given an array A, returns the minimum possible result as explained above.

Examples

1. For A = [11, 5, 3, 12, 6, 8, 1, 7, 4], the function should return 3, as explained above.
2. ForA = [10, 14, 12, 1000, 11, 15, 13, 1], the function should return 5. The elements of A should be divided into three groups as follows:
   • [1]
   • [10, 14, 12, 11, 15, 13]
   • [1000]
3. ForA = [4, 5, 7, 10, 10, 12, 12, 12], the function should return 2. The elements of A could be divided into these three groups:
   • [4, 5]
   • [7]
   • [10, 10, 12, 12, 12]

---

You are given N numbers on a circle, described by an array A. Find the maximum number of neighbouring pairs whose sums are even. One element can belong to only one pair.

Write a function:

def solution(A)

that, given an array A consisting of N integers, returns the maximum number of neighbouring pairs whose sums are even.

Examples

1. GivenA = [4, 2, 5, 8, 7, 3, 7], the function should return 2. Explanation:
   • We can create two pairs with even sums:
     • (A[0], A[1]) → (4, 2), sum = 6 (even)
     • (A[4], A[5]) → (7, 3), sum = 10 (even)
   • Another valid way to choose two pairs:
     • (A[0], A[1]) → (4, 2)
     • (A[5], A[6]) → (3, 7), sum = 10 (even)

Constraints

• The numbers are arranged in a circle, meaning the last element A[N-1] is a neighbor of the first element A[0].
• The goal is to maximize the number of such even-sum pairs.

---

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