表示言語

Problem Statement

flakepym was typing the string SCSC on his computer and accidentally omitted one character. Find the missing character.

Constraints

• The string S has length 3 and consists only of the uppercase letters S and C.
• The given string can be obtained by removing exactly one character from SCSC.

Sample Input 1

CSC

Sample Output 1

S

Sample Input 2

SSC

Sample Output 2

C

表示言語

Problem Statement

Zye is writing AI inference code to run on REGULUS using Mobilint's SDK. Since Zye is a developer who is not very good at coding, the code he writes can compute only tree-shaped graphs.

Using this code, Zye wants to compute a rooted tree-shaped computation graph consisting of N tensors. The root of the tree is node 1. Node i of the tree represents a tensor of size w_i MiB.

A tensor represented by a leaf node is called an input tensor, and a tensor represented by a non-leaf node is called a result tensor. Input tensors already exist in memory in the initial state. The memory usage in the initial state is at most M MiB.

To compute the result tensor represented by node i, all tensors represented by the children of i must currently exist in memory. When computing the result tensor represented by node i, first the result tensor of size w_i MiB is allocated in memory. After the computation is finished, all tensors represented by the children of i are removed from memory.

The memory usage at a certain moment is defined as the sum of the sizes of all tensors that exist in memory at that moment.

Zye wants to choose the computation order so that the peak memory usage while computing the tensor represented by the root node is minimized. The peak memory usage is the maximum memory usage over the initial state and all moments during the computation.

The memory limit of the computer is M MiB. During the computation, the memory usage must always be at most M MiB.

Find the minimum peak memory usage needed to compute the result tensor represented by the root node.

Constraints

• 2 \leq N \leq 5\,000
• M = 8\,192
• w_i = 1
• 1 \leq p_i \leq N
• The given graph is a rooted tree with root node 1.
• All input values are integers.

Sample Input 1

8 8192
1 1 1 1 1 1 1 1
1 1 2 2 4 3 3

Sample Output 1

5

In the initial state, the tensors that exist in memory are the input tensors represented by leaf nodes 5,6,7,8. Therefore, the memory usage is 1+1+1+1=4 MiB.

For example, the result tensors can be computed in the following order.

1. Compute the result tensor represented by node 4. The maximum memory usage during this step is 4+1=5 MiB.
2. Compute the result tensor represented by node 3. The maximum memory usage during this step is 4+1=5 MiB.
3. Compute the result tensor represented by node 2. The maximum memory usage during this step is 3+1=4 MiB.
4. Compute the result tensor represented by node 1. The maximum memory usage during this step is 2+1=3 MiB.

The peak memory usage for this computation order is 5 MiB. It is impossible to make the peak memory usage at most 4 MiB, so the answer is 5.

表示言語

Problem Statement

An infinite sequence (a_n) satisfies the following property.

• For every positive integer i satisfying i>N, a_i is equal to the K-th element of a_{i-N},a_{i-N+1},\dots,a_{i-1} after these values are sorted in nondecreasing order.

Once the values of a_1,\dots,a_N are determined, the values of a_{N+1},a_{N+2},\dots are uniquely determined.

You are given the values of N, K, M and a_1,\dots,a_N. Find a_M.

Constraints

• 1 \leq K \leq N \leq 300\,000
• 1 \leq M \leq 10^{18}
• -10^9 \leq a_i \leq 10^9
• All input values are integers.

Sample Input 1

8 6 9
2 0 2 6 0 5 1 6

Sample Output 1

5

Sorting [2,0,2,6,0,5,1,6] in nondecreasing order, we have [0,0,1,2,2,5,6,6]. Since K=6, we have a_9=5.

Sample Input 2

1 1 1
1

Sample Output 2

1

表示言語

Problem Statement

utilForever visited the Sushisushi conveyor belt sushi restaurant. Its conveyor belt has a total of N positions where sushi can be placed. Initially, K_i pieces of sushi are stacked at the i-th position, and eating the j-th sushi from the top at the i-th position gives satisfaction X_{i,j}. X_{i,j} may be negative.

Starting with today's lunch, utilForever will eat for T days. At lunch each day, utilForever can eat at most one sushi, namely the top sushi among the sushi at position 1. The conveyor belt moves by 1 position every night. Sushi that was at position i+1 moves to position i, and sushi that was at position 1 moves to position N.

Find the maximum possible total satisfaction utilForever can obtain.

Constraints

