Description:

https://interunia.unswcpmsoc.com/task/Counting%20Stars/

Thinking:

• Given a set of star positions, we need to calculate the minimum number of stars required to explain these positions.
• Meteors (i.e., moving stars) move from left to right, and from high to low (x coordinates increase, y coordinates decrease), without moving horizontally or vertically.
• Each meteor may appear in multiple positions (because it moves), and the final cumulative image will show all the positions it has passed through.
• The positions of fixed stars remain unchanged.

Therefore, we need to maintain a list of the last y-coordinate of the current chain.

1. Sort the points: Sort them by increasing x coordinates.
2. Initialization: Create an empty list last_y to store the last y-coordinate of each chain.
3. Traverse the set of points:
   • For each point (x, y):
     • Use bisect_right to find the first position in last_y that is greater than the current y.
     • If the index is less than the length of last_y, it means there is an existing chain that can accommodate the current point, so we update the last y-coordinate of that chain to the current y.
     • If the index is equal to the length of last_y, it means no suitable chain is found, so we need to create a new chain and add the current y to last_y.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import bisect

n = int(input())
stars = []

for _ in range(n):
    x, y = map(int, input().split())
    stars.append((x, y))

# 按 x 坐标递增排序
stars.sort(key=lambda x: (x[0],))

last_y = []

for x, y in stars:
    idx = bisect.bisect_right(last_y, y)
    if idx < len(last_y):
        last_y[idx] = y  # 更新链的最后一个 y 坐标
    else:
        last_y.append(y)  # 创建新的链

print(len(last_y))

Exercise 1

Problem Description

At first, I thought this exercise was about dividing by a modulus, where the modulus would always be incremented by one. But then I realized that in some cases, there’s no “2” in the division sequence. For example, for 12, the answer is 12 6 3 1\n. This indicates that the number is always being divided by 2.

When we look at the examples of these answers, we can see that the format aligns each number to the right, based on the width of the largest number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

%%run_and_test python3 -c "from exercise_4_1 import f1; f1(13)"

'''
 13  6  3  1\n
 12  6  3  1\n
 11  5  2  1\n
 10  5  2  1\n
  9  4  2  1\n
  8  4  2  1\n
  7  3  1\n
  6  3  1\n
  5  2  1\n
  4  2  1\n
  3  1\n
  2  1\n
  1\n
'''

So we have the following solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Assume that the argument n is an integer at least equal to 1.
#
# Each integer is printed out in a field of size equal to
# the number of digits in n plus 1.
#
# The output is printed out, not returned.

def f1(n):
    w = len(str(n)) + 1
    for i in range(n, 0, -1):
        while i:
            print(f'{i:{w}}', end="")
            i = i // 2
        print()
    return

Complexity Analysis

The time complexity of this algorithm is O(n log n), where n is the input number. This is because we are dividing the number by 2 until we reach 1. The space complexity is O(1) because we are not using any additional data structures.

Exercise 2

Problem Description

This exercise asks us to repeatedly remove the maximum number from the set until only one element remains. The line print(“A list of sets:”, all(isinstance(x, set) for x in S)) checks if the return value of f2 is a list of sets.

In my solution:

1
2
3
4
5
6
7
8

def f2(S: set[int]):
    ans = []
    s_list = list(S)  # Convert the set to a list
    s_list.sort()  # Sort the list
    while len(s_list) > 0:
        ans.append(set(s_list))  # Append the current set
        s_list.pop()  # Pop the last (largest) element
    return ans

I convert the set to a list because tuples don’t have a sort() method. So I convert it, sort it, and then pop the largest element (which is at the end of the list) while the length is greater than 1.

The standard solution is:

1
2
3
4
5
6

def f2(S):
    U = [set(S)]
    while len(S) > 1:
        S.remove(max(S))  # Remove the maximum element
        U.append(set(S))  # Append the current set
    return U

The standard solution is simpler; it uses max() to find and remove the largest element, then appends the result to the list.

Standard solution is better because it is more concise and uses less memory.

Exercise 3

Problem Description

As per the description of Exercise 4, we need to remove elements that are equal to the mean value of their neighboring elements (i.e., the element is the average of the one just before and the one just after it).
Please pay attention to the special challenge: use only one loop without any break or continue statements, and only one if statement (with no elif nor else statements).

In my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Assume that the argument L is an increasing list of integers.
#
# Keep removing any member of the list
# that is neither the first one nor the last one
# and that is the average of the one just before and the one just after.
#
# Special challenge: use only one loop without any break or continue statements,
# and only one if statement (with no elif nor else statements).
def f3(L):
    for i in range(len(L) - 2):
        if L[i] + L[i + 2] == 2 * L[i + 1]:  # Check if the middle element is the average
            L.pop(i + 1)  # Remove the element if it satisfies the condition
            return f3(L)  # Recurse to check the rest of the list
    return L

