Your task is to create a navigation program for an autonomous car. The car is currently in development and has its drawbacks. The car can make no more than two turns on its way from the starting point to the finish point.

The testing center is a grid of b rows and p columns. Find a way from the starting point to the finish point that has no more than two turns and does not contain cells with blockages, or determine that it is impossible to reach the end. The car can only move upwards, downwards, to the left, and the right.

Input:

• First line: integer b
• Second line: integer p
• Next b lines: p space-separated characters where o = empty cell, x = blockage, Q = start, W = end. Q and W appear only once.

Output: "DRIVE!" if reachable, else "DON'T DRIVE!".

Example: a 4x4 grid where Q and W are diagonally opposite and the row/col path is clear should return "DRIVE!" if it can be done in at most two turns.

解法

在状态 (row, col, direction, turns_used) 上 BFS。每个状态可以沿当前方向继续走，或在 turns_used < 2 时原地切换到任意其他方向。复杂度 O(rows * cols * 4 * 3)。

from collections import deque

def solve(grid):
    n, m = len(grid), len(grid[0])
    sr = sc = er = ec = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'Q': sr, sc = i, j
            elif grid[i][j] == 'W': er, ec = i, j
    DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
    dq = deque()
    seen = set()
    for d in range(4):
        dq.append((sr, sc, d, 0)); seen.add((sr, sc, d, 0))
    while dq:
        r, c, d, t = dq.popleft()
        if (r, c) == (er, ec): return "DRIVE!"
        dr, dc = DIRS[d]
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != 'x' and (nr, nc, d, t) not in seen:
            seen.add((nr, nc, d, t)); dq.append((nr, nc, d, t))
        if t < 2:
            for nd in range(4):
                if nd != d and (r, c, nd, t + 1) not in seen:
                    seen.add((r, c, nd, t + 1)); dq.append((r, c, nd, t + 1))
    return "DON'T DRIVE!"

class Solution {
    public String solve(char[][] g) {
        int n = g.length, m = g[0].length, sr = 0, sc = 0, er = 0, ec = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (g[i][j] == 'Q') { sr = i; sc = j; }
            else if (g[i][j] == 'W') { er = i; ec = j; }
        }
        int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
        boolean[][][][] seen = new boolean[n][m][4][3];
        Deque<int[]> q = new ArrayDeque<>();
        for (int d = 0; d < 4; d++) { q.add(new int[]{sr, sc, d, 0}); seen[sr][sc][d][0] = true; }
        while (!q.isEmpty()) {
            int[] s = q.poll();
            int r = s[0], c = s[1], d = s[2], t = s[3];
            if (r == er && c == ec) return "DRIVE!";
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && g[nr][nc] != 'x' && !seen[nr][nc][d][t]) {
                seen[nr][nc][d][t] = true; q.add(new int[]{nr, nc, d, t});
            }
            if (t < 2) for (int nd = 0; nd < 4; nd++) if (nd != d && !seen[r][c][nd][t+1]) {
                seen[r][c][nd][t+1] = true; q.add(new int[]{r, c, nd, t+1});
            }
        }
        return "DON'T DRIVE!";
    }
}

string solve(vector<vector<char>>& g) {
 int n = g.size(), m = g[0].size();
 int sr=0, sc=0, er=0, ec=0;
 for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
 if (g[i][j] == 'Q') { sr = i; sc = j; }
 else if (g[i][j] == 'W') { er = i; ec = j; }
 }
 int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
 vector seen(n, vector(m, vector(4, vector<int>(3, 0))));
 queue<tuple<int,int,int,int>> q;
 for (int d = 0; d < 4; ++d) { q.push({sr, sc, d, 0}); seen[sr][sc][d][0] = 1; }
 while (!q.empty()) {
 auto [r, c, d, t] = q.front(); q.pop();
 if (r == er && c == ec) return "DRIVE!";
 int nr = r + dr[d], nc = c + dc[d];
 if (nr >= 0 && nr < n && nc >= 0 && nc < m && g[nr][nc] != 'x' && !seen[nr][nc][d][t]) {
 seen[nr][nc][d][t] = 1; q.push({nr, nc, d, t});
 }
 if (t < 2) for (int nd = 0; nd < 4; ++nd) if (nd != d && !seen[r][c][nd][t+1]) {
 seen[r][c][nd][t+1] = 1; q.push({r, c, nd, t+1});
 }
 }
 return "DON'T DRIVE!";
}

