In the year 1935, physicist Erwin Schrödinger received a mysterious package labeled only as "Box 42." Inside, a bizarre quantum experiment was set up by a group of eccentric scientists. The box contains a cat, a vial of poison activated by an unstable radioactive atom, and a note beside it with a single instruction: "Do not open unless you are ready to accept a single truth."

According to quantum physics, while the box is closed, it is impossible to determine the state of the cat. The entire system is in a quantum superposition: the cat is both alive and dead simultaneously. However, if someone has the courage to open the box, the superposition collapses, revealing whether the cat is indeed alive or dead.

You, as an apprentice of the old Schrödinger, have found records with the state of the box and the internal reading of the state of the cat; these are privileged information that is not observable to anyone who has not opened the box. Your mission is to determine the observable state of the cat at the described moment.

An analysis was conducted on the evolution of the possible quantum states of a system of particles, resulting in a rooted tree of $$$N$$$ states. Each state, except for the root state, is connected to its parent state by an edge that has a label of a lowercase Latin letter from a to z. This label describes the type of interference that caused the system to collapse into another state. The sequence of interferences of a state is defined as the concatenation of the labels of the edges on the path from the root to that state.

For each state, we define the minimum periodicity of its sequence as the smallest integer $$$P \geq 1$$$ such that the sequence can be obtained by repeating a smaller sequence of length $$$P$$$ multiple times (at least twice). If there is no valid integer $$$P \geq 1$$$, the sequence is considered to have a periodicity of $$$0$$$. The empty sequence from the root is considered to have a periodicity of $$$0$$$.

We are interested in studying periodic interferences within the system of particles, so your task is to determine, among all the states from the root, the highest value of minimum periodicity of their respective interference sequences.

In quantum computing, logic gates operate a bit differently. Quantum logic gates are reversible, and the number of input qubits is equal to the number of output qubits. Additionally, they can be represented by $$$2^N$$$ by $$$2^N$$$ matrices, where $$$N$$$ is the number of qubits.

A quantum circuit is a model for quantum computation where the computation is performed through a sequence of quantum logic gates and measurement devices. A sequence of logic gates can be represented by a matrix resulting from the multiplication of the matrices of the logic gates in the order of application, which is the reverse order of how they are graphically represented. For example, the circuit for adding two bits in its quantum form is:

In this circuit, we have two variations of a logic gate that we will call $$$\text{CNOT}(q_c, q_t)$$$ and $$$\text{CCNOT}(q_{c_1}, q_{c_2}, q_t)$$$. In the diagram, the qubit $$$q_t$$$ is marked with a $$$\oplus$$$. The logic gate $$$\text{CNOT}(q_c, q_t)$$$ can be seen as being equal to $$$\text{CCNOT}(q_c, q_c, q_t)$$$, that is, the application of the logic gate $$$\text{CCNOT}$$$ with $$$q_c = q_{c_1} = q_{c_2}$$$.

The logic gate $$$\text{CCNOT}(q_{c_1}, q_{c_2}, q_t)$$$ behaves by inverting the output qubit $$$q_t$$$ if both control qubits $$$q_{c_1}$$$ and $$$q_{c_2}$$$ are set. Mathematically, $$$q'_t = q_t \oplus (q_{c_1} \land q_{c_2})$$$. In its matrix form:

where $$$i$$$ is the row and $$$j$$$ is the column with $$$0 \leq i, j \lt 2^N$$$, and $$$i$$$ contains bit $$$k$$$ ($$$0 \leq k$$$) if $$$\left\lfloor \frac{x}{2^k} \right\rfloor \mod 2 = 1$$$. The operation $$$\oplus$$$ is the bitwise exclusive or operation, commonly represented as $$$\land$$$ in programming languages.

Thus, the matrix of the quantum circuit for adding two bits is given by

where the qubits $$$q_0, q_1, q_2, q_3$$$ are used with inputs $$$|A\rangle, |B\rangle, |C_{in}\rangle, |0\rangle$$$ respectively and result in $$$|A\rangle, |B\rangle, |S\rangle, |C_{out}\rangle$$$ respectively.

Your task is given the description of a circuit with logic gates $$$\text{CNOT}$$$ and $$$\text{CCNOT}$$$ in the order of application, to print the resulting matrix.

The SBC (Brazilian Computer Society) is developing various models of architectures for quantum computers, with the goal of making them accessible to everyone in the future. One of the main challenges faced by the development teams is quantum decoherence, which occurs when a qubit in superposition (simultaneously representing states $$$0$$$ and $$$1$$$) collapses to $$$0$$$ or $$$1$$$ due to environmental interference.

For each model developed, the rate of quantum decoherence will be analyzed. To do this, the qubits will be observed in an isolated state and under normal temperature and pressure conditions. The rate of quantum decoherence is the ratio between the number of qubits that collapsed under normal temperature and pressure conditions and the number of qubits that were in superposition in the isolated state.