Explanation:

• The function iterates through the list, checking if any element (except the first and last) is the average of its neighbors.

• If an element meets this condition, it’s removed using pop(), and the function calls itself recursively to continue checking the remaining list.

• This approach ensures that all elements satisfying the condition are removed.

• The main reason for using recursion in the original code is to avoid i going beyond the scope of the list, because the length of the list changes each time an element is deleted, so in the original for loop, the index may exceed the length of the list. Recursion avoids this situation by re-calling the function and re-traversing the list from the beginning.

When we use for i in sth. in Python, i is essentially a “view” or a “shallow copy” of the elements in sth.. Modifying i directly will not change sth. itself. Additionally, we cannot modify the value of i, because in each iteration of the loop, i is reset to the next element in the sequence.
This means that if we use a for loop directly in this context, and we remove an element from the list during the loop, the list will get shorter. As a result, i could end up being out of range in subsequent iterations of the loop.

The standard solution is:

1
2
3
4
5
6
7

def f3(L):
    i = 0
    while (i := i + 1) < len(L) - 1:
        if L[i - 1] + L[i + 1] == L[i] * 2:
            L.pop(i)
            i -= 1
    return L

Explanation:

The while loop version of the code does avoid recursion, and manually manages the value of i to ensure that the index does not exceed the range after the list is deleted. This reduces the complexity of the recursive call while achieving the same effect.

Key points:

• The function uses only one loop and one if statement as required by the challenge.
• Recursion is used to continue processing after each removal.

Exercise 4

Problem Description

You are given an integer n, and the goal is to express n as a sum (or difference) of powers of 2. This should be done by leveraging the binary representation of n.
Specifically, you need to:

1. Convert n to its binary form.
2. Identify which positions in the binary form have a 1.
3. Use these positions to generate the corresponding powers of 2.
4. If n is positive, add the powers of 2 together. If n is negative, subtract the powers of 2.
   The output should be in the form of an equation, displaying the original number as the sum (or difference) of powers of 2.

Example 1:

For n = 13:

The binary representation of 13 is 1101.
This corresponds to 2^3 + 2^2 + 2^0, because the 3rd, 2nd, and 0th positions in the binary number are 1.

Output: 13 = 2^3 + 2^2 + 2^0

Explanation:

The function f4(n) converts an integer n into a sum of powers of 2 based on its binary representation. Let’s go through the code:

1. Handling the case when n is zero:

   1 2 3

   if not n: print('0 = 0') return

   This part checks if n is zero using if not n. If n is zero, the function prints 0 = 0 and returns immediately, since zero doesn’t need further decomposition into powers of 2.

2. Converting the number to binary:

   1	binary_n = f'{n:b}'

   The f'{n:b}' converts the integer n to its binary form as a string (without the 0b prefix). For example, if n = 13, binary_n will be 1101.

3. Finding the positions of 1s in the binary representation:

   1	powers = (i for i in range(len(binary_n)) if binary_n[i] == '1')

   This list comprehension creates a list of indices where the binary digit is 1. For 1101, the positions list will be [0, 2, 3].

   • This is a generator expression that finds the positions (indices) in the binary string where there is a 1.
   • range(len(binary_n)) iterates over each character in the binary string, and the condition binary_n[i] == '1'filters out the positions where there is a 1.
   • For example, if n = 13 and binary_n = '1101', the positions of 1s would be (0, 2, 3), because the first, third, and fourth bits from the right are 1.

4. print(operator.join(f’2^{len(binary_n) - i - 1}’ for i in powers))

   1	print(operator.join(f'2^{len(binary_n) - i - 1}' for i in powers))

   • This is the key part of the function that prints the powers of 2 based on the positions of 1s in the binary representation.
     • f'2^{len(binary_n) - i - 1}' creates strings like 2^3, 2^2, 2^0 by converting each position i into the corresponding exponent for 2. The exponent is calculated as len(binary_n) - i - 1, where i is the position of the 1 in the binary string.
     • operator.join(...) joins all these terms together with either' + 'or' - 'depending on the value of n.

Exercise 5

To solve next problems, lets first understand the zip function in Python.

1. Let’s try:

1
2
3

L1 = [1, 2, 3]
L2 = [4, 5, 6]
print(list(zip(L1, L2)))

Output:

1

[(1, 4), (2, 5), (3, 6)]

And zip in dictionary:

1
2
3