You are given a queue of n integers, from which x integers will be selected as explained below:

1. You will perform x iterations on the queue.
2. In each iteration, x integers will be dequeued.

• If the queue has fewer than x numbers, all of them will be dequeued.

3. The maximum integer out of the ones dequeued will be selected.

• If there is more than one occurrence of the maximum number, then the first in the queue will be selected.

4. The remaining ones when decremented by 1 and enqueued back in the same order in which they were dequeued.

• Once the value becomes 0, the integer cannot be decremented any further, and it will continue to remain 0.

Print the original indexes in the queue of the x integers that are chosen (indexing starts from 1).

Example: x=5, queue=[1,2,2,3,4,5,5] returns the 1-based original indices selected across x rounds.

解法

用承载 (original_index, value) 的双端队列模拟。每轮取前 x 项，挑首个最大值，把其下标追加到答案，剩余项减 1(不低于 0)后重新入队。最坏复杂度 O(x² · n)。

from collections import deque

def solve(x, queue):
    dq = deque((i + 1, v) for i, v in enumerate(queue))
    chosen = []
    for _ in range(x):
        if not dq: break
        batch = [dq.popleft() for _ in range(min(x, len(dq)))]
        mv = max(v for _, v in batch)
        for i, (idx, v) in enumerate(batch):
            if v == mv:
                chosen.append(idx)
                for ridx, rv in batch[:i] + batch[i+1:]:
                    dq.append((ridx, max(0, rv - 1)))
                break
    return chosen

class Solution {
    public List<Integer> solve(int x, int[] queue) {
        Deque<int[]> dq = new ArrayDeque<>();
        for (int i = 0; i < queue.length; i++) dq.add(new int[]{i + 1, queue[i]});
        List<Integer> chosen = new ArrayList<>();
        for (int it = 0; it < x && !dq.isEmpty(); it++) {
            List<int[]> batch = new ArrayList<>();
            for (int j = 0; j < x && !dq.isEmpty(); j++) batch.add(dq.poll());
            int maxV = Integer.MIN_VALUE, pos = -1;
            for (int i = 0; i < batch.size(); i++) if (batch.get(i)[1] > maxV) { maxV = batch.get(i)[1]; pos = i; }
            chosen.add(batch.get(pos)[0]);
            for (int i = 0; i < batch.size(); i++) if (i != pos)
                dq.add(new int[]{batch.get(i)[0], Math.max(0, batch.get(i)[1] - 1)});
        }
        return chosen;
    }
}

vector<int> solve(int x, vector<int>& queue) {
 deque<pair<int,int>> dq;
 for (int i = 0; i < (int)queue.size(); ++i) dq.push_back({i + 1, queue[i]});
 vector<int> chosen;
 for (int it = 0; it < x && !dq.empty(); ++it) {
 vector<pair<int,int>> batch;
 for (int j = 0; j < x && !dq.empty(); ++j) {
 batch.push_back(dq.front()); dq.pop_front();
 }
 int maxV = INT_MIN, pos = -1;
 for (int i = 0; i < (int)batch.size(); ++i) if (batch[i].second > maxV) { maxV = batch[i].second; pos = i; }
 chosen.push_back(batch[pos].first);
 for (int i = 0; i < (int)batch.size(); ++i) if (i != pos)
 dq.push_back({batch[i].first, max(0, batch[i].second - 1)});
 }
 return chosen;
}

Find employees whose complete records appear more than once in the EMPLOYEE table (NAME, PHONE, AGE must all match for duplicate).

解法

按构成「完整记录」的所有列分组，筛选 COUNT(*) > 1 的组。SQL 题，不需要 <Tabs>。