Since there are several models, you have been asked to develop a program that calculates this rate. After all, you need extracurricular hours to graduate, right?!

There is a particle at point $$$X = 1$$$ on an infinite number line with a charge value of $$$Y$$$. When interacting with the line, it gains unusual properties: by absorbing energy, this particle releases enough kinetic energy to move $$$\gcd(X,Y)$$$ steps along the number line, where $$$\gcd(X,Y)$$$ is the greatest common divisor of $$$X$$$ and $$$Y$$$. That is, with each procedure, the particle moves from position $$$X$$$ to position $$$X + \gcd(X,Y)$$$.

Scientists need to energize the particle $$$K$$$ times in order to discover new properties about it; however, they need to predict at which point the particle will stop after these procedures so that they can reuse it in future studies.

Therefore, help determine what the final position $$$X$$$ will be after the $$$K$$$ processes.

Richard Feynman was the first to propose the use of a quantum phenomenon to perform computational routines. This was during a lecture presented at the First Conference on Physics Computing at MIT. He showed that a classical computer would take a long time to simulate a simple quantum physics experiment. Legend has it that he could memorize large sequences of numbers and mentally calculate various properties at super-fast speeds.

The MythBusters, upon learning this, decided to verify this legend directly with Feynman using their time machine. To verify, they would generate a sequence of numbers and ask how many ways we can choose exactly 4 elements from this sequence that sum to $$$X$$$. The creation of the test was assigned to you, the new intern of the MythBusters.

Your task is to write a program that, given a set of numbers and multiple query values, determines how many quadruples $$$\{i,j,k,l\}$$$ with $$$1 \leq i \lt j \lt k \lt l \leq N$$$ have a sum $$$A_i + A_j + A_k + A_l$$$ equal to the queried values.

Grover is an Indo-American computer scientist who wants to propose a quantum search algorithm that offers a quadratic speedup over classical search algorithms for unstructured databases. To achieve this, he needs to solve a problem in trees that is part of his research to develop his algorithm.

Grover has a tree with $$$N$$$ vertices and $$$N - 1$$$ undirected edges, and his goal is to assign a value $$$v_i$$$ to each vertex satisfying some constraints:

• $$$1 \leq v_i \leq 5$$$
• There are exactly $$$cnt_x$$$ vertices with the value $$$v_i = x$$$, for $$$1 \leq x \leq 5$$$
• For each vertex $$$i$$$, there is a set of values that the value of $$$v_i$$$ can take
• Additionally, in this tree, there are $$$P$$$ special paths for Grover, where a special path is represented by a pair of vertices $$$(X_i, Y_i)$$$ (the paths may intersect, and a path may appear more than once in the input) and for these paths, the values assigned to the vertices along the path (in the order from $$$X_i$$$ to $$$Y_i$$$) must form a strictly increasing sequence.

If there is a valid solution, print any one that satisfies the constraint imposed by Grover; otherwise, print $$$-1$$$.

Several quantum alternatives to traditional algorithms have been researched to solve a variety of problems. Using quantum logic gates, it is possible to gain performance in some specific types of tasks, leading to improvements, for example, in number factorization algorithms and data set searches.

Shor is working on a quantum algorithm for recognizing palindromes in binary sequences. To do this, he needs to generate a large number of examples, and he decided that he would need to know for a given positive integer $$$X$$$, what the largest integer $$$Y$$$ less than or equal to $$$X$$$ would be, whose binary representation is palindromic.

Shor has a lot of experience with quantum algorithms, but he is having difficulty creating a classical algorithm that solves this problem. Can you help?

In the laboratory of the Institute of Quantum Physics, a team of scientists is conducting a new experiment. The idea is to reconstruct the evolution of a set of entangled particles over time. The problem is that the experiment cannot be observed directly.

Therefore, the laboratory has a network of $$$N$$$ quantum sensors distributed in space. The sensors detect various properties of the particles (spin, polarization, angular momentum, etc.). However, for technical and energy reasons, the same sensor cannot be activated for a very short time (to avoid noise) and cannot remain active for too long (to avoid overheating).

The experiment will last $$$T$$$ seconds. To avoid wasting energy and to ensure that all information is collected, exactly one of the sensors must be on each second, collecting information, and no sensor should remain on after the end of the experiment.

Each sensor i at time j provides a reliability score $$$c(i, j)$$$, reflecting the quality of the measurement at that moment. The team's challenge is to select which sensors to activate throughout the experiment, ensuring that after a sensor is activated, it must remain active for at least $$$L$$$ seconds and at most $$$U$$$ seconds. Additionally, a sensor can be used multiple times during the experiment, as long as the time it remains active is respected.

The final reliability of the experiment is equal to the sum of the reliability of the chosen sensors at each second during the test. The team's goal is to select the sensors in such a way as to maximize the reliability of the reconstruction of the quantum state. Since the physicists are very busy studying other quantum matters, they have sent this problem to the teams of the Fase Zero da Maratona SBC de Programação to solve.