L1 = [1, 2, 3]
L2 = [4, 5, 6]
print(dict(zip(L1, L2)))

Output:

1
2

[(1, 4), (2, 5), (3, 6)]
{1: 4, 2: 5, 3: 6}

The finally we try using zip with *, which is used to unpack the elements of a list or tuple:

1
2
3
4
5
6

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in zip(L):
    print(i)

for i in zip(*L):
    print(i)

Output:

1
2
3
4
5
6

([1, 2, 3],)
([4, 5, 6],)
([7, 8, 9],)
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)

Problem Description

In this problem, we can identify the pattern by observing the example: start from the first and last elements of a list and progressively make pairs towards the center of the list.

My initial thought was to use a two-pointer approach: one pointer starts at the beginning of the list, and the other starts at the end, and they move towards each other. However, I missed the specific requirement in the problem: “Return an expression built only from list, reversed, and zip.”

Wrong Solution:

1
2
3
4
5
6
7
8
9

def f5(*L):
    ans = []
    left = 0
    right = len(L) - 1
    while left < len(L):
        ans.append(((L[left], L[right]), (L[right], L[left])))
        left += 1
        right -= 1
    return ans

Correct Solution:

1
2

def f5(*L):
    return list(zip(zip(L, reversed(L)), reversed(list(zip(L, reversed(L))))))

The idea behind the correct solution is as follows:

1. zip(L, reversed(L)) creates pairs of elements where the first comes from L and the second comes from reversed(L) (i.e., L reversed).
   Example: If L = (1, 2, 3), then reversed(L) is (3, 2, 1). So, zip(L, reversed(L)) results in [(1, 3), (2, 2), (3, 1)].

2. reversed(list(zip(L, reversed(L)))): Here, we convert the result of zip(L, reversed(L)) into a list and then reverse the entire list.
   Example: If zip(L, reversed(L)) produced [(1, 3), (2, 2), (3, 1)], then reversed(list(zip(L, reversed(L)))) will return [(3, 1), (2, 2), (1, 3)].

3. zip(zip(L, reversed(L)), reversed(list(zip(L, reversed(L))))): This part pairs the result of zip(L, reversed(L)) with its reversed version. It takes corresponding elements from both sequences and forms pairs.
   Example: If zip(L, reversed(L)) is [(1, 3), (2, 2), (3, 1)] and its reverse is [(3, 1), (2, 2), (1, 3)], then zip(zip(L, reversed(L)), reversed(list(zip(L, reversed(L))))) produces pairs of tuples like:

   • ((1, 3), (3, 1))
   • ((2, 2), (2, 2))
   • ((3, 1), (1, 3))

Finally, this expression is wrapped in list() to convert the zip object into a list of tuples.

Exercise 6

Problem Description

Exercise 6 is similar to Exercise 5, requiring us to use zip, *, and list to solve the problem. We are given a variable number of arguments *L, and the goal is to output them in the form of [(...), (...)]. This task is simpler than the previous one, as the pairing only needs to reverse and mirror the elements.

At first, I attempted the following approach:

Wrong Solution:

1
2

def f6(*L):
    return list(zip(zip(L, reversed(L)), zip(reversed(L), L)))

I tried using zip to pair elements in forward and reverse order:

zip(L, reversed(L)) pairs the elements of L with the reversed version of L, while zip(reversed(L), L) pairs them in the reverse order.

However, the output of this solution was:

[((0, 1), (1, 0)), ((1, 0), (0, 1))]

This did not meet the requirements, as the pairs (0, 1) and (1, 0) were grouped separately. The correct format should have 0, 1, 1, 0 in the same tuple.

Correct Solution:

1
2

def f6(*L):
    return list(zip(*zip(L, reversed(L)), *zip(reversed(L), L)))

Explanation of the Fix:

To achieve the desired output, we need to flatten or “unpack” the pairs created by zip(L, reversed(L)) and zip(reversed(L), L) into individual elements and combine them correctly. This is where the * operator comes in, which unpacks the results from the zip function.

By using * before zip(L, reversed(L)) and zip(reversed(L), L), you effectively unpack the tuples into separate elements, allowing the outer zip function to combine them in the desired form.

• *zip(L, reversed(L)): This unpacks the paired tuples from L and reversed(L). Instead of getting pairs like (0, 1), it unpacks them into 0, 1, 1, 0.

• *zip(reversed(L), L): Similarly, this unpacks the reversed pairs.

The final zip call then combines these unpacked elements into the correct tuple format. The result is:

[(0, 1, 1, 0), (1, 0, 0, 1)]

This ensures that the mirrored pairs are placed together in the same tuple as required by the problem.

Description：

Darts
https://interunia.unswcpmsoc.com/task/Darts/

