Welcome to the most peculiar farm in the digital world - the Binary Chicken Farm! Here, the chickens don't just lay eggs; they lay binary eggs. Each egg contains a sequence of 0s and 1s, and the farm's success depends on properly managing these binary-laying hens.
The Binary Chicken Farm has N chickens, numbered from 1 to N. Each chicken lays exactly one binary egg per day. The egg from the i-th chicken on day j is represented by a binary string (e.g. 0101).
The farm owner has noticed a strange pattern: some chickens seem to influence others. Specifically, if chicken A influences chicken B, then the egg laid by chicken B on any given day will always be the binary XOR of its own previous day's egg and chicken A's previous day's egg. Otherwise, the chicken lays the same egg as in previous day.
Given the eggs laid on day 1 and the influence relationships between chickens, your task is to predict the eggs that will be laid on day K. Note that each chicken can be influenced only by one other chicken.
The first line contains three space-separated integers:
- N: the number of chickens
- M: the number of influence relationships
- K: the day for which you need to predict the eggs
The second line contains N space-separated binary strings, each of length L, representing the eggs laid by each chicken on day 1.
The next M lines each contain two space-separated integers A and B, indicating that chicken A influences chicken B.
Output N space-separated binary strings, each of length L, representing the eggs laid by each chicken on day K.
3 2 3 101 010 111 1 2 2 3
101 010 010
Limits
- 1 $$$\le$$$ N $$$\le$$$ 1000
- 0 $$$\le$$$ M $$$\le$$$ N
- 2 $$$\le$$$ K $$$\le$$$ $$$10^4$$$
- 1 $$$\le$$$ L $$$\le$$$ 20
- 1 $$$\le$$$ A, B $$$\le$$$ N
- A $$$\ne$$$ B
There is a queue of $$$N$$$ people numbered from $$$1$$$ to $$$N$$$ waiting to submit their requests at a government office. Initially the queue is formed in ascending order of their number. Each person has a request that requires $$$R_i$$$ units of time for the office to process. The government office can process a maximum of $$$M$$$ units of time per person in one turn. If a person's request requires more time than $$$M$$$, they must go to the back of the queue and wait for their turn again. A person leaves the queue once their entire request has been processed.
Your task is to determine the order in which the people leave the queue after their requests are fully processed.
The first line on the input gives you two space separated integers: $$$N$$$, $$$M$$$.
The next line contains $$$N$$$ space separated integers $$$R_i$$$.
One line, a space separated list of integers that denote the order in which the people leave the queue.
5 6 9 10 4 7 2
3 5 1 2 4
Limits
* $$$1 \leq N \leq 10^6 $$$
* $$$1 \leq R_i \leq 10^9$$$
* $$$1 \leq M \leq 10^9$$$
You are part of a research team dedicated to deciphering symbols carved into ancient stone tablets. After years of study, you have successfully decrypted certain groups of symbols. Recently, a new set of tablets from the same era has been discovered and handed over to you. Although you haven't yet managed to translate complete sentences in the past, you're confident that these new inscriptions contain larger segments of symbols that can be translated using the groups you've already decrypted.
Your goal is to identify the longest segment of symbols on the new tablets that you can translate based on your existing knowledge.
The first line contains a string representing the text on the tablet, consisting of $$$n$$$ consecutive alphanumeric characters.
The second line contains the integer $$$m$$$.
Each on of the next $$$m$$$ lines contains a group of symbols that you have already decrypted.
The length of the longest segment of the tablet's text that can be fully translated using the decrypted symbol groups.
abafopwewwqeiqioloadaduertwpoeabafad 3 abaf iolo ad
8
Limits
- $$$1 \leq n \leq 1000$$$
- $$$1 \leq m \leq 200$$$
- Each of the $$$m$$$ groups of symbols' length is at most $$$20$$$
We wish to construct an electricity generation and transmission network in a cluster of $$$N$$$ islands. To this end, we have calculated a cost $$$p(x)$$$ to (potentially) build a generating station on each island $$$x$$$, as well as a cost $$$c(x,y)$$$ to build an energy transmission line between any two islands $$$x$$$ and $$$y$$$. An island is connected to the grid if it has a generating station built on it, or if there is a sequence of power transmission lines connecting it to an island that has a generating station. Our goal is to connect all $$$N$$$ islands to the grid, minimizing the total network construction cost.
The first line of the input contains an integer $$$N$$$ which gives the number of islands in the cluster.
The next $$$N$$$ lines of the input are sequences of $$$N$$$ numbers that form an $$$N$$$-by-$$$N$$$ array $$$A$$$, such that each diagonal entry $$$A[x,x]$$$ corresponds to the cost $$$p(x)$$$ to build generating station on island $$$x$$$ (that is, $$$'A[x,x] = p(x)'$$$), while each non-diagonal entry $$$A[x,y]$$$ corresponds to the cost $$$c(x,y)$$$ to build an energy transmission line between two islands $$$x$$$ and $$$y$$$ (that is, $$$'A[x,y] = c(x,y)'$$$).
A single integer that gives the total construction cost of the network.
4 10 8 10 14 8 15 9 13 10 9 12 12 14 13 12 11
38
Limits
- $$$1 \leq N \leq 1000$$$
- $$$1 \leq A[x,y] \leq 10000, \forall 1 \leq x,y \leq N$$$
In the Anomia neighborhood, there is a fugitive wanted by the police. To capture him, the police have stationed several officers at fixed locations throughout the neighborhood to monitor the area.
The neighborhood is represented as an $$$N \times M$$$ grid of characters, where each cell can be one of the following:
- '.': a road
- '#': a building
- 'F': the initial location of the fugitive
- 'H': the fugitive's hideout
- '$$$ \gt $$$', '$$$ \lt $$$', '$$$^{\wedge}$$$', 'v': a police officer positioned at a fixed location and looking in a specific direction (right, left, up, down respectively)
Each police officer monitors the cells in their line of sight, defined by the direction they are facing and a maximum distance $$$D$$$. A police officer's line of sight is blocked by buildings and other police officers.
The fugitive can only move right, left, up and down, not diagonally.
Your task is to determine if there is a safe path for the fugitive to move from his initial location to his hideout without being seen by any police officer.
The first line gives you three space-separated integers: the grid's number or rows $$$N$$$, the grid's number of columns $$$M$$$ and the line of sight distance $$$D$$$.
The next $$$N$$$ lines contain $$$M$$$ characters that represent the neighborhood map.
The string 'YES' if there is a safe path to the hideout, otherwise the string 'NO'.
4 7 100 ...F... >...##. .....#. ...H...
YES
Limits
- $$$1 \leq N, M \leq 1000$$$
- $$$1 \leq D \leq 1000$$$
Today, our airport had $$$N$$$ flights scheduled, initially planned with multiple runways in mind. Unfortunately, due to maintenance issues, only one runway is available, which means not all flights can depart as scheduled. Some flights will leave on time, while others will be postponed until the end of the day.
Airlines, prioritizing customer satisfaction, offer bribes (denoted as $$$b_i$$$ for each flight $$$i$$$) to the airport management to ensure their flights depart on time. Conversely, if a flight is delayed, the airline demands compensation (denoted as $$$c_i$$$ for each flight $$$i$$$).
Your task is to determine the maximum profit the airport can achieve under these conditions, taking into account the bonuses and compensations for each flight.
Additionally, note that there must be a minimum interval of $$$T$$$ time units between consecutive departures, and each plane takes off instantly.
The first line contains two space-separated integers, the number of scheduled flights $$$N$$$, and the minimum interval between flights $$$T$$$.
Each of the next $$$N$$$ lines contain three integers $$$t_i$$$, $$$b_i$$$, $$$c_i$$$, describing the scheduled departure time, the bonus for on-time departure and the compensation required for delay respectively, for the $$$i$$$-th flight. The flights are listed in order of increasing departure time $$$t_i$$$.
The output should contain a single integer $$$P$$$: the maximum profit the airport can achieve.
4 5 2 1000 -100 5 500 -500 7 300 -500 9 1000 -100
1000
Limits
- $$$0 \leq N \leq 10^6$$$
- $$$0 \leq T \leq 10^5$$$
- $$$1 \leq t_i \leq 10^8$$$
- $$$1 \leq b_i \leq 1,000$$$
- $$$-1,000 \leq c_i \leq -1$$$
Seih Sou forest consists of $$$N$$$ enchanted trees, numbered from $$$1$$$ to $$$N$$$. The trees are interconnected by magical roots, forming paths that allow magic to flow between connected trees. A subset $$$S$$$ of the trees are considered to be the source of magic in the forest. If the subset $$$S$$$ becomes disconnected from other trees, these trees stop being magical.
One day, a series of $$$Q$$$ trees start withering, one after the other. Each time a tree withers, it loses its magical properties and disconnects from the forest network, sometimes causing even more trees to lose their magical properties. The Seih Sou elves, habitats of the forest, need to know the number of trees that stop being magical after a tree in the series withers.
The first line contains three space-seperated integers $$$N$$$, $$$M$$$, $$$C$$$ representing the number of trees, the number of tree-connections and cardinality of $$$S$$$ respectively.
The next line contains $$$C$$$ space-separated integers describing the elements of $$$S$$$.
Each one of the next $$$M$$$ lines that follow contains two integers $$$U_i$$$, $$$V_i$$$ describing that trees $$$U_i$$$ and $$$V_i$$$ are interconnected by magical roots.
The next line contains an integer $$$Q$$$ describing the number of withering trees.
Each one of the next $$$Q$$$ lines that follow contains an integer $$$T_i$$$ describing the $$$i$$$-th withering tree.
The output should contain $$$Q$$$ lines with one integer $$$a_i$$$: the number of trees that stopped being magical after the withering of tree $$$T_i$$$.
6 4 1 1 1 2 2 3 2 4 5 6 2 2 5
3 0
Limits:
* $$$1 \leq C \leq N \leq 10^6$$$
* $$$ 1 \leq U_i, V_i \leq N$$$
* $$$1 \lt M \leq 10^6$$$
* $$$1 \lt Q \leq 10^6$$$