SELECT NAME
FROM EMPLOYEE
GROUP BY NAME, PHONE, AGE
HAVING COUNT(*) > 1
ORDER BY NAME;

Determine the number of valid ways to color an n × 3 grid using red, green, and blue, such that no row or column contains cells that are all the same color. Return the answer modulo 10⁹ + 7.

Example: n=2 → 174, n=3 → 9758, n=4 → 290490.

Secure a compromised communication network by disconnecting all nodes. There is a series of nodes (each represented by lowercase English letters) in a string. In a single operation, you can disconnect any number of adjacent nodes that are the same letter.

Determine the minimum number of operations required to disconnect all nodes and secure the network.

Example: s = "aabaa" → 2 (remove the run of a at the ends together via the middle, then remove b).

Some data scientists are developing a tool to analyze palindromic trends in DNA sequences. The palindrome transformation cost of a string is defined as the minimum number of changes required to make it a palindrome. For example, the cost for "asbsd" is 1 (change d to a to get "asbsa").

Given a string dna, determine the total sum of palindromic transformation costs for all its substrings.

Example: dna = "asbsd" has palindrome cost 1; summing across all substrings yields the answer.

To monitor pricing trends, a company wants to identify products that have had an unusually large price increase. A row qualifies when current_price > 1.5 × average_price (i.e. the current price is more than 50% above the historical average).

Output columns: product_id | name | current_price | average_price.

• current_price = the latest price row in price_history (the one with the largest changed_at).
• average_price = average price across the entire dataset for that product, rounded to two decimal places.
• Sort by average_price DESC, then by product_id ASC.

Schema:

products(id, name, brand) — id PK. price_history(id, product_id, price, changed_at) — id PK, product_id FK referencing products.id, price DECIMAL(10,2), changed_at DATE.

Sample data:

products:

price_history:

Expected output:

Reasoning: iPhone 11 has only one row (current_price equals average_price), so it fails the > 1.5 × avg threshold. Mate Pro X averages (1020.10 + 3500.00) / 2 = 2260.05, and 3500.00 > 1.5 × 2260.05 = 3390.075, so it qualifies.

Q1: Output of pushing 1, 1.1, 'z', "Hello" onto a C# Stack, then iterating via foreach?

Answer: Hello, z, 1.1, 1 Explanation: C# non-generic Stack accepts any boxed value; foreach walks the stack top-to-bottom (LIFO), so it prints the last pushed first.

Q2: An input-restricted deque allows inserts at only one end but removes from either end. It can be used as:

Answer: both as a queue and as a stack Explanation: Pushing at the rear and popping from the rear gives a stack; pushing at the rear and popping from the front gives a queue.

Q3: Inorder traversal of the tree where root is F with left subtree B(A, D(C, E)) and right subtree G(_, I(H, _))?

Answer: A B C D E F G H I Explanation: Inorder = left, root, right. Visiting: A B C D E F G H I.

Q4: Bug in the binary-search snippet (mid = l + (r-l)/2; if arr[mid] > x recurse on [l, mid+1])?

Answer: There is an error in line 8. Explanation: When the target is smaller than arr[mid], the recursion should narrow to [l, mid-1], not [l, mid+1].

Q5: Complexity of int a = 1; while (a < n) a = a * 2;?

Answer: O(log₂ n) Explanation: Each iteration doubles a, so the loop runs about log₂(n) times.

Q6: Time complexity to find an element in a singly linked list of length n?

Answer: O(n) Explanation: No random access — every search walks the list from head, O(n) in the worst case.

Once upon a time, a King saw a dream, where if his kingdom has good line of tanks, meaning tanks lined up side by side in a certain way, they will become invincible. Now, since you are the advisor of the king, he has asked you to create a good line of tanks. There are m types of tanks, numbered 1 through m, and we have infinite amount of tanks for each type. Come up with a good line of size n tanks. If there are multiple good lines return one which is lexicographically smallest. A good line is a configuration where tanks lined up in an array and the count of subarrays with only distinct tank types is maximum. e.g {3, 4, 4, 5} contains 6 subarrays with distinct tanks: {3}, {4}, {4}, {5}, {3, 4}, {4, 5} An array x is lexicographically smaller than an array y if there exists an index i such that x[i] < y[i] and for all j < i, x[j] == y[j].