Thinking：

This contest is harder than I imaged, this is the second task, and I spent a lot of time but when I checked the Leaderboard and no one has solved it yet, I feel a little bit better.
At first, I thought of simply judging whether this point is in the middle of this circle, using Euclidean distance calculation. But later I found that when there are n circles and m darts, the amount of data is surprisingly large. After the brute force cracking timed out, I had to consider a new method.

We can use the gridded Spatial Indexing, the specific steps are as follows:

1. Spatial division: Divide the entire plane into grids of equal size (Grid), and map the target and dart to the corresponding grid.

Purpose:

• Reduce the number of targets that need to be calculated.
• For each dart, you only need to check the targets in its grid and adjacent grids.

2. Map Targets to Grids:

• Calculate the bounding box of each target.
  • Lower-left corner: ( (x_i - r_i, y_i - r_i) )
  • Upper-right corner: ( (x_i + r_i, y_i + r_i) )
• Record all grid cells covered by this rectangle and add the target index to these grid cells.

3. Map Darts to Grids:

For each dart, calculate the grid coordinates where it is located.

4. Check if the Dart Hits a Target:

• For each dart, check all targets in its grid and the adjacent 8 grids.
• Calculate the distance from the dart to the center of each target and determine whether it is less than or equal to the square of the target’s radius, i.e., ( (dx - x_i)^2 + (dy - y_i)^2 \leq r_i^2 ).

Grid Division Parameters

Grid size (GRID_SIZE):

• Choose an appropriate grid size, such as 500.
• The choice of grid size requires a trade-off between space and time efficiency.

1
2
3
4
5

auto get_grid_cell = [&](long long x_n, long long y_n) {
    int gx = int((x_n - min_x) / s);
    int gy = int((y_n - min_y) / s);
    return make_pair(gx, gy);
};

Coordinate mapping function:

Maps actual coordinates to grid coordinates.

• s is the actual length of each grid cell.
• $min_x$ and $min_y$ are the minimum values among all target and dart coordinates, used to shift the coordinates.

Mapping Targets to Grids

• Iterate over all targets and calculate their covered grid ranges.
• In these grids, record the indices of the targets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

for (int idx = 0; idx < n; ++idx) {
    int x, y, r;
    tie(x, y, r) = circles[idx];
    long long x_min = x - r;
    long long x_max = x + r;
    long long y_min = y - r;
    long long y_max = y + r;
    auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
    auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
    for (int gx = gx_min; gx <= gx_max; ++gx) {
        for (int gy = gy_min; gy <= gy_max; ++gy) {
            long long key = get_grid_key(gx, gy);
            grid[key].push_back(idx); // 存储靶子索引
        }
    }
}

Mapping Darts to Grids

• For each dart, calculate the grid cell it belongs to.
• No need to store darts in grids; we process them directly.

Checking if Darts Hit Targets

• For each dart, get its grid coordinates ( (gx, gy) ).
• Check the dart’s grid cell and its 8 adjacent grid cells.
• For each target in these grids, calculate the distance to the dart.
• If the distance squared is less than or equal to the target’s radius squared, increment the counter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

for (const auto& p : points) {
    int dx = p.first;
    int dy = p.second;
    auto [gx, gy] = get_grid_cell(dx, dy);
    bool found = false;
    
    // Check the grid and the 8 adjacent grids
    for (int ix = gx - 1; ix <= gx + 1; ++ix) {
        for (int iy = gy - 1; iy <= gy + 1; ++iy) {
            long long key = get_grid_key(ix, iy);
            if (grid.count(key)) {
                const auto& circle_indices = grid[key];
                for (int idx : circle_indices) {
                    int x, y, r;
                    tie(x, y, r) = circles[idx];
                    // caculate the distance
                    long long dx_sq = (long long)(dx - x) * (dx - x);
                    long long dy_sq = (long long)(dy - y) * (dy - y);
                    long long r_sq = (long long)r * r;
                    if (dx_sq + dy_sq <= r_sq) {
                        ans++;
                        found = true;
                        break; // The dart has found the target, check the next dart
                    }
                }
            }
            if (found) break;
        }
        if (found) break;
    }
}

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

import math

n, m = map(int, input().split())

circles = []

min_x = min_y = float('inf')
max_x = max_y = float('-inf')

for _ in range(n):
    x, y, r = map(int, input().split())
    circles.append((x, y, r))
    min_x = min(min_x, x - r)
    max_x = max(max_x, x + r)
    min_y = min(min_y, y - r)
    max_y = max(max_y, y + r)

points = []