• 1 \leq N,T \leq 10^6
• 0 \leq K_i \leq 10^6
• \sum_{i=1}^N K_i \leq 10^6
• -100 \leq X_{i,j} \leq 100
• All input values are integers.

Sample Input 1

4 10
5 31 4 -15 9 26
3 53 -5 -89
3 -79 -32 -38
0

Sample Output 1

88

表示言語

Problem Statement

N students, numbered from 1 to N, are seated in a circle in numerical order. Each student wears a name tag marked with either O or X. Each student can see the name tags of N-1 students, excluding their own. No three or more students sitting next to each other have name tags with the same letter, and all students are aware of this fact.

The game continues until every student has correctly guessed the letter on their own name tag. The rules of the game are as follows:

• In each round, all students who are certain of the letter on their name tag raise their hands at the same time.
• Once all students have confirmed which students raised their hands in this round, the next round begins.

During the game, no student may exchange name tags with others, remove their name tag, or change the letter on their name tag.

You are given T test cases. For each test case, determine in which round each student will raise their hand for the first time.

Constraints

• 1 \le T \le 100\,000
• 3 \le N \le 100\,000
• S is a string of length N consisting only of O and X.
  • The ith character of S is the character written on the name tag of the ith student.
• None of the three students sitting consecutively are wearing name tags with the same characters written on them.
• The sum of N over all test cases is at most 300\,000.
• All input numbers are integers.

Sample Input 1

4
4
XOXO
3
OOX
3
OXX
6
OXOOXX

Sample Output 1

1 1 1 1 
2 2 1 
1 2 2 
1 1 2 1 1 2 

In the first test case, four students are seated in a circle, each wearing a name tag labeled X, O, X, and O, respectively.

In the first round, Student 2 observes that both Student 1 and Student 3 are wearing name tags labeled X. If Student 2 were wearing a badge marked with X, then Students 2, 3, and 4 would all be wearing badges marked with X, which contradicts the rule that three students sitting consecutively cannot all have badges marked with the same character.

Therefore, Student 2 cannot be wearing a name tag marked with an X and can be certain that they are wearing a name tag marked with an O, so they raise their hand in the first round. The other students also raise their hands in the first round based on the same reasoning.

表示言語

Problem Statement

As you know, SQL stands for "Sorohue is a Query Lover".

Q queries are given.

• x: If x < 0, print the input of the |x|–th query; if x > 0, print the output of the |x|–th query. (1 \le |x| \le Q)

After all queries are given, answer all queries in order.

Constraints

• 1 \le Q \le 500\,000
• 1 \le |x_i| \le Q
• All input values are integers.

Sample Input 1

6
-2 -3 -1 1 2 6

Sample Output 1

-3 -1 -2 -3 -1 4

Query 1 outputs -3, which is the input for Query 2, so it is correct.

Query 4 outputs -3, which is the answer to Query 1, so it is correct.

Query 6 outputs 4, which is the answer to Query 6, so it is correct.

表示言語

Problem Statement

This year, FuriosaAI officially announced mass production of RNGD, its second-generation AI accelerator. RNGD is specialized for processing language models and multimodal models, and provides powerful computing performance even with low power consumption.

At SCSC, AI agents Lulu and Terra were created using RNGD chips, and SCSC had them play the SCSC game for performance testing.

The SCSC game is played with a string S consisting of uppercase letters S and C that does not contain SCSC as a substring. Lulu and Terra take turns, with Terra going first. On each turn, the current player chooses one character from the string and removes it. If, after the removal, the string contains SCSC as a substring, that player wins and the other player loses. If the current player can no longer choose any character to remove, that player loses and the other player wins.

Thanks to the powerful computing performance of the RNGD chips, Lulu and Terra have become able to always find optimal moves to win. Given the string S, determine which agent wins the game if both Lulu and Terra play optimally.

Constraints

• 1 \leq T \leq 10\,000
• 1 \leq |S| \leq 200\,000
• S consists only of uppercase letters S and C, and does not contain SCSC as a substring.
• The sum of |S| over all test cases does not exceed 200\,000.

Sample Input 1

2
SCSSCCS
SSSS

Sample Output 1

Terra
Lulu

表示言語

Problem Statement

An exam is approaching! queued_q has T hours left until the exam, and the exam covers N topics. Studying each topic basically takes A hours. queued_q wants to study as many topics as possible while keeping the total study time at most T.

