Smart Ticket Machine Keyboard

Problem Statement

Bao recently discovered a new intelligent automatic ticket machine at C city railway station. This machine is very smart! When passengers enter their destination, the keyboard dynamically displays only available letters, hiding the others. Bao is fascinated by this intelligent design and wants to know how the keyboard will look after entering some characters.

The ticket machine screen has a 4x8 keyboard.

After each character input, only valid characters remain selectable on the keyboard (depending on remaining destination candidates), while other letters are replaced with `*`.

Given N destination names and the characters already entered by a passenger, output the current state of the keyboard.

Input Format

• First line: an integer N.
• Next N lines: each line contains a string of uppercase letters with length not exceeding 100, representing a destination.
• Last line: a string with length not exceeding 100, representing the characters entered in sequence.

Output Format

• Output 4 lines, each with a string of length 8, representing the keyboard state.

Sample Input 1

4
ZAGREB
SISAK
ZADAR
ZABOK
ZA

Sample Output 1

****B*D*
*G******
********
********

Sample Explanation 1

After entering `ZA`, the next character could be `G` (destination might be `ZAGREB`), or `D` (destination might be `ZADAR`), or `B` (destination might be `ZABOK`).

Constraints

• 1 ≤ N ≤ 50

---

Optimal Product Pricing

Problem Statement

Bao has opened a new boutique in a commercial district, specializing in handmade limited-edition bags. On the opening day, n fashion enthusiasts came to admire the unique designs. Each customer praised the bags' uniqueness, but their maximum willingness to pay varies.

As a savvy shop owner, Bao needs to set the most suitable price for these limited bags to maximize both the number of customers who can purchase them and the total revenue.

Each customer i has a maximum price a_i they are willing to pay for the bag. If the final price does not exceed a_i, the customer will buy the bag; otherwise, they will leave.

Bao needs to choose a price p from all customers' maximum prices. Your task is to find the price that maximizes total revenue, which is the number of buyers multiplied by the price.

Input Format

• First line: a single integer n
• Second line: n integers a_1, a_2, ..., a_n

Output Format

• Output a single integer representing the maximum total revenue

Sample Input 1

5
50 100 110 120 60

Sample Output 1

300

Sample Explanation 1

Setting the product price at 100 is the optimal choice.

Constraints

• For 30% of data, 1 ≤ n ≤ 10^3
• For 60% of data, 1 ≤ n ≤ 5 × 10^3
• For 100% of data, 1 ≤ n ≤ 2 × 10^5, 1 ≤ a_i ≤ 10^6

---

Binary Matrix Expansion

Problem Statement

Bao has a magical digit s that can only be 0 or 1. Bao decides to perform n rounds of expansion on this digit to form a 2^n × 2^n magic matrix. The expansion rules for each round are as follows:

• When encountering digit 0, it transforms into the matrix:

  0 0
  0 1
  

• When encountering digit 1, it transforms into the matrix:

  1 1
  1 0
  

Bao needs your help to construct this magic matrix!

Input Format

• First line: two integers n and s, representing the number of expansion rounds and the initial digit

Output Format

• Output a 2^n × 2^n matrix with no spaces between elements

Sample Input 1

2 0

Sample Output 1

0000
0101
0011
0110

Sample Explanation 1

Bao starts with digit 0 and performs 2 rounds of expansion:

1. First round expansion:
   • 0 transforms into:

     0 0
     0 1
     

   • Resulting matrix:

     00
     01
     

2. Second round expansion:
   • Each element expands separately:
     • 0 transforms into:

       0 0
       0 1
       

     • 1 transforms into:

       1 1
       1 0
       

   • Combined result is the final matrix:

     0000
     0101
     0011
     0110
     

Constraints

• s = 0 or 1
• 0 ≤ n ≤ 11

---

Skill Dependency Scheduling

Problem Statement

Bao is a master of bun-making and can learn N different techniques, numbered 1, 2, ..., N. To learn each technique i, he needs to spend T_i time practicing and must have already mastered techniques A_{i,1}, A_{i,2}, ..., A_{i,K_i}. It is guaranteed that each prerequisite technique has a smaller number than the current technique, i.e., A_{i,j} < i.

At time 0, Bao has not mastered any techniques. He can only practice one technique at a time, and once started, he cannot stop midway. Your task is to calculate the minimum time required for Bao to learn technique N.

Input Format

• First line: a positive integer N representing the number of techniques
• Next N lines: each line starts with two numbers T and K, indicating the time needed to learn this technique and the number of prerequisite techniques. Then K numbers follow, representing the prerequisite techniques for the current technique.

Output Format

• Output the minimum time required for Bao to master technique N.

Sample Input 1

3
3 0
5 1 1
7 1 1

Sample Output 1

10

Sample Explanation 1

Bao can follow this learning sequence:

• He starts learning technique 1 at time 0 and masters it at time 3.
• Then, he starts practicing technique 3 at time 3 and masters it at time 10.

Thus, the minimum time for Bao to learn technique 3 is 3 + 7 = 10. In this process, he doesn't need to master technique 2.

Sample Input 2

5
1000000000 0
1000000000 0
1000000000 0
1000000000 0
1000000000 4 1 2 3 4

Sample Output 2

5000000000

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ T_i ≤ 10^9
• 0 ≤ K_i < i
• 1 ≤ A_{i,j} < i
• ∑_{i=1}^N K_i ≤ 2 × 10^5
• A_{i,1}, A_{i,2}, ..., A_{i,K_i} are all distinct.
• All inputs are integers.

---

Bun Exhibition Palindrome Transformation

Problem Statement

Bao is preparing an important bun exhibition. The exhibition requires arranging N buns with different filling numbers. To make the exhibition more aesthetically pleasing, Bao wants these buns to be arranged in a palindrome shape - meaning the filling order looks the same from front to back and back to front.

Bao can perform the following operation:

• Choose two filling numbers (x, y) and replace all buns with filling x with filling y in the exhibition.

What is the minimum number of operations Bao needs to perform to arrange the buns in a perfect palindrome shape?

Input Format

• First line: an integer N, representing the number of bun types
• Next N numbers: representing the filling type of each bun

Output Format

• Output the minimum number of operations Bao needs.

Sample Input 1

8
1 5 3 2 5 2 3 1

Sample Output 1

2

Sample Explanation 1

Initial bun filling sequence: 1(red bean) 5(egg yolk) 3(lotus) 2(sesame) 5(egg yolk) 2(sesame) 3(lotus) 1(red bean)

1. Replace all buns with filling 3 (lotus) with filling 2 (sesame)
2. Replace all buns with filling 2 (sesame) with filling 5 (egg yolk)

Final sequence: 1 5 5 5 5 5 5 1, which is perfectly symmetrical!

Sample Input 2

7
1 2 3 4 1 2 3

Sample Output 2

1

Sample Input 3

1
200000

Sample Output 3

0

Constraints

• 1 ≤ N ≤ 2 × 10^5
• Bun filling numbers: 1 ≤ A_i ≤ 2 × 10^5