for _ in range(m):
    dx, dy = map(int, input().split())
    points.append((dx, dy))
    min_x = min(min_x, dx)
    max_x = max(max_x, dx)
    min_y = min(min_y, dy)
    max_y = max(max_y, dy)

GRID_SIZE = 500
delta_x = max_x - min_x
delta_y = max_y - min_y
s = max(delta_x, delta_y) / GRID_SIZE
if s == 0:
    s = 1

# Function that maps coordinates to grid indices
def get_grid_cell(x_n, y_n):
    gx = int((x_n - min_x) / s)
    gy = int((y_n - min_y) / s)
    return gx, gy

grid = {}

# Mapping the targets onto the grid
for idx, (x, y, r) in enumerate(circles):
    x_min = x - r
    x_max = x + r
    y_min = y - r
    y_max = y + r
    gx_min, gy_min = get_grid_cell(x_min, y_min)
    gx_max, gy_max = get_grid_cell(x_max, y_max)
    for gx in range(gx_min, gx_max + 1):
        for gy in range(gy_min, gy_max + 1):
            if (gx, gy) not in grid:
                grid[(gx, gy)] = []
            grid[(gx, gy)].append(idx)  # store the target index

ans = 0

# For each dart, check the target in the grid where it is located
for dx, dy in points:
    gx, gy = get_grid_cell(dx, dy)
    found = False
    if (gx, gy) in grid:
        for idx in grid[(gx, gy)]:
            x, y, r = circles[idx]
            # Determine if the dart is in the target
            if (dx - x) ** 2 + (dy - y) ** 2 <= r ** 2:
                ans += 1
                found = True
                break  # 找到后跳出循环
    # The grids do not overlap and the surrounding grids are not detected?

print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    // Fast input/output
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> circles;
    long long min_x = LLONG_MAX, min_y = LLONG_MAX;
    long long max_x = LLONG_MIN, max_y = LLONG_MIN;

    // Read circles and update bounding box
    for (int i = 0; i < n; ++i) {
        int x, y, r;
        cin >> x >> y >> r;
        circles.emplace_back(x, y, r);
        min_x = min(min_x, (long long)x - r);
        max_x = max(max_x, (long long)x + r);
        min_y = min(min_y, (long long)y - r);
        max_y = max(max_y, (long long)y + r);
    }

    vector<pair<int, int>> points;

    // Read darts and update bounding box
    for (int i = 0; i < m; ++i) {
        int dx, dy;
        cin >> dx >> dy;
        points.emplace_back(dx, dy);
        min_x = min(min_x, (long long)dx);
        max_x = max(max_x, (long long)dx);
        min_y = min(min_y, (long long)dy);
        max_y = max(max_y, (long long)dy);
    }

    const int GRID_SIZE = 500;
    long long delta_x = max_x - min_x;
    long long delta_y = max_y - min_y;
    double s = max(delta_x, delta_y) / (double)GRID_SIZE;
    if (s == 0) {
        s = 1;
    }

    // Function to get grid cell indices
    auto get_grid_cell = [&](long long x_n, long long y_n) {
        int gx = int((x_n - min_x) / s);
        int gy = int((y_n - min_y) / s);
        return make_pair(gx, gy);
    };

    // Function to combine gx and gy into a single key
    auto get_grid_key = [](int gx, int gy) -> long long {
        return ((long long)gx << 32) | (unsigned int)gy;
    };

    // Map from grid cell key to list of circle indices
    unordered_map<long long, vector<int>> grid;

    // Map circles to grid cells
    for (int idx = 0; idx < n; ++idx) {
        int x, y, r;
        tie(x, y, r) = circles[idx];
        long long x_min = x - r;
        long long x_max = x + r;
        long long y_min = y - r;
        long long y_max = y + r;
        auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
        auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
        for (int gx = gx_min; gx <= gx_max; ++gx) {
            for (int gy = gy_min; gy <= gy_max; ++gy) {
                long long key = get_grid_key(gx, gy);
                grid[key].push_back(idx); // Store circle index
            }
        }
    }

    int ans = 0;

    // For each dart, check circles in its grid cell and adjacent cells
    for (const auto& p : points) {
        int dx = p.first;
        int dy = p.second;
        auto [gx, gy] = get_grid_cell(dx, dy);
        bool found = false;

        // Check the dart's grid cell and its 8 neighbors
        for (int ix = gx - 1; ix <= gx + 1; ++ix) {
            for (int iy = gy - 1; iy <= gy + 1; ++iy) {
                long long key = get_grid_key(ix, iy);
                if (grid.count(key)) {
                    const auto& circle_indices = grid[key];
                    for (int idx : circle_indices) {
                        int x, y, r;
                        tie(x, y, r) = circles[idx];
                        // Check if the dart is inside the circle
                        long long dx_sq = (long long)(dx - x) * (dx - x);
                        long long dy_sq = (long long)(dy - y) * (dy - y);
                        long long r_sq = (long long)r * r;
                        if (dx_sq + dy_sq <= r_sq) {
                            ans++;
                            found = true;
                            break; // Move to next dart
                        }
                    }
                }
                if (found) break;
            }
            if (found) break;
        }
    }

    cout << ans << '\n';
    return 0;
}