Some topics are related to one another. If queued_q has previously studied topics related to the topic to be studied next, that topic becomes easier to study. The relationships between exam topics can be represented as a tree with N vertices and N-1 edges. The i-th edge of the tree means that topic u_i and topic v_i are directly related to each other. When studying topic i, if k topics adjacent to i have already been studied, the actual time required to study topic i is \max(1, A - B \times k). In other words, each additional adjacent topic already studied decreases the study time by B, but at least 1 hour must be spent.

queued_q wants to choose the topics to study and their order appropriately so as to study as many topics as possible. Find the maximum number of topics K that queued_q can study within T hours, the minimum time M required to study K topics, and an order that achieves them.

Constraints

• 1 \leq N \leq 200\,000
• 0 \leq T \leq 10^9
• 1 \leq A \leq 10^9
• 0 \leq B \leq A
• 1 \leq u_i < v_i \leq N
• The given relationships always form a tree.
• All given numbers are integers.

Sample Input 1

2 1 1 0
1 2

Sample Output 1

1 1
1 

Sample Input 2

4 0 1 1
1 2
1 3
1 4

Sample Output 2

0 0

表示言語

Problem Statement

A CUBRID HA cluster is a system consisting of N servers. The servers are numbered from 1 to N.

Jank has become the server administrator of SCSC and wants to choose some of the servers in the CUBRID HA cluster to use. Jank turns on the servers he chooses and turns off the servers he does not choose.

Jank, who rules SCSC, chooses whether each chosen server operates as a Master or as a Slave when turning it on. A Master server can process RW requests and RO requests, and a Slave server can process RO requests and SO requests. Each server can process at most one request at the same time.

If there is no Master server among the currently turned-on servers and at least one Slave server is currently turned on, the currently turned-on Slave server with the smallest number immediately becomes a Master server.

Jank, who rules SCSC, must process Q queries of the following two types in order.

• 1 i: Turn off server i. If it is already turned off, ignore this query.
• 2 a b c: a RW requests, b RO requests, and c SO requests arrive simultaneously.

The requests that arrive in a type-2 query must all be processed using only the servers that are currently turned on. Each request must be assigned to a server that can process that request, and at most one request can be assigned to each server. A request that is not assigned when the query is given cannot be processed.

When all requests have been assigned, each server processes its assigned request and discards the processed request. A server with no remaining request becomes ready to process another request again.

Find the minimum number of servers Jank, who rules SCSC, must choose initially in order to process all requests. If it is impossible to process all requests by any method, output -1 instead.

Constraints

• 1 \leq N,Q \leq 2\,000
• 1 \leq i \leq N
• 0 \leq a,b,c \leq N
• There is at least one query of the second type.
• All input values are integers.

Sample Input 1

3 4
2 2 0 0
1 1
2 0 0 1
2 1 0 1

Sample Output 1

3

表示言語

Problem Statement

ChannelTalk, an all-in-one AI messenger that facilitates real-time communication with customers, offers a workflow feature that allows anyone to easily create chatbots. Using ChannelTalk Workflow, you can combine triggers and actions like building blocks based on the customer and the situation to automate the entire process from the start to the end of a consultation. Additionally, frequently used functions can be created as modules and reused multiple times.

Ino intends to build a chatbot using ChannelTalk Workflow to handle N different types of questions. Each question is assigned a unique number from 1 to N.

Ino wants to add M modules to the workflow and number them from 0 to M-1 in the order they are added. Since Ino cannot manage too many modules, at most 2\,048 modules can be used.

When question x is entered, module i operates as follows.

• If x = i, it answers the question and ends the consultation.
• If x \neq i, it enters question x to module L_i if x \le F_i, and module G_i if x \gt F_i.

When a question is received, it is first input to module 0, and executing each module takes 1 second. That is, the time taken to process question i is equal to the total number of modules passed through, including module 0 and module i, until the consultation ends. If the same module is passed through multiple times, it is counted as many times as it was passed through.

Ino wants to ensure that the consultation ends in exactly K seconds regardless of which question from 1 to N is asked. Given the number of question types N and the ending time K, choose the number of modules M and the values of F_i, L_i, and G_i for each module so that the consultation always ends exactly at K seconds using at most 2\,048 modules. Note that M does not need to be minimized.

Constraints

• 2 \le K \le N \le 1\,000
• All input values are integers.

Sample Input 1

6 6

Sample Output 1

11
1 7 1
2 7 2
3 7 3
4 7 4
5 5 6
4 0 0
5 0 0
3 8 4
2 9 3
1 10 2
0 0 1