Constraints

• 1 ≤ n ≤ 100000
• 1 ≤ m ≤ 10000000

Example 1

Input:

n = 1
m = 2

Output:

[1]

Explanation: Max subarrays count with distinct tanks for line size 1 is 1. Possible lines - {1}, {2} We choose {1} as it is lexicographically smallest.

Example 2

Input:

n = 2
m = 1

Output:

[1, 1]

Explanation: The only possible line - {1, 1}

Example 3

Input:

n = 2
m = 2

Output:

[1, 2]

Explanation: Possible lines: {1, 1}, {1, 2}, {2, 1}, {2, 2} Lines {1, 2} and {2, 1} have max count of subarrays with distinct tanks.

Given an array A[] denoting heights of N ice cream sticks and a positive integer K, modify the height of each stick either by increasing or decreasing them by K only once and then find out the least difference in the heights between the shortest and longest sticks. For example, consider that the heights are 0, 6, 11 and K=7. We can change 0 to 7, 6 to 9, and 11 to 4. The maximum difference is between 4 and 9, which is 5. We cannot minimise this difference. Input The first line of input contains a positive integer K. The second line of input contains a positive integer N, representing the number of sticks. The third line of the input contains N integers, representing the heights of N sticks. Output The minimum of the maximum difference of heights possible.

Constraints

0 < K ≤ 30 0 < N ≤ 30 0 ≤ A[i] ≤ 500

Example 1

Input:

K = 2
A = [2, 6, 9, 11]

Output:

5

Explanation: Explanation: 2->4, 6->8, 9->7, 11->9. So, the maximum difference is 5 (9-4).

Example 2

Input:

K = 20
A = [3, 4, 5]

Output:

2

Explanation: 3 → 23, 4 → 24, 5 → 25. So, the max different is 2 (25 − 23).

Kady is very energetic guy and he is fond of jumping. He is standing on a two dimension plane of size m*n square units. Plane is partitioned into unit squares. So in total there are m*n squares. Kady has his favourite number 'X', so each time when he will jump he will take jump of 'X' units. In short, plane can be considered as a 2D matrix. Kady is currently standing at position S(p,q) where p is p^th row of matrix and q is q^th column of matrix. Kady wants to go from his position S to new position R(u,v) by taking jumps of exactly X units each time. Determine if kady can reach his destination or not. If he can reach, print the minimum number of jumps he need to take to go from S to R. Note:

• Kady cannot go out of plane. If he do so then he will fall off the plane and dies.
• If Kady wants to take jump from point A to B then jump is only feasible if Euclidean distance between these two points is X. Function Description Complete the function minimumJumps in the editor. minimumJumps has the following parameters:
• int m: the number of rows in the plane
• int n: the number of columns in the plane
• int X: Kady's favourite number, the jump distance
• int p: the row number of Kady's starting position
• int q: the column number of Kady's starting position
• int u: the row number of Kady's destination
• int v: the column number of Kady's destination Returns int: the minimum number of jumps required to reach the destination or -1 if it's not possible

Constraints

• 1 ≤ m, n ≤ 1000
• 1 ≤ X ≤ 1000
• 1 ≤ p, u ≤ m
• 1 ≤ q, v ≤ n

Example 1

Input:

m = 6
n = 5
X = 5
p = 1
q = 2
u = 6
v = 2

Output:

2

Explanation: In starting Kady is standing at position (1,2). From here he can jump to point (6,2) by taking 5 units of jump. From (6,2) he can go to (2,5) which is also at a distance of 5 units from his position. Therefore, the minimum number of jumps required is 2.

Your friend Alice has a box with N letter candles in it. The cost of the box is determined as follows - Find the number of occurrences of each character in the box and sum up the squares of these numbers. Alice wants to reduce the cost of the box by removing some candles from it. However, she is allowed to remove at most M candles from the box. Can you help Alice determine the minimum cost of the box? Input The first line of the input contains the integer N, representing the number of letter candles. The second line of the input contains the integer M, representing the number of candles Alice can remove. The third line of the input contains an N-lettered string S, which contains lowercase English letters, representing the letter candles in the box. Output Print the minimum possible cost of the box.