Slide 1: Introduction

Today, we are going to walk through six Python functions that perform various tasks involving integers, lists, and text files. Each function demonstrates different ways to manipulate data, including string formatting, list processing, and reading from files.

Slide 2: Function 1 - f1(m, n)

The first function, f1, generates a simple string pattern. Here’s how it works:

1
2

def f1(m, n):
    return ('|' + '_' * n + '|') * m

1. The function takes two integer arguments, m and n. Both are assumed to be at least 0.
2. It constructs a pattern consisting of vertical bars (|) enclosing underscores (_), repeated m times. The number of underscores between the bars is determined by n.
3. For example, if m = 3 and n = 4, the output would be:

1

|____||____||____|

Slide 3: Function 2 - f2(n)

The second function, f2, creates a square pattern made up of digits. Here’s the function:

1
2

def f2(n):
    return (str(n) * n + '\n') * n

1. This function takes an integer n and generates a square of n rows, where each row contains the digit n repeated n times.
2. The pattern ends with a newline after each row.
3. For example, if n = 3, the output will be:

1
2
3

333
333
333

Slide 4: Function 3 - f3(L)

Next, we have f3, which works on a list of integers:

1
2
3
4

def f3(L):
    while len(L) > 1 and L[0] > L[1]:
        L.remove(L[0])
    print(L)

1. This function removes elements from the start of the list until the first two consecutive elements are in non-decreasing order.
2. The process continues as long as the first element is strictly greater than the second element.
3. Once the list is stable, it prints the modified list.
4. For example, if L = [9, 8, 7, 10], the function will remove 9, 8, and 7, leaving [10].

Slide 5: Function 4 - f4(D, n)

The fourth function, f4, works with dictionaries:

1
2
3
4
5
6
7
8

def f4(D, n):
    if n not in D:
        return []
    ans = [n]
    while n in D and D[n] > n:
        ans.append(D[n])
        n = D[n]
    return ans

1. This function takes a dictionary D and an integer n. It generates a strictly increasing sequence of integers based on the relationships defined in the dictionary.
2. Starting from n, it appends D[n], D[D[n]], and so on to the list, as long as each subsequent value is greater than the previous one.
3. For example, if D = {1: 2, 2: 3, 3: 5} and n = 1, the function will return [1, 2, 3, 5].

Slide 6: Function 5 - f5(filename)

The fifth function, f5, reads from a file and processes each line:

1
2
3
4
5
6

def f5(filename):
    with open(filename) as f:
        for i in f:
            name, number = i.split(',')
            number = int(number) * 1000
            print(f"{number} people named {name}")

1. This function reads a text file, where each line consists of a name and a count separated by a comma.
2. The function multiplies the count by 1000 and prints the result in the format: “X people named Y”.
3. For example, if the file contains a line “John,5”, it will print:

1

5000 people named John

Slide 7: Function 6 - f6(filename)

The final function, f6, also reads from a text file, but with a different format:

1
2
3
4
5
6

def f6(filename):
    with open(filename) as f:
        for i in f:
            if not i.isspace():
                number, charactor = i.split()
                print(int(number) * charactor)

1. This function reads lines that contain an integer followed by a symbol (e.g., “5 *”).
2. It multiplies the symbol by the integer and prints the result.
3. For example, if the file contains the line “3 # “, the function will print:

1

### 

longsizhuo123.github.io

“Maybe it could be a nice memory”

Welcome to my personal blog repository on Github! My name is Sizhuo Long, and I am currently a student in Australia. This repository is home to my personal blog, which is built using the HEXO static site generator.

On my blog, you’ll find a variety of content including my thoughts on technology, programming, and the latest developments in my field of study. I also share my experiences and lessons learned from the projects I’ve worked on.

I hope that by sharing my knowledge and insights, I can help others who are interested in the same topics. I welcome any comments and feedback, and I am always open to collaboration.

Thank you for visiting my blog, I hope you will find something interesting here. And I would really appreciate it if you could pay more attention to my blog and follow me.

Why you should follow me

• I’ll share my personal experiences and thoughts on technology and programming
• I’ll keep you updated on the latest developments in my field of study
• I’m open to collaboration and feedback.

