Multi-Task Challenge

Problem Statement

This problem consists of three independent tasks. The input begins with an integer indicating the task to solve (1, 2, or 3). Depending on the task, the input format and required output are different. You must write a program that handles the respective task as described below.

Task 1: Sorting Unsigned Integers

Given n unsigned 32-bit integers, sort them in increasing order.

Task 2: Rock-Paper-Scissors Tournament

There are 2n people playing a fixed-strategy "Rock-Paper-Scissors" game. They stand in two rows with n people in each row. The strategy for the person in the i^th row (i=1,2) and j^th position (0 ≤ j < n) is denoted by an integer \( a_{ij} \) where:

• 0 : Always plays Rock
• 1 : Always plays Scissors
• 2 : Always plays Paper

There are q queries. Each query consists of three integers \( x, y, l \) (with \( 0 \le x,y < n \) and \( 1 \le l \le n - \max(x,y) \)) indicating that the players from positions x to x+l-1 in the first row will play against the players from positions y to y+l-1 in the second row respectively. For each pair (first row vs. second row), the win conditions follow the standard rules:
- Rock (0) beats Scissors (1).
- Scissors (1) beats Paper (2).
- Paper (2) beats Rock (0).
Output the number of wins achieved by the first row in that query matchup.

Task 3: Valid Parenthesis String Replacement

A string is a valid parenthesis string if it consists solely of '(' and ')' characters, has an equal number of both, and every prefix has at least as many '(' as ')'. Given a string that contains characters '(', ')' and '?' (where '?' can be replaced by either '(' or ')'), determine the number of different ways to replace each '?' so that the resulting string becomes a valid parenthesis string. Two ways are considered different if there is at least one position where the replacement differs.

Input Format

The first line of the input contains an integer t (1 ≤ t ≤ 3) that indicates which task to execute.

• Task 1:
  • Line 1: 1 (task indicator)
  • Line 2: An integer n representing the number of unsigned integers.
  • Line 3: n space-separated unsigned integers.
• Task 2:
  • Line 1: 2 (task indicator)
  • Line 2: An integer n representing the number of players in each row.
  • Line 3: n space-separated integers representing the strategies of the first row.
  • Line 4: n space-separated integers representing the strategies of the second row.
  • Line 5: An integer q representing the number of queries.
  • Next q lines: Each contains three integers x y l as described above.
• Task 3:
  • Line 1: 3 (task indicator)
  • Line 2: A string composed of characters '(', ')' and '?'

Output Format

• Task 1: A single line containing the sorted numbers in ascending order separated by a space.
• Task 2: For each query, output a line with a single integer representing the number of wins for the first row.
• Task 3: A single integer representing the number of valid ways to replace '?' such that the string becomes a valid parenthesis string.

inputFormat

Input:

• The first line is an integer t (1 ≤ t ≤ 3) indicating the task number.
• If t = 1:
  • An integer n on the next line.
  • A line with n space-separated unsigned integers.
• If t = 2:
  • An integer n on the next line.
  • A line with n space-separated integers for the first row.
  • A line with n space-separated integers for the second row.
  • An integer q representing the number of queries.
  • Then q lines follow, each with three integers: x y l.
• If t = 3:
  • A single string (which can include '(', ')' and '?').

outputFormat

Output:

• Task 1: A line with the sorted numbers separated by spaces.
• Task 2: For each query, output a line containing the number of wins for the first row.
• Task 3: A single integer that represents the number of valid replacements to form a correct parenthesis string.

sample

1
5
3 0 4 2 1

0 1 2 3 4