Constraints

Unknwon for now. Will add once find them

You are working on a secret government project, and you are tasked with decoding. You hit upon a theory that the cipher is hidden within a sequence of characters and has the following restrictions:

• (a) It has to contain at least one uppercase character.
• (b) It cannot contain any digits. You are given a string s consisting of n alphanumerical characters. You need to find the longest substring of s that is a valid cipher and return its length. A substring is defined as a contiguous segment of a string. For example, given "k3Cb", the substrings that are valid ciphers are "C" and "Cb". Note that "kCb" is not a substring, and "k3B" is not a valid cipher. In this case, your function should return 2 as the longest substring is "Cb". Alternatively, given "k3uu", your function should return -1 since there is no substring that satisfies the restrictions on the format of a valid cipher. Input The input contains a string s. Output Print the length of the longest substring that is a valid cipher. If there is no such substring, your function should return -1.

Constraints

• 1 ≤ n ≤ 200
• s

MS Dhoni is known for his cool nature, however, on many occasions we have seen him lose his calmness when his fielders drop catches. Catches win matches. He has come up with a new activity as a fielding practice for his players, where they can earn points for completing catches. Players are made to stand in the form of a N * M matrix with values assigned at all positions. If a Player at position (i2, j2) catches a ball from a player standing at (i1, j1), he is rewarded with points equal to the difference of values between the points: (i2, j2) and (i1, j1). Player1 can throw a ball to player2 only if player2 is located either towards right or down in the matrix. Provided that there is only one ball, your task is to determine the maximum reward that can be obtained collectively by the players. The catching can start from any player and can end at any player, and it must include at least two players. Input Format: The first line of input consists of two integers N and M denoting the number of rows and columns in the matrix. The next N lines have M space separated integers denoting the values at each position in the matrix Output Format: You need to output the maximum reward that can be obtained by the players

Constraints

• 2 ≤ N, M ≤ 1000
• 0 ≤ matrix[i][j] ≤ 10⁴

Example 1

Input:

N = 4
M = 4
matrix = [[1, 2, 13, 0], [15, 26, 7, 48], [99, 86, 11, 12], [92, 89, 0, 99]]

Output:

99

Explanation: Maximum reward of 99 can be obtained if the ball is thrown from (3,2) to (3,3),(0,3) to (1,3); score = 48 (1,3) to (2,3); score = -36 (2,3) to (3,3); score = 87 Total score = 99

Sam the gardener takes care for the garden in his area. One of the jobs in the garden is to water the garden. The garden has attached equidistant sprinklers, where each sprinkler has a range and a cost associated with it. Sam wants to switch on the sprinklers in such a way that whole garden is watered and the cost of this operation is minimised, so that he can use the money in some other gardening activities. Can you help Sam in optimising the cost of watering the garden? We can assume the garden to be on a x axis, where sprinklers are placed on every integer index from 0 to length of the garden. So, if the len of garden is n, then it has n + 1 sprinkles from 0 to n. If it is not possible to water the garden then return -1. A sprinkler placed on index i with range r can water the garden from i-r to i+r. Input Format First line contains single integer N denoting the len of the garden.

• Second line contains N + 1 space separated integers denoting the range of N + 1
• Third line contains N + 1 space separated integers denoting the cost of N + 1 sprinkles Output Format Min cost of watering the garden

Constraints

• 1 ≤ N ≤ 10⁴
• 0 ≤ range[i] ≤ 100
• 0 ≤ cost[i] ≤ 10⁴

