chat

🔍

question:You are given an array of integers and a target sum. Your task is to determine if there exist two distinct elements in the array such that their sum is equal to the target sum. If such a pair exists, return the indices of the two elements in the form of a list. Otherwise, return an empty list. However, there's a twist: 1. You must find the first pair (if multiple pairs exist) that appears in the array. 2. The output list must have the smallest index first. INPUT The first line contains an integer T, the number of test cases. For each test case: - The first line contains an integer N, the number of elements in the array. - The second line contains N integers, representing the elements of the array. - The third line contains an integer K, the target sum. OUTPUT For each test case, output a list containing the indices of the two elements that sum up to the target, or an empty list if no such pair exists. Constraints 1 ≤ T ≤ 100 2 ≤ N ≤ 100 -10^5 ≤ array elements ≤ 10^5 -10^5 ≤ K ≤ 10^5 SAMPLE INPUT 2 5 1 2 3 4 5 9 4 1 0 -1 2 6 SAMPLE OUTPUT [3, 4] [] Explanation In the first test case, the array is [1, 2, 3, 4, 5]. The only pair whose sum is 9 is (4, 5) at indices 3 and 4. In the second test case, the array is [1, 0, -1, 2]. There is no pair whose sum is 6. Hence, the output is an empty list.

answer:def find_indices_of_two_sum(arr, target): Returns the indices of the first pair of elements in the array that sum up to the target. index_map = {} for i, num in enumerate(arr): complement = target - num if complement in index_map: return [index_map[complement], i] index_map[num] = i return [] def process_test_cases(test_cases): Processes multiple test cases. results = [] for case in test_cases: N, arr, K = case['N'], case['arr'], case['K'] result = find_indices_of_two_sum(arr, K) results.append(result) return results

question:Santa is trying to decorate a Christmas tree using colored balls. He wants to hang the balls in such an order that the color of adjacent balls is always different. Santa has n balls and each ball has a particular color. He wants to know whether it is possible to arrange the balls in the required order and if possible, give such an arrangement. Input The first line contains an integer n (1 ≤ n ≤ 1000) — the number of balls. The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 1000) — the colors of the balls in the initial order. Output If it is possible to arrange the balls as required, print "YES" on the first line and then print the arrangement on the second line. If it is not possible, print "NO". Examples Input 3 1 2 1 Output YES 1 2 1 Input 4 1 1 1 1 Output NO Input 6 1 2 3 4 5 1 Output YES 1 2 3 4 1 5 Note In the first example, the initial order of the balls already satisfies the requirement, so it is printed as it is. In the second example, since all balls have the same color, it is impossible to rearrange them such that no two adjacent balls have the same color. In the third example, one possible valid rearrangement is shown, but other valid rearrangements are also possible.

answer:def can_arrange_balls(n, colors): from collections import Counter color_count = Counter(colors) if any(count > (n + 1) // 2 for count in color_count.values()): return "NO" sorted_colors = sorted(color_count.items(), key=lambda x: -x[1]) result = [0] * n index = 0 for color, count in sorted_colors: for _ in range(count): result[index] = color index += 2 if index >= n: index = 1 return "YES", result

question:You are given a string consisting of lowercase Latin letters. Let's call a string beautiful if no two adjacent characters are the same. Your task is to find the minimum number of characters needed to be removed to make the string beautiful. If the given string is already beautiful, output 0. Input The first line contains a single integer n (1 ≤ n ≤ 1000) — the length of the string. The second line contains a string of length n consisting of lowercase Latin letters. Output Return the minimum number of characters needed to be removed to make the string beautiful. Examples Input 5 abaaa Output 2 Input 8 aabbccdd Output 4 Input 6 abcdef Output 0

answer:def min_removals_to_beautiful(n, s): Returns the minimum number of characters needed to be removed to make the string beautiful (no two adjacent characters are the same). removals = 0 for i in range(1, n): if s[i] == s[i - 1]: removals += 1 return removals

question:Write a program that determines if a given maze is solvable. The maze is represented by a grid of characters, where an 'S' denotes the starting point, an 'E' denotes the ending point, '.' denotes an open path, and '#' denotes a wall. You may move up, down, left, or right, but you cannot move diagonally. Your task is to determine whether there is a path from 'S' to 'E'. Input The first line contains a single integer T (1 ≤ T ≤ 10), the number of test cases. Each test case starts with two integers N and M (1 ≤ N, M ≤ 100), the dimensions of the maze grid. The next N lines each contain a string of length M, representing the maze grid. Each string may contain 'S', 'E', '.', or '#'. There will always be exactly one 'S' and one 'E' in each grid. Output For each test case, print a single line containing "YES" if there is a path from 'S' to 'E', otherwise print "NO". Example Input 2 5 5 S.... .#. .#..E .#. ..... 3 3 S#E # #.# Output YES NO

answer:def is_solvable(T, tests): def dfs(x, y, visited): if not (0 <= x < N and 0 <= y < M) or (x, y) in visited or grid[x][y] == '#': return False if grid[x][y] == 'E': return True visited.add((x, y)) return ( dfs(x + 1, y, visited) or dfs(x - 1, y, visited) or dfs(x, y + 1, visited) or dfs(x, y - 1, visited) ) results = [] for test in tests: N, M, grid_data = test grid = [list(line) for line in grid_data] start = end = None for i in range(N): for j in range(M): if grid[i][j] == 'S': start = (i, j) elif grid[i][j] == 'E': end = (i, j) if not start or not end: results.append("NO") continue visited = set() result = dfs(start[0], start[1], visited) results.append("YES" if result else "NO") return results T = 2 tests = [ (5, 5, [ "S....", ".#.", ".#..E", ".#.", "....." ]), (3, 3, [ "S#E", "#", "#.#" ]) ] print(is_solvable(T, tests))