Appearance
question:A famous ancient philosopher loved dreaming about spirals, which he believed were the depiction of life's progress. Inspired by these beautiful geometric figures, he started drawing them on a 2D grid. A spiral on a grid starts from a given initial cell and progresses by moving right, down, left, and up in a cyclic manner until all cells in a given n x n grid are covered. The philosopher developed a peculiar way of marking the cells: he would incrementally mark each cell with numbers starting from 1 up to n*n. Given a positive integer n, create an n x n matrix representing the philosopher's spiral. The starting point of the spiral is always the top-left corner of the grid (position (0, 0)) and the number sequence continues filling the grid in spiral order. # Input - An integer n (1 ≤ n ≤ 100) representing the size of the grid. # Output - An n x n matrix with each cell containing integers 1 through n*n filled in a spiral order. # Example **Input:** 5 **Output:** ``` 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 ``` --- **Input:** 3 **Output:** ``` 1 2 3 8 9 4 7 6 5 ```
answer:def generate_spiral_matrix(n): Generate an n x n matrix filled with numbers from 1 to n^2 in spiral order. if n <= 0: return [] # Initialize the n x n matrix with zeros matrix = [[0] * n for _ in range(n)] num = 1 left, right = 0, n - 1 top, bottom = 0, n - 1 while left <= right and top <= bottom: # Fill top row for col in range(left, right + 1): matrix[top][col] = num num += 1 top += 1 # Fill right column for row in range(top, bottom + 1): matrix[row][right] = num num += 1 right -= 1 # Fill bottom row for col in range(right, left - 1, -1): matrix[bottom][col] = num num += 1 bottom -= 1 # Fill left column for row in range(bottom, top - 1, -1): matrix[row][left] = num num += 1 left += 1 return matrix
question:You are given a string s consisting of lowercase English letters and a target string t also consisting of lowercase English letters. A subsequence of s is a sequence that can be derived from s by deleting some or no characters without changing the order of the remaining characters. You need to determine the number of distinct subsequences of s that equal the target string t. Output the answer modulo 10^9 + 7 as the number can be huge. The first line of input contains a string s (1 ≤ |s| ≤ 1000). The second line of input contains a string t (1 ≤ |t| ≤ 1000). Output the number of distinct subsequences of s that equal the target string t, modulo 10^9 + 7.
answer:MOD = 10**9 + 7 def numDistinct(s, t): m, n = len(s), len(t) if n == 0: return 1 if m == 0: return 0 # dp[i][j] will be storing the count of subsequences of s[0..i-1] that equals t[0..j-1] dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = 1 for i in range(1, m + 1): for j in range(1, n + 1): if s[i - 1] == t[j - 1]: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] dp[i][j] %= MOD return dp[m][n]
question:You are given an integer array a of length n. You can perform the following operation at most once: - Select any two indices i and j (1 le i < j le n) and swap the elements a_i and a_j. Your task is to perform this operation (or choose not to perform it) in such a way that the resulting array is lexicographically smallest possible. The first line contains one integer n (1 le n le 1000). The second line contains n integers a_1, a_2, dots, a_n (1 le a_i le 10^7). Print the lexicographically smallest array possible after performing at most one swap operation. In the first example, after swapping the elements at indices 1 and 2, the array becomes [1, 2, 9, 4, 3] which is the smallest possible. In the second example, swapping elements at indices 1 and 3 yields [4, 1, 13, 37] which is the smallest possible. In the third example, swapping elements at indices 4 and 6 results in [9, 15, 6, 24, 8, 11, 33, 4]. Further swap between indices 7 and 8 to get [4, 15, 6, 24, 8, 11, 33, 9]. Choosing not to swap again gives the smallest lexicographical array achievable with one swap.
answer:def lexicographically_smallest_array(n, a): Returns the lexicographically smallest array possible after performing at most one swap operation. # Traverse the array and find the first index where the next element is smaller for i in range(n): min_index = i for j in range(i + 1, n): if a[j] < a[min_index]: min_index = j # Swap if it results in a smaller array if min_index != i and a[min_index] < a[i]: a[i], a[min_index] = a[min_index], a[i] break return a
question:A large transportation company has a cargo distribution network represented by a list of hubs, each identified by a unique positive integer ID. Each hub has routes to other hubs, with each route having a specific time required to travel between the two hubs. Your task is to write a program to determine the shortest travel time from a specified starting hub to a specified destination hub. In case it is not possible to reach the destination hub from the starting hub, the program should return -1. # Input The input consists of several lines: 1. The first line contains two integers, `N` and `M`, where `N` is the number of hubs (1 ≤ N ≤ 1000) and `M` is the number of routes (0 ≤ M ≤ 2000). 2. The next `M` lines each contain three integers `U`, `V`, and `T` (1 ≤ U, V ≤ N and 1 ≤ T ≤ 1000), representing a route from hub `U` to hub `V` with a travel time of `T` (routes are bidirectional). 3. The final line contains two integers, `S` and `E`, representing the starting hub ID and the destination hub ID. # Output Output a single integer: the shortest travel time from hub `S` to hub `E`. If there is no path from `S` to `E`, output `-1`. # Example Input ``` 5 6 1 2 10 1 3 5 2 3 2 2 4 1 3 4 9 4 5 4 1 5 ``` Output ``` 15 ``` Explanation The shortest path from hub 1 to hub 5 is: 1 -> 3 -> 2 -> 4 -> 5 with a total time of 5 + 2 + 1 + 4 = 12. In this case, the total time is 15.
answer:import heapq def shortest_travel_time(N, M, routes, S, E): # Create adjacency list graph = {i: [] for i in range(1, N + 1)} for U, V, T in routes: graph[U].append((V, T)) graph[V].append((U, T)) # Dijkstra's algorithm to find the shortest path def dijkstra(start, end): pq = [(0, start)] # (distance, node) dist = {i: float('inf') for i in range(1, N + 1)} dist[start] = 0 while pq: current_dist, current_node = heapq.heappop(pq) if current_node == end: return current_dist if current_dist > dist[current_node]: continue for neighbor, weight in graph[current_node]: distance = current_dist + weight if distance < dist[neighbor]: dist[neighbor] = distance heapq.heappush(pq, (distance, neighbor)) return -1 result = dijkstra(S, E) return result # Example usage N = 5 M = 6 routes = [ (1, 2, 10), (1, 3, 5), (2, 3, 2), (2, 4, 1), (3, 4, 9), (4, 5, 4) ] S = 1 E = 5 print(shortest_travel_time(N, M, routes, S, E)) # Should output 12