# 1. The number of combinations in which the sum of two elements in the array is less than or equal to M

For an integer array, how many combinations are there when any two elements are added and less than or equal to M;

If yes, output the combined logarithm;

No, output 0.

code:

nums = list(map(int, input().split())) M = int(input()) n = len(nums) ans = 0 for i in range(n - 1): for j in range(i + 1, n): if nums[i] + nums[j] <= M: ans += 1 print(ans)

# 2. Calculate K-bit

Give you two positive integers n and k, where 1 = < n < = 26, and the formation rules of string Sn are as follows:

Li stands for 26 letters a-z, which are:

L1 = "a"

L2 = "b"

L3 = "c"

...

L26="z"

S1 = "a"

When I > 1, Si = Si-1 +Li + reverse(invert(Si-1))

Where + represents the connection operation of the string, reverse(x) returns the string obtained by reversing x, and convert (x) will flip each bit in X (for example, 'a' to 'z', 'b' to 'y',... And 'z' to 'a').

For example, the first four strings of the sequence according to the above description are:

S1="a"

S2="abz"

S3="abzcayz"

S4="abzcayzdabzxayz"

Please return the k-th character of Sn. The title data must ensure that K is within the length range of Sn.

Example 1 input and output examples are only for debugging, and the background judgment data generally does not contain examples

code:

# The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly # # Returns the k-th character of Sn # @N of param n int integer Sn # @param k int integer needs to return the character subscript # @return char character type # class Solution: def findKthBit(self, n, k): # write code here def invert(s) -> str: inv_s = '' for ch in s: inv_s += chr(122 - ord(ch) + 97) return inv_s S = {} for i in range(1, n + 1): if i == 1: S[i] = 'a' else: S[i] = S[i - 1] + chr(96 + i) + invert(S[i - 1])[::-1] return S[n][k - 1] n, k = 3, 1 print(Solution().findKthBit(n, k))

# 3. Paper distribution problem

A group of children gathered in a circle to start painting. Now the teacher needs to give these children paper;

The rule is that if a child is older than the child next to him, the child must be given more paper than the child next to him;

All children should have at least one piece of paper. Please help the teacher design an algorithm to calculate the minimum number of sheets of paper.

remarks:

It is assumed that the total number of children will not exceed 100;

Each child is required to have at least one piece of paper;

If and only if the age is older than the adjacent children, more paper will be required (less than or equal to is allowed if the age is equal).

Solution: take the local minimum value by dichotomy, judge the height of the left and right sides, and discuss the situation

code:

from collections import defaultdict ages = list(map(int, input().split())) papers = defaultdict(int) n = len(ages) def get_paper(left, right): if left >= right: return part_ages = ages[left: right] min_age = min(part_ages) idx = part_ages.index(min_age) + left if ages[idx - 1] >= ages[idx] and ages[(idx + 1) % n] >= ages[idx]: papers[idx] = 1 elif ages[idx - 1] < ages[idx] and ages[(idx + 1) % n] < ages[idx]: papers[idx] = max(papers[idx - 1], papers[(idx + 1) % n]) + 1 elif ages[idx - 1] < ages[idx]: papers[idx] = papers[idx - 1] + 1 else: papers[idx] = papers[(idx + 1) % n] + 1 get_paper(left, idx) get_paper(idx + 1, right) get_paper(0, n) print(sum(papers.values()))

# 4. Nautical exploration

Give you a two-dimensional grid composed of '0' (water), '1' (land) and '2' (obstacles), and then give you an amphibious vehicle. The land cost is 1 and the waterway cost is 2. The obstacles are impassable. Please calculate the minimum cost from the starting position of the grid to the final position.

Note: you can only drive horizontally and vertically. If the destination cannot be reached, - 1 is returned

In addition, the first starting location is not counted, and the cost is determined according to the attribute of the arrival location.

Example 1 input and output examples are only for debugging, and the background judgment data generally does not contain examples.

Solution:

## Backtracking (time consuming, timeout)

# # The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly # # Calculate the minimum sailing cost # @param input int integer 2D array 2D mesh # @return int integer # class Solution: ans = 99999 def minSailCost(self, input): # write code here m, n = len(input), len(input[0]) flag = [[False] * n for _ in range(m)] cost_dict = {0: 2, 1: 1, 2: 0} def travel(x, y, cost): if x < 0 or x >= m or y < 0 or y >= n: return if flag[x][y] or input[x][y] == 2: return if x != 0 or y != 0: cost += cost_dict[input[x][y]] if x == m - 1 and y == n - 1: if cost < self.ans: self.ans = cost return flag[x][y] = True travel(x - 1, y, cost) travel(x + 1, y, cost) travel(x, y - 1, cost) travel(x, y + 1, cost) flag[x][y] = False travel(0, 0, 0) return self.ans if self.ans != 99999 else -1 input = [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]] print(Solution().minSailCost(input))

## Dynamic planning paper cutting (snake walking is not considered)

# # The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly # # Calculate the minimum sailing cost # @param input int integer 2D array 2D mesh # @return int integer # class Solution: def minSailCost(self, input): # write code here m, n = len(input), len(input[0]) cost_dict = {0: 2, 1: 1} inf = 99999 # Record the minimum cost from a point of departure to the end dp = [[inf] * n for _ in range(m)] def travel(x, y): if x < 0 or x >= m or y < 0 or y >= n or input[x][y] == 2: return inf if dp[x][y] != inf: return dp[x][y] cur_cost = 0 if x == 0 and y == 0 else cost_dict[input[x][y]] if x == m - 1 and y == n - 1: dp[x][y] = cur_cost else: part_cost1 = travel(x + 1, y) part_cost2 = travel(x, y + 1) dp[x][y] = min((part_cost1, part_cost2)) + cur_cost return dp[x][y] ans = travel(0, 0) return ans if ans < inf else -1 input = [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]] print(Solution().minSailCost(input))

## Priority queue (positive solution, PRIM algorithm idea)

# # The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly # # Calculate the minimum sailing cost # @param input int integer 2D array 2D mesh # @return int integer # from queue import PriorityQueue class Node: def __init__(self, x, y, cost): self.x = x self.y = y self.cost = cost def __lt__(self, other): return self.cost < other.cost class Solution: def minSailCost(self, input): # write code here m, n = len(input), len(input[0]) cost_dict = {0: 2, 1: 1} directions = ((0, 1), (0, -1), (1, 0), (-1, 0)) vis = [[0] * n for _ in range(m)] q = PriorityQueue() q.put(Node(0, 0, 0)) vis[0][0] = 1 while not q.empty(): node = q.get() if node.x == m - 1 and node.y == n - 1: return node.cost for i in range(4): dx = node.x + directions[i][0] dy = node.y + directions[i][1] if dx < 0 or dx >= m or dy < 0 or dy >= n or input[dx][dy] == 2 or vis[dx][dy] == 1: continue vis[dx][dy] = 1 cur_cost = node.cost + cost_dict[input[dx][dy]] q.put(Node(dx, dy, cur_cost)) return -1 input = [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]] print(Solution().minSailCost(input))