You have a string S. Your task is to rearrange some characters of the string (if needed) so that S[i] is not equal to S[L - i - 1] for each 0 Input The input contains the string S`. Output Print 'impossible' if there is no answer. Otherwise, print a lexicographical first string that satisfies the given requirements.

Constraints

1 ≤ L ≤ 10⁴

Example 1

Input:

s = "abca"

Output:

"aabc"

Explanation: No explanation is provided for now As always, I will add it once find any. Or if you happen to know about it, feel free to dm Groot! Many thanks in advance!

Oleg has N dolls of various sizes. He can place the smaller dolls inside the larger ones, but dolls of the exact same size cannot be placed inside each other. He needs to find the minimum number of dolls that remain when the maximum number of dolls have been packed. Input The first line of input contains an integer N representing the number of dolls initially. The second line consists of N space-separated integers representing the size of dolls. Output Print an integer representing the minimum number of dolls Oleg has after placing all smaller dolls inside the larger dolls.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ size of doll ≤ 10⁵

Example 1

Input:

sizes = [2, 2, 3, 3]

Output:

2

Explanation: In order to be left with the minimum number of dolls, Oleg will do the following:

• Puts doll at index 1 inside doll at index 3 i.e doll of size two in size three.
• Puts doll at index 2 inside box at index 4 i.e doll of size two in size three. Now he is left with two dolls of size three which cannot be further placed inside each other. So, the output is 2.

Example 2

Input:

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

Output:

2

Explanation: Oleg will place dolls at index (1, 2, 4, 5) in the doll at index 6. So, he will remain with two dolls of sizes two and five.

A string is called "palindrome-like" if it can be rearranged in any way to become a palindrome. For example, aabb is palindrome-like since it can be rearranged to abba. For any string, you are allowed to change any number of characters to make it palindrome-like. Let this minimum number of changes be the string's cost. Given a string s, find the total sum of palindrome transformation costs of all substrings of s. Also asked by Google: DNA Sequencing.

Constraints

• 1 ≤ n ≤ 10⁵
• s consists of lowercase English letters

Example 1

Input:

s = "abca"

Output:

6

Explanation: Substrings of "abca" with non-zero cost are:

• "ab": cost 1
• "abc": cost 1
• "abca": cost 1
• "bc": cost 1
• "bca": cost 1
• "ca": cost 1 Single-character substrings have cost 0, so total cost is 1 + 1 + 1 + 1 + 1 + 1 = 6.

There is a 2D plane of size N*M. There is fire which is there at K different points in the 2D plane. From each of these K points, the fire is spreading in a circular form with the radius of the fire increasing by time. So, if at t=1, the radius of fire (represented by R) was 2, at t=2, it becomes 4, at t=3, it become 6 and so on. "t" denotes time here. Help us determine, the number of points (points are denoted by (x,y), where both x and y are whole numbers, and are within the plane) which would not be touched by the fire. Input Format The first line has 3 space separated integer N, M and K, dimensions of the 2D plane and the number of fire points. Next K lines each having 2 space separated integers, stating the coordinates of the fire. Next line denotes the R, the radius of the fire at t=1, Next line contain an integer T, stating the time at which we want to know points not touched by fire.

Example 1

Input:

N = 4
M = 4
K = 2
firePoints = [[1, 1], [3, 3]]
R = 1
T = 2

Output:

6

Explanation: Fire does not reach these 6 points:

• 0,3
• 0,4
• 1,4
• 3,0
• 4,0
• 4,1

You are given a petri dish with a grid with some healthy cells at locations i,j. It is of dimensions N x M, where each grid point in the dish can only have the following values: 0: Empty

• 1: Has a healthy cell
• 2: Has a virus cell Unfortunately, a virus can make its healthy neighbors sick (infected), and you need to find the minimum time at which all the cells have the virus. A virus-cell at location [i, j] will infect healthy cells at [i-1, j], [i+1, j], [i, j-1], [i, j+1] (up, down, left and right), and this takes place in one second of time. If not all cells in the dish are infected with the virus, then return -1. Function Description Complete the function minimumTimeToInfect in the editor. minimumTimeToInfect has the following parameter:
• int N: Num of rows
• int M: Num of columns
• N lines of the input contains the M space-separeted elements that indicate elements in each row of the matrix Returns int: an integer that denotes the min time for all cells to have the virus, or print -1 if not all cells in the dish are infected.

Constraints

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• 0 ≤ ar[j] ≤ 2