How to contact me

• Email: longsizhuo@gmail.com
• LinkedIn: Sizhuo Long
• XiaoHongShu(Small RedBook): @sizhuo_long

Thank you for reading, and I hope you enjoy my blog!

Single -cellRNAData analysis tool
The project I did before，There are many errors，Don’t spray。
Shu Di Travel Bacteria
This is a small assignment when I was a second junior year，It’s a group operation。At first I couldn’t get the linkhtmldocument，I read a lot of official documents orCSDNdocument
。Finally read an article，Said to beHEXODang thegeneratewhen，I willsource中的documentappendarrivepublicMiddle，I tried many times later，Discover directly
public为源document夹，Just call the directory。Although this will cause it to be unable to bemddocument中超链接arrivedocument。

at the same time，也exist新的bugunsolved：login.htmlUnable toindex.htmlJump
Linkin:

Question:

4
1 3
2 4
199999 200000
19 84

5
6
36
263

My think:

At first, I thought it was a simple simulation problem: calculate the number of times x when the smallest
number divided by 3 equals 0, and then the answer would be x * 2 plus the number of remaining times when
the left number divided by 3 equals 0. However, this approach is incorrect.

By utilizing the characteristics of exponential growth and performing some simple
calculations, we can quickly determine the minimum number of operations within a given range.
This method has a low time complexity and can efficiently handle large input ranges.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import math
t = int(input())
for i in range(t):
    num = list(map(int, input().split()))
    l = num[0]
    r = num[1]
    start_pow3 = 1
    cnt_start = 1
    while start_pow3 <= (l / 3):
        start_pow3 *= 3
        cnt_start += 1
    ans = cnt_start
    pow3 = start_pow3
    next_pow3 = start_pow3 * 3
    while pow3 <= r:
        ans += (min(r + 1, next_pow3) - max(l, pow3)) * cnt_start
        cnt_start += 1
        pow3 *= 3
        next_pow3 *= 3
    print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def min_operations_to_zero(n):
    operations = 0
    while n > 0:
        n = n // 3
        operations += 1
    return operations

t = int(input())
results = []
for _ in range(t):
    l, r = map(int, input().split())
    total_operations = 0
    oper = min_operations_to_zero(l)
    for n in range(l+1, r+1):
        total_operations += min_operations_to_zero(n)
    total_operations += oper*2
    results.append(total_operations)

for result in results:
    print(result)

topic：

“””

Given m x n grid  grid middle，Each cell can have one of the following three values：

• value 0 Represents the empty unit；
• value 1 Represents fresh oranges；
• value 2 代表Rotten orange。

every minute，Rotten orange around 4 Adjacent in this direction Fresh oranges will rot。

return 直到单元格middle没有新鲜橘子为止所必须经过的最小分钟数。If it is impossible，return -1 。

Exemplary example 1：

enter：grid = [[2,1,1],[1,1,0],[0,1,1]]
Output：4

Exemplary example 2：

enter：grid = [[2,1,1],[0,1,1],[1,0,1]]
Output：-1
explain：Orange in the lower left corner（First 2 OK， First 0 List）Never rot，Because rotten will only happen in 4 In the direction。

Exemplary example 3：

enter：grid = [[0,2]]
Output：0
explain：because 0 There is no fresh orange in minutes，So the answer is 0 。

hint：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] Only for 0、1 or 2

Thought：

这个问题可以用Priority search（BFS）To solve。We need to track the spread of rotten oranges，Record time，And check if there is a fresh orange that cannot be rotten。The initial idea of ​​the original idea：

1
2
3
4
5
6
7
8
9

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        bad_orange = []
        # 找到所有初始Rotten orange
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    # 存入初始队List
                    bad_orange.append((i, j))

Similar to multi -threaded，每个线程存入一个初始队List，初始队List通过BFSGradual diffusion

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        bad_orange = deque()
        fresh_oranges = 0
        rows, cols = len(grid), len(grid[0])
        
        # 找到所有初始Rotten orange，And calculate the number of fresh oranges
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 2:
                    bad_orange.append((i, j))
                elif grid[i][j] == 1:
                    fresh_oranges += 1
        
        # 方向Array：up down left right
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        # If there is no fresh orange，直接return 0
        if fresh_oranges == 0:
            return 0
        
        # BFS
        minutes = 0
        while bad_orange:
            minutes += 1
            for _ in range(len(bad_orange)):
                x, y = bad_orange.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                        grid[nx][ny] = 2
                        fresh_oranges -= 1
                        bad_orange.append((nx, ny))
        
        # If there are fresh oranges，return -1
        return minutes - 1 if fresh_oranges == 0 else -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

