Problem A: Character Frequency Analysis
Given a string of length 5 consisting only of characters 'A' and 'B', determine which character appears more frequently.
Input Format:
- The first line contains an integer t (1 ≤ t ≤ 32) - the number of test cases
- Each test case contains a single line with a string of length 5 containing only 'A' and 'B'
Output Format:
- For each test case, output either 'A' or 'B' indicating the character that appears most frequently
**Solution Approach:**We can solve this by simply counting the occurrences of each character and comparing them.
def analyze_frequency():
test_cases = int(input())
for _ in range(test_cases):
text = input().strip()
count_A = text.count('A')
count_B = text.count('B')
print('A' if count_A > count_B else 'B')
analyze_frequency()
Problem B: Shape Identification in Grid
Given an n×n binary grid, determine if the 1s form a triangle or a square.
Input Format:
- The first line contains t (1 ≤ t ≤ 100) - number of test cases
- Each test case starts with n (2 ≤ n ≤ 10) - grid size
- Followed by n lines of n characters (0 or 1)
Output Format:
- "SQUARE" if the 1s form a square
- "TRIANGLE" if the 1s form a triangle
**Solution Approach:**We need to check the pattern of 1s to determine if they form a square or triangle.
def identify_shape():
test_cases = int(input())
for _ in range(test_cases):
n = int(input())
grid = [input().strip() for _ in range(n)]
# Find the first '1' in the grid
start_row, start_col = -1, -1
for i in range(n):
for j in range(n):
if grid[i][j] == '1':
start_row, start_col = i, j
break
if start_row != -1:
break
# Determine shape by checking dimensions
height = 0
width = 0
while start_row + height < n and grid[start_row + height][start_col] == '1':
height += 1
while start_col + width < n and grid[start_row][start_col + width] == '1':
width += 1
# Check if all cells in the identified region are 1s
is_square = True
for i in range(height):
for j in range(width):
if grid[start_row + i][start_col + j] != '1':
is_square = False
break
if not is_square:
break
print("SQUARE" if is_square and height == width else "TRIANGLE")
identify_shape()
Problem C: Sum of Digit Sums
Calculate the sum of digit sums for numbers from 1 to n.
Input Format:
- The first line contains t (1 ≤ t ≤ 10⁴) - number of test cases
- Each test case contains a single integer n (1 ≤ n ≤ 2×10⁵)
Output Format:
- The sum of digit sums for numbers from 1 to n
**Solution Approach:**We can precompute the digit sums and use them to answer queries efficiently.
def sum_of_digit_sums():
MAX_N = 200000
digit_sum = [0] * (MAX_N + 1)
# Precompute digit sums
for i in range(1, MAX_N + 1):
num = i
while num > 0:
digit_sum[i] += num % 10
num //= 10
digit_sum[i] += digit_sum[i - 1]
test_cases = int(input())
for _ in range(test_cases):
n = int(input())
print(digit_sum[n])
sum_of_digit_sums()
Problem D: Bit Pattern Grouping
Given a list of integers, determine the minimum number of groups needed such that no two numbers in the same group have matching bits in positions 1-31.
Input Format:
- The first line contains t (1 ≤ t ≤ 10⁴) - number of test cases
- Each test case starts with n (1 ≤ n ≤ 2×10⁵) - number of integers
- Followed by n integers (0 ≤ a_j < 2³¹)
Output Format:
- The minimum number of groups required
**Solution Approach:**We can use a greedy approach with a map to track which numbers can be paired.
def bit_pattern_grouping():
from collections import defaultdict
test_cases = int(input())
for _ in range(test_cases):
n = int(input())
numbers = list(map(int, input().split()))
full_mask = (1 << 31) - 1
count_map = defaultdict(int)
groups = 0
for num in numbers:
complement = full_mask ^ num
if count_map[complement] > 0:
count_map[complement] -= 1
else:
groups += 1
count_map[num] += 1
print(groups)
bit_pattern_grouping()
Problem E: Card Ordering
Given n cards numbered 1 to n, determine the k-th card in a specific ordering pattern.
Input Format:
- The first line contains t (1 ≤ t ≤ 5×10⁴) - number of test cases
- Each test case contains n and k (1 ≤ k ≤ n ≤ 10⁹)
Output Format:
- The k-th card in the ordering
**Solution Approach:**We can determine the position by analyzing the pattern of odd multiples.
def find_kth_card():
test_cases = int(input())
for _ in range(test_cases):
n, k = map(int, input().split())
multiplier = 1
while multiplier <= n * 2:
cards_in_group = (n + multiplier // 2) // multiplier
if k <= cards_in_group:
result = k * multiplier - multiplier // 2
print(result)
break
k -= cards_in_group
multiplier <<= 1
find_kth_card()
Problem F: Grid Color Adjustment
Given a 7×7 grid of black and white cells, find the minimum operations to ensure no black cell has all four diagonal neighbors black.
Input Format:
- The first line contains t (1 ≤ t ≤ 200) - number of test cases
- Each test case contains 7 lines of 7 characters ('W' or 'B')
Output Format:
- The minimum number of opeartions needed
**Solution Approach:**We can use a backtracking approach to find the minimum flips required.
def adjust_grid():
test_cases = int(input())
for _ in range(test_cases):
grid = [input().strip() for _ in range(7)]
min_operations = float('inf')
def backtrack(row, col, operations):
nonlocal min_operations
if row == 5:
min_operations = min(min_operations, operations)
return
if col == 7:
backtrack(row + 1, 0, operations)
return
if (row + col) % 2 != 0:
backtrack(row, col + 1, operations)
return
# Check if current cell forms a problematic pattern
if (grid[row][col] == 'B' and grid[row+2][col] == 'B' and
grid[row+1][col+1] == 'B' and grid[row][col+2] == 'B' and
grid[row+2][col+2] == 'B'):
# Try flipping each of the 5 cells
for flip_row, flip_col in [(row, col), (row+2, col), (row+2, col+2), (row, col+2), (row+1, col+1)]:
grid[flip_row] = grid[flip_row][:flip_col] + ('W' if grid[flip_row][flip_col] == 'B' else 'B') + grid[flip_row][flip_col+1:]
backtrack(row, col + 1, operations + 1)
grid[flip_row] = grid[flip_row][:flip_col] + ('B' if grid[flip_row][flip_col] == 'W' else 'W') + grid[flip_row][flip_col+1:]
else:
backtrack(row, col + 1, operations)
backtrack(0, 0, 0)
print(min_operations)
adjust_grid()
Problem G: Dormitory Wall Installation
Given a tree representing a dormitory with students of different types, find the minimum number of thick walls needed to separate partying and sleeping students.
Input Format:
- The first line contains t (1 ≤ t ≤ 1000) - number of test cases
- Each test case starts with n (2 ≤ n ≤ 10⁵) - number of vertices
- Followed by n-1 integers representing tree edges
- Followed by a string of length n representing student types ('P', 'S', 'C')
Output Format:
- The minimum number of thick walls needed
**Solution Approach:**We can use dynamic programming on trees to solve this problem.
def install_walls():
import sys
sys.setrecursionlimit(200000)
test_cases = int(input())
for _ in range(test_cases):
n = int(input())
edges = [[] for _ in range(n+1)]
for i in range(2, n+1):
parent = int(input())
edges[i].append(parent)
edges[parent].append(i)
student_types = " " + input().strip()
# dp[0][i] = min walls if i is party node
# dp[1][i] = min walls if i is sleep node
dp = [[0, 0] for _ in range(n+1)]
INF = float('inf')
def dfs(node, parent):
if student_types[node] == 'P':
dp[node][0] = 0
dp[node][1] = INF
elif student_types[node] == 'S':
dp[node][1] = 0
dp[node][0] = INF
else:
dp[node][0] = dp[node][1] = 0
for neighbor in edges[node]:
if neighbor == parent:
continue
dfs(neighbor, node)
if student_types[node] == 'P':
dp[node][0] += min(dp[neighbor][0], dp[neighbor][1] + 1)
elif student_types[node] == 'S':
dp[node][1] += min(dp[neighbor][1], dp[neighbor][0] + 1)
else:
dp[node][0] += min(dp[neighbor][0], dp[neighbor][1] + 1)
dp[node][1] += min(dp[neighbor][1], dp[neighbor][0] + 1)
dfs(1, -1)
print(min(dp[1][0], dp[1][1]))
install_walls()