An experiment at the Large Hadron Collider is being set up to test phase properties of various different particles. There are $$$N$$$ filters arranged in a circle, where the $$$i$$$-th filter allows particles with a phase less than or equal to its limit $$$A_i$$$ to pass.

An experiment begins with the release of a particle at the position of the $$$i$$$-th filter, with an initial phase set to $$$A_i$$$. When passing through filter $$$i$$$, including the first one, the particle:

• Is filtered out if the phase of the particle is greater than the limit $$$A_i$$$, ending the experiment.
• Otherwise, the particle passes through the filter, increases its phase by $$$K$$$, and moves to the next filter on the right, the $$$(i \bmod N) + 1$$$-th filter.

We want to simulate the result of this experiment to compare with the results verified empirically. To achieve this, we need to create a vector $$$B_i$$$ of size $$$N$$$, where $$$B_i$$$ ($$$1 \leq B_i \leq N$$$) is the position of the filter that stopped the particle that started at position $$$i$$$.

In the core of Station Q-42, scientists have created the most advanced simulator of combinatorial quantum states: the Enhanced Path Entangler (EPE). The EPE has been programmed to study quantum walks in permutation spaces. In a quantum walk, the walker evolves in a superposition of positions, following the rules of quantum mechanics.

The input to the simulator is a permutation $$$A$$$ of size $$$N$$$. Each index $$$i$$$ of the permutation has an integer $$$A_i$$$ associated with it, representing a node in a Hilbert space. We define a quantum walk that follows the increasing evolution criterion as a subsequence of indices $$$i_1 \lt i_2 \lt \ldots \lt i_M$$$ ($$$M \gt 0$$$) such that $$$A_{i_1} \lt A_{i_2} \lt \ldots \lt A_{i_M}$$$. Each node $$$i$$$ also has a quantum energy charge stored at position $$$B_i$$$ of the vector $$$B$$$.

When simulating all possible quantum walks that follow the increasing evolution criterion, the EPE collapsed the state of each path into a sum of the quantum energies of the visited nodes. Each of these sums was recorded in a vector $$$C$$$, representing all the amplitudes of valid paths collapsed into classical energy.

To organize the data, the vector $$$C$$$ was sorted in non-increasing order, but something unexpected happened: a decoherence caused the vector $$$C$$$ to get lost in the middle of the simulation. Your goal as an analyst at Station Q-42 is to reconstruct the $$$K$$$ largest values of the vector $$$C$$$, or report if $$$C$$$ does not have that element.

The Brazilian Society of Smartphones (SBC) is developing a new model of smartphones that utilizes quantum computing, the qPhones. Unlike traditional devices that store bits, this new architecture will use qubits.

A qubit (quantum bit) is the basic unit of quantum information, just as a bit is in classical computing. However, while a classical bit can only assume one state at a time (0 or 1), a qubit can exist in superposition, assuming multiple states simultaneously as a "quantum mixture" of 0 and 1, each with a probability of being measured when observed.

Thus, if a device can store qubits, all of its combinations can be represented simultaneously due to superposition. For example, if a device stores 3 qubits, we can have the representation of $$$2^3 = 8$$$ superposed classical states, which are 000, 001, 010, 011, 100, 101, 110, and 111.

In practice, we can assume that to simulate 1 qubit we need 2 bits, to simulate 2 qubits we need 4 bits, to simulate 3 qubits we need 8 bits, and so on. Therefore, to fully simulate the memory of a classical cell phone with $$$M$$$ megabytes (MB), the engineers at SBC need to ensure that the qubits of the new device can represent at least $$$M$$$ megabytes. Consider that 1 MB is equivalent to $$$10^6$$$ bytes.

You have recently been hired by SBC to assist in the production line of the new quantum smartphones. Your task is, given the memory value of $$$M$$$ megabytes, to determine the minimum number of qubits necessary to simulate all possible states of a classical device with that amount of memory.

Charles is a great physicist, cryptographer, and computer scientist, known for his significant contributions, including foundational work on the relationship between physics and information. During his studies on quantum teleportation, Charles discovered a quantum field with $$$N$$$ positions numbered from 1 to $$$N$$$. In an experiment, Charles can place a particle initially in any position of the quantum field. At each moment in time, the particle can decide whether to teleport to a position greater than its current position or to remain still and finish its path. Thus, there are $$$2^N - 1$$$ possible paths.

Let a path be a sequence of positions visited by a particle in an experiment. Each position $$$i$$$ ($$$1 \leq i \leq N$$$) of the quantum field has an associated coefficient $$$A_i$$$. Charles defines the beauty of a path as the greatest common divisor of all the coefficients of the positions visited in the path.

Charles will perform several operations in sequence, which are:

• 1 X: Consider that all possible paths have the same probability of being taken. What is the probability that the path taken has beauty equal to $$$X$$$?
• 2 I X: Update the value of the coefficient $$$A_I$$$ to be $$$X$$$.

Can you help Charles with his experiments?