import (
	"sync"
)

func orangesRotting(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	badOranges := make([][2]int, 0)
	freshOranges := 0

	// 找到所有初始Rotten orange，And calculate the number of fresh oranges
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == 2 {
				badOranges = append(badOranges, [2]int{r, c})
			} else if grid[r][c] == 1 {
				freshOranges += 1
			}
		}
	}

	// If there is no fresh orange，直接return 0
	if freshOranges == 0 {
		return 0
	}

	directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	minutes := 0

	var wg sync.WaitGroup

	// BFS
	for len(badOranges) > 0 {
		minutes++
		nextBadOranges := make([][2]int, 0)
		for _, orange := range badOranges {
			x, y := orange[0], orange[1]
			wg.Add(1)
			go func(x, y int) {
				defer wg.Done()
				for _, d := range directions {
					nx, ny := x+d[0], y+d[1]
					if nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1 {
						grid[nx][ny] = 2
						nextBadOranges = append(nextBadOranges, [2]int{nx, ny})
						freshOranges--
					}
				}
			}(x, y)
		}
		wg.Wait()
		badOranges = nextBadOranges
	}

	// If there are fresh oranges，return -1
	if freshOranges > 0 {
		return -1
	}
	return minutes - 1
}

topic：

1017. Negative binary conversion

Thought：

The difference from binary is just not always//2，It’s every number//-1

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def baseNeg2(self, n: int) -> str:
        k = 1
        ans = []
        while n:
            if n % 2:
                ans.append('1')
                n -= k
            else:
                ans.append('0')
            n //= 2
            k *= -1
        return ''.join(ans[::-1]) or '0' 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn base_neg2(mut n: i32) -> String {
        let mut ans = Vec::new();
        while n != 0 {
            if n % 2 != 0 {
                ans.push('1');
                n = (n - 1) / -2;
            } else {
                ans.push('0');
                n /= -2;
            }
        }
        if ans.is_empty() {
            ans.push('0');
        }
        ans.reverse();
        ans.iter().collect()
    }
}

topic：

Give you an integer n ，Return to the integer in the form of a binary string Negative binary（base -2）express。

Notice，Unless the string is "0"，Otherwise, the returned string cannot contain the front guide zero。

Exemplary example 1：

enter：n = 2
Output："110"
explain：(-2)2 + (-2)1 = 2

Exemplary example 2：

enter：n = 3
Output："111"
explain：(-2)2 + (-2)1 + (-2)0 = 3

Exemplary example 3：

enter：n = 4
Output："100"
explain：(-2)2 = 4

hint：

• 0 <= n <= 109

Thought：

We can judge n Every bit from low to high，If the bit is 1，Then the answer is 1，Otherwise 0。If the bit is 1，So we need to n minus k。Next we update n=⌊n/2⌋, k=−k。Continue to judge the next。
at last，We will return to the answer。
time complexity O(logn)，in n For the given integer。Ignore the space consumption of the answer，Spatial complexity O(1)。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def baseNeg2(self, n: int) -> str:
        k = 1
        ans = []
        while n:
            if n % 2:
                ans.append('1')
                n -= k
            else:
                ans.append('0')
            n //= 2
            k *= -1
        return ''.join(ans[::-1]) or '0'

topic：

1124. The longest period of performance.md

Thought：

This question is not，I thought it was a double pointer but timeout over time，结果是Prefix and算法。The following isSpiritual godSolution
通过Prefix and，我们可以把Elements and elements of sub -array转换成两个Prefix and的差，Right now
$$
\sum_{j=left}^{right} nums[j] = \sum_{j=0}^{right} nums[j]− \sum_{j=0}^{left-1} nums[j]=s[right+1]−s[left]
$$
Now that I said it「Elements and elements of sub -array」，那么利用Prefix and s，Turn the problem to：
Find two bidding i and j，satisfy j<ij<ij<i and s[j]<s[i]，maximize i−jValue。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans = 0
        for index, i in enumerate(hours):
            count = 0
            j = index
            while j < len(hours):
                if hours[j] <= 8:
                    count -= 1
                elif hours[j] > 8:
                    count += 1
                if count > 0:
                    ans = max(ans, j - index + 1)
                j += 1
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        s = [0] * (n + 1)
        st = [0]
        for j, h in enumerate(hours, 1):
            s[j] = s[j - 1] + (1 if h > 8 else -1)
            if s[j] < s[st[-1]]:
                st.append(j)
        ans = 0
        for i in range(n, 0 , -1):
            while st and s[i] > s[st[-1]]:
                ans = max(ans, i-st.pop())
        return ans