python代写: python exercise

python代写：这是一个典型的python练习 涉及了python的基本语法等知识
Problem S1: Sum Game
Time limit: 1 second
Problem Description
Annie has two favourite baseball teams: the Swifts and the Semaphores. She has followed them throughout the season, which is now over. The season lasted for N days. Both teams played exactly one game on each day.
For each day, Annie recorded the number of runs scored by the Swifts on that day. She also recorded this information for the Semaphores.
She would like you to determine the largest integer K such that K ≤ N and the Swifts and the Semaphores had scored the same total number of runs K days after the start of the season. The total number of runs scored by a team after K days is the sum of the number of runs scored by the team in all games before or on the K-th day.
For example, if the Swifts and the Semaphores have the same total number of runs at the end of the season, then you should output N. If the Swifts and the Semaphores never had the same number of runs after K games, for any value of K ≤ N , then output 0.
Input Specification
The first line of input will contain an integer N (1 ≤ N ≤ 100 000). The second line will contain N space-separated non-negative integers representing the number of runs scored by the Swifts on each day, in order. The third line will contain N space-separated non-negative integers representing the number of runs scored by the Semaphores on each day, in order. You may assume that each team scored at most 20 runs in any single game.
For 7 of the 15 points available, N ≤ 1000.
Output Specification
Output the largest integer K such that K ≤ N and the Swifts and the Semaphores have the same total number of runs after K days.
Sample Input 1
3 133 226
Output for Sample Input 1
2
Explanation for Output for Sample Input 1
After 2 days, each team had scored a total of 4 runs.
Version franc ̧aise sont apre`s la version anglaise
Sample Input 2
3 123 456
Output for Sample Input 2
0
Explanation for Output for Sample Input 2
The only time when the Swifts and the Semaphores had scored the same number of runs was the beginning of the season.
Sample Input 3
4 1234 1324
Output for Sample Input 3
4
Explanation for Output for Sample Input 2
The Swifts and Semaphores have the same number of total runs after the first game, and after the third game, and after the fourth game. We take the largest of these values (1, 3 and 4) and output 4.
Version franc ̧aise sont apre`s la version anglaise

Proble`me S1 : Somme toute
Description du proble`me
Annie a deux e ́quipes de baseball pre ́fe ́re ́es, les Swifts et les Se ́maphores. Elle les a suivies toute la saison qui vient de se terminer. La saison a dure ́ N jours. Chaque e ́quipe a joue ́ exactement une partie par jour.
Chaque jour, Annie a note ́ le nombre de points compte ́s par les Swifts ce jour-la`. Elle a fait de meˆme pour les Se ́maphores.
Vous devez de ́terminer le plus grand entier K (K ≤ N) pour lequel les Swifts et les Se ́maphores ont compte ́ le meˆme nombre total de points apre`s K jours depuis le de ́but de la saison. Le nombre total de points compte ́s par une e ́quipe apre`s K jours est la somme des nombres de points compte ́s par cette e ́quipe chaque jour jusqu’au Kie`me jour inclusivement.
Par exemple, si les Swifts et les Se ́maphores ont compte ́ le meˆme nombre total de points a` la fin de la saison, la sortie devrait eˆtre N. Si les Swifts et les Se ́maphores n’ont jamais obtenu le meˆme nombre total de points apre`s K parties, pour n’importe valeur de K (K ≤ N), la sortie devrait eˆtre 0.
Pre ́cisions par rapport aux entre ́es
La premie`re ligne d’entre ́e contiendra un entier N (1 ≤ N ≤ 100 000). La deuxie`me ligne d’entre ́e contiendra N entiers non ne ́gatifs se ́pare ́s d’une espace, indiquant le nombre de points compte ́s par les Swifts chaque jour, dans l’ordre. La troisie`me ligne d’entre ́e contiendra N entiers non ne ́gatifs se ́pare ́s d’une espace, indiquant le nombre de points compte ́s par les Se ́maphores chaque jour, dans l’ordre. Vous pouvez supposer que chaque e ́quipe a compte ́ au plus 20 points dans n’importe quelle partie.
Pour 7 des 15 points disponibles, on aura N ≤ 1000.
Pre ́cisions par rapport aux sorties
La sortie sera le plus grand entier K (K ≤ N) pour lequel les Swifts et les Se ́maphores ont le meˆme nombre total de points apre`s K jours.
Exemple d’entre ́e 1
3 133 226
Sortie pour l’exemple d’entre ́e 1
2
Explication de la sortie pour l’exemple d’entre ́e 1
Apre`s 2 jours, chaque e ́quipe a un total de 4 points.
English version appears before the French version

Exemple d’entre ́e 2
3 123 456
Sortie pour l’exemple d’entre ́e 2
0
Explication de la sortie pour l’exemple d’entre ́e 2
Le seul jour ou` les Swifts et les Se ́maphores ont le meˆme nombre total de points est au de ́but de la saison, avant la premie`re partie.
Exemple d’entre ́e 3
4 1234 1324
Sortie pour l’exemple d’entre ́e 3
4
Explication de la sortie pour l’exemple d’entre ́e 3
Les Swifts et les Se ́maphores ont le meˆme nombre total de points apre`s la 1re partie, apre`s la 3e partie et apre`s la 4e partie. On choisit le plus grand des nombres 1, 3 et 4 et la sortie est 4.
English version appears before the French version

Problem S2: High Tide, Low Tide
Time limit: 1 second
Problem Description
Joe Coder is camping near the Bay of Fundy between Nova Scotia and New Brunswick. When he arrived at the bay, he was told that the difference in height between high tide and low tide at the Bay of Fundy was the largest tidal difference in the world. Ever the skeptic, Joe decided to verify this. He chose a reference point and, after learning from the radio when the tides were highest and lowest, he went with a boat to his reference point and measured the depth of the water. Unfortunately, on the last day of his trip, a strong wind scattered his measurements.
Joe has recovered all of his measurements, but they may not be in their original order. Luckily, he remembers some things about his measurements:
• He started measuring water levels at a low tide, his second measurement was of the water level at high tide, and after that the measurements continued to alternate between low and high tides.
• All high tide measurements were higher than all low tide measurements.
• Joe noticed that as time passed, the high tides only became higher and the low tides only
became lower.
Given Joe’s measurements in no particular order, you must reconstruct the correct order in which the measurements were taken.
Input Specification
The first line contains the integer N (1 ≤ N ≤ 100). The next line contains N distinct space- separated positive integers, where each integer is at most 1 000 000.
Output Specification
Output the N integers in the unique order that Joe originally took the measurements.
Sample Input
8
10 50 40 7 3 110 90 2
Output for Sample Input
10 40 7 50 3 90 2 110
Explanation of Output for Sample Input
The low tide measurements (in order) were 10, 7, 3, and 2. The high tide measurements (in order) were 40, 50, 90, and 110.
Version franc ̧aise sont apre`s la version anglaise

Proble`me S2 : Mare ́e haute, mare ́e basse
Description du proble`me
DenisCodeurcampepre`sdelabaiedeFundyentrelaNouvelle-E ́cosseetleNouveau-Brunswick. En arrivant, on lui a dit que c’est dans la baie de Fundy qu’on trouve le plus grand marnage (la diffe ́rence entre la mare ́e haute et la mare ́e basse) au monde. Toujours sceptique, Denis de ́cide de le ve ́rifier. Il choisit d’abord un point de re ́fe ́rence. Chaque jour, apre`s avoir entendu les heures de mare ́e haute et les heures de mare ́e basse a` la radio, il se rend en bateau a` son point de re ́fe ́rence et mesure la profondeur de l’eau a` ces heures. Malheureusement, le dernier jour de ses vacances, un vent soudain e ́parpille les mesures qu’il a collecte ́es.
Or, il a pu re ́cupe ́rer les mesures, mais elles ne sont plus en ordre. Heureusement, il se souvient de ce qui suit :
• Il a commence ́ a` mesurer a` mare ́e basse, ensuite a` mare ́e haute et ainsi de suite en alternant entre mare ́e basse et mare ́e haute.
• Les mesures collecte ́es a` mare ́e haute e ́taient toutes supe ́rieures a` toutes celles collecte ́es a` mare ́e basse.
• A` mesure que le temps passait, les mare ́es hautes augmentaient en profondeur et les mare ́es basses diminuaient en profondeur.
E ́tantdonne ́lesmesuresdansunordrequelconque,vousdevezlesremettredansl’ordredanslequel elles ont e ́te ́ collecte ́es.
Pre ́cisions par rapport aux entre ́es
La premie`re ligne d’entre ́e contiendra un entier N (1 ≤ N ≤ 100). La ligne suivante contiendra N entiers strictement positifs distincts se ́pare ́s d’une espace, chaque entier e ́tant au plus 1 000 000.
Pre ́cisions par rapport aux sorties
Les N entiers devront sortir dans l’ordre unique dans lequel Denis a collecte ́ les mesures.
Exemple d’entre ́e
8
10 50 40 7 3 110 90 2
Sortie pour l’exemple d’entre ́e
10 40 7 50 3 90 2 110
Explication de la sortie pour l’exemple d’entre ́e
Les mesures de la mare ́e basse, dans l’ordre, e ́taient 10, 7, 3 et 2. Les mesures de la mare ́e haute, dans l’ordre, e ́taient 40, 50, 90 et 110.
English version appears before the French version

Problem S3: Nailed It!
Time limit: 2 seconds
Problem Description
Tudor is a contestant in the Canadian Carpentry Challenge (CCC). To win the CCC, Tudor must demonstrate his skill at nailing wood together to make the longest fence possible using boards. To accomplish this goal, he has N pieces of wood. The ith piece of wood has integer length Li.
A board is made up of exactly two pieces of wood. The length of a board made of wood with lengths Li and Lj is Li + Lj . A fence consists of boards that are the same length. The length of the fence is the number of boards used to make it, and the height of the fence is the length of each board in the fence. In the example fence below, the length of the fence is 4; the height of the fence is 50; and, the length of each piece of wood is shown:
20
40
30
15
35
30
20
10
length of fence
Tudor would like to make the longest fence possible. Please help him determine the maximum length of any fence he could make, and the number of different heights a fence of that maximum length could have.
Input Specification
The first line will contain the integer N (2 ≤ N ≤ 1 000 000).
The second line will contain N space-separated integers L1, L2, . . . , LN (1 ≤ Li ≤ 2 000).
For 5 of the 15 available marks, N ≤ 100.
For an additional 4 of the 15 available marks, N ≤ 1000. For an additional 3 of the 15 available marks, N ≤ 100 000.
Output Specification
Output two integers on a single line separated by a single space: the length of the longest fence and the number of different heights a longest fence could have.
Version franc ̧aise sont apre`s la version anglaise
length of each board
height of fence

Sample Input 1
4 1234
Output for Sample Input 1
21
Explanation for Output for Sample Input 1
Tudor first combines the pieces of wood with lengths 1 and 4 to form a board of length 5. Then he combines the pieces of wood with lengths 2 and 3 to form another board of length 5. Finally, he combines the boards to make a fence with length 2 and height 5.
Sample Input 2
5
1 10 100 1000 2000
Output for Sample Input 2
1 10
Explanation for Output for Sample Input 2
Tudor can’t make a fence longer than length 1, and there are 10 ways to make a fence with length 1 by choosing any two pieces of wood to nail together. Specifically, he may have a fence of height 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100 and 3000.
Version franc ̧aise sont apre`s la version anglaise

Proble`me S3 : Teˆte de clou !
Description du proble`me
Thierry veut se joindre a` la Confre ́rie des charpentiers inde ́pendants (CCI). Pour eˆtre admis a` la CCI, Thierry doit de ́montrer son habilete ́ a` clouer des panneaux de bois de manie`re a` former la cloˆture la plus longue possible. Pour re ́ussir, il dispose de N planches de bois. La iieme planche de bois a pour longueur Li (un entier).
Un panneau est compose ́ d’exactement deux planches. Un panneau compose ́ de planches de lon- gueursLi etLj apourlongueurLi+Lj.Unecloˆtureestcompose ́edepanneauxdemeˆmelongueur. La longueur d’une cloˆture est le nombre de panneaux qui la composent et la hauteur d’une cloˆture est la longueur de chaque panneau qui la compose. Dans l’exemple suivant, on a une cloˆture de longueur 4 et de hauteur 50. La longueur de chaque planche est indique ́e au milieu de la planche.
20
40
30
15
35
30
20
10
longueur de la cloˆture
Thierry aimerait construire la cloˆture la plus longue possible. Pour l’aider, vous devez de ́terminer la longueur maximale de cloˆture qu’il pourrait construire et le nombre de hauteurs diffe ́rentes qu’une cloˆture de longueur maximale pourrait avoir.
Pre ́cisions par rapport aux entre ́es
La premie`re ligne contiendra l’entier N (2 ≤ N ≤ 1 000 000).
La deuxie`me ligne contiendra N entiers se ́pare ́s d’une espace : L1, L2, . . . , LN (1 ≤ Li ≤ 2 000).
Pour 5 des 15 points disponibles, on aura N ≤ 100. Pour 4 autres des 15 points disponibles, on aura N ≤ 1000. Pour 3 autres des 15 points disponibles, on aura N ≤ 100 000.
Pre ́cisions par rapport aux sorties
La sortie comportera deux entiers se ́pare ́s d’une espace sur une seule ligne, soit la longueur de la plus longue cloˆture possible et le nombre de hauteurs diffe ́rentes que cette cloˆture la plus longue peut avoir.
English version appears before the French version
longueur de chaque panneau
hauteur de la cloˆture

Exemple d’entre ́e 1
4 1234
Sortie pour l’exemple d’entre ́e 1
21
Explication de la sortie pour l’exemple d’entre ́e 1
Thierry re ́unit les planches de longueurs 1 et 4 pour former un panneau de longueur 5. Il re ́unit ensuite les planches de longueurs 2 et 3 pour former un autre panneau de longueur 5. Il re ́unit les panneaux pour construire une cloˆture de longueur 2 et de hauteur 5.
Exemple d’entre ́e 2
5
1 10 100 1000 2000
Sortie pour l’exemple d’entre ́e 2
1 10
Explication de la sortie pour l’exemple d’entre ́e 2
Thierry peut seulement construire des cloˆtures de longueur 1. Il y a 10 fac ̧ons de construire une cloˆture de longueur 1, soit en clouant n’importe quelles deux planches ensemble. Il peut ainsi construire des cloˆtures de hauteur 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100 ou 3000.
English version appears before the French version

Problem S4: Minimum Cost Flow
Time limit: 3 seconds
Problem Description
The city of Watermoo has buildings numbered 1,2,…,N. The city has M pipes that connect pairs of buildings. Due to urban planning oversights, building 1 is the only sewage treatment plant in the city. Each pipe can be either active or inactive. The set of active pipes forms a valid plan if building 1 is directly or indirectly connected to each other building using active pipes. (Pipes directly connect pairs of buildings. Buildings X and Z are indirectly connected if X is directly or indirectly connected to Y , and Y is directly or indirectly connected to Z.)
The municipal government of Watermoo is currently operating a valid plan of N − 1 pipes today, but they think it is too expensive! Each pipe has a monthly maintenance fee that the city must pay when it is active, and the total cost of a valid plan is the sum of the maintenance fees of its active pipes. (Inactive pipes cost nothing.)
Additionally, researchers at the University of Watermoo have developed an experimental pipe en- hancer which you can use on one pipe of your choice. It will reduce that pipe’s cost from C down to max(0, C − D), where D is the enhancer’s strength.
The city wants you to minimize the cost of the plan, and they want you to do it quickly. Every day, the city will allow you to activate one pipe, and deactivate another pipe. How many days do you need to make the set of active pipes form a valid plan, whose cost is minimum among all valid plans and all choices of enhanced pipe?
Note that it is possible that the plan becomes invalid while you are working, but by the end it should be a valid plan.
Input Specification
The first line will contain the integers N, M, and D (1 ≤ N ≤ 100000,N −1 ≤ M ≤ 200 000, 0 ≤ D ≤ 109). Each of the next M lines contain three integers Ai, Bi, and Ci, which means that there is a pipe from building Ai to building Bi that costs Ci per month when activated (1≤Ai,Bi ≤N,1≤Ci ≤109).ThefirstN−1oftheselinesrepresentthevalidplanthecityis currently using.
It is guaranteed that there is at most one pipe connecting any two buildings and no pipe connects a building to itself.
For3ofthe15availablemarks,N ≤8,M ≤28andD=0.
For an additional 5 of the 15 available marks, N ≤ 1000 and M ≤ 5000 and D = 0. For an additional 3 of the 15 available marks, D = 0.
For an additional 2 of the 15 available marks, N ≤ 1 000 and M ≤ 5 000.
Output Specification
Version franc ̧aise sont apre`s la version anglaise

Output one integer on a single line, the minimum number of days to complete this task. If the initial valid plan is already an optimal plan, then output 0.
Sample Input 1
440 121 232 341 411
Output for Sample Input 1
1
Explanation for Output for Sample Input 1
Note that it does not matter which pipe you use the pipe enhancer on because D = 0, so it will not affect the maintenance fee of any pipe.
On the first day, you should deactivate the pipe from building 2 to 3 and activate the pipe from building 4 to 1.
Sample Input 2
562 125 235 145 455 131 151
Output for Sample Input 2
2
Explanation for Output for Sample Input 2
One solution using the minimum number of days is to first use the pipe enhancer on the pipe from building 1 to 2 to decrease its cost to 3. Then on the first day, replace the pipe from building 2 to 3 with the pipe from building 1 to 3, and on the second day replace the pipe from 1 to 4 with the pipe from building 1 to 5. Note that the cost of the optimal plan is 10.
Additionally, there are no solutions where you use the pipe enhancer on the pipe from building 1 to 3 or the pipe from building 1 to 5. Doing so would make that pipe have a maintenance fee of 0, and then any optimal plan would have cost 11 (and we have already seen that we can achieve a cost of 10).
Sample Input 3
Version franc ̧aise sont apre`s la version anglaise

440
1 2 715827882 2 3 715827882 3 4 715827882 4 1 715827884
Output for Sample Input 3
0
Explanation for Output for Sample Input 3
The initial valid plan is already an optimal plan. Be careful of integer overflow when implementing your solution.
Version franc ̧aise sont apre`s la version anglaise

Proble`me S4 : De ́bit a` cout minimal
Description du proble`me
La ville de Waterleau a des e ́difices nume ́rote ́s 1,2,…,N. La ville a M tuyaux qui relient des paires d’e ́difices. A` cause d’omissions dans la planification urbaine, l’e ́difice 1 est la seule station d’e ́puration des eaux use ́es de la ville. Chaque tuyau peut eˆtre actif ou inactif. L’ensemble des tuyaux actifs forme un plan valide si l’e ́difice 1 est relie ́ directement ou indirectement a` tous les autres e ́difices par des tuyaux actifs. (Un tuyau qui va d’un e ́difice a` un autre les relie directement. Les e ́difices X et Z sont relie ́s indirectement si X est relie ́ directement ou indirectement a` Y et Y est relie ́ directement ou indirectement a` Z.)
Le gouvernement municipal de Waterleau a pre ́sentement un plan valide de N − 1 tuyaux, mais il conside`re que ce plan est trop dispendieux ! Chaque tuyau actif a un cout mensuel de maintenance et le cout total d’un plan valide est e ́gal a` la somme des couts mensuels de maintenance de ses tuyaux actifs. (Les tuyaux inactifs ne coutent rien.)
Or, des chercheurs de l’Universite ́ de Waterleau ont de ́veloppe ́ un amplificateur de tuyau qui est pre ́sentement au stade expe ́rimental et que vous pouvez ajouter a` un seul tuyau selon votre choix. Il re ́duira le cout de maintenance C du tuyau a` max(0, C − D), D e ́tant la force de l’amplificateur.
La ville vous demande de diminuer le cout total de son plan valide et de le faire rapidement. Chaque jour, la ville vous permet de de ́sactiver un tuyau et d’en activer un autre. Combien de jours vous faudra-t-il pour obtenir un ensemble de tuyaux actifs qui forment un plan valide dont le cout total est minimal parmi tous les choix de plans valides et les choix d’un tuyau amplifie ́ ?
A` noter qu’il est possible que le plan devienne invalide pendant que vous travaillez, mais il doit eˆtre valide a` la fin.
Pre ́cisions par rapport aux entre ́es
La premie`re ligne contiendra les entiers N, M et D (1 ≤ N ≤ 100000,N − 1 ≤ M ≤ 200 000, 0 ≤ D ≤ 109). Chacune des M lignes suivantes contiendra trois entiers Ai, Bi et Ci, ce qui indique qu’il y a un tuyau qui relie l’e ́difice Ai et l’e ́difice Bi et qu’il coute Ci par mois lorsqu’il est active ́ (1 ≤ Ai, Bi ≤ N, 1 ≤ Ci ≤ 109). Parmi ces lignes, les N − 1 premie`res repre ́sentent le plan valide que la ville utilise pre ́sentement.
Il est certain qu’il y a au plus un tuyau qui relie n’importe quels deux e ́difices et qu’aucun tuyau ne relie un e ́difice a` lui-meˆme.
Pour3des15pointsdisponibles,onauraN ≤8,M ≤28etD=0.
Pour 5 autres des 15 points disponibles, on aura N ≤ 1000 et M ≤ 5000 et D = 0. Pour 3 autres des 15 points disponibles, on aura D = 0.
Pour 2 autres des 15 points disponibles, on aura N ≤ 1 000 et M ≤ 5 000.
English version appears before the French version

Pre ́cisions par rapport aux sorties
La sortie sera un entier sur une ligne, soit le nombre minimal de jours qu’il faut pour comple ́ter cette taˆche. Si le plan initial est de ́ja` optimal, la sortie sera 0.
Exemple d’entre ́e 1
440 121 232 341 411
Sortie pour l’exemple d’entre ́e 1
1
Explication de la sortie pour l’exemple d’entre ́e 1
Il n’importe pas sur quel tuyau on ajoute l’amplificateur, car D = 0. Ainsi le cout de maintenance du tuyau de change pas.
Le premier jour, il faut de ́sactiver le tuyau qui relie les e ́difices 2 et 3 et activer le tuyau qui relie les e ́difices 4 et 1.
Exemple d’entre ́e 2
562 125 235 145 455 131 151
Sortie pour l’exemple d’entre ́e 2
2
Explication de la sortie pour l’exemple d’entre ́e 2
On peut, par exemple, ajouter l’amplificateur sur le tuyau qui relie les e ́difices 1 et 2 pour re ́duire son cout a` 3. Le premier jour, on peut de ́sactiver le tuyau qui relie 2 et 3 et activer celui qui relie 1 et 3 et le deuxie`me jour, de ́sactiver le tuyau qui relie 1 et 4 et activer celui qui relie 1 et 5. Le plan optimal a alors un cout total de 10.
De plus, il n’y a aucune solution lorsqu’on emploie l’amplificateur sur le tuyau qui relie les e ́difices 1 et 3 ou sur le tuyau qui relie les e ́difices 1 et 5. Un tel emploi donnerait un cout de 0 et n’importe quel plan optimal aurait alors un cout total de 11 (et on sait qu’il est possible d’obtenir un cout total de 10).
English version appears before the French version

Exemple d’entre ́e 3
440
1 2 715827882 2 3 715827882 3 4 715827882 4 1 715827884
Sortie pour l’exemple d’entre ́e 3
0
Explication de la sortie pour l’exemple d’entre ́e 3
Le plan valide initial e ́tait de ́ja` optimal. Il faut e ́viter un de ́passement d’entier lorsqu’on exe ́cute la solution.
English version appears before the French version

Problem S5: RMT
Time limit: 5 seconds
Problem Description
The Rail Metro Transit (RMT) operates a very unusual subway system. There are N subway stations numbered from 1 to N. There are M subway lines numbered from 1 to M, with each station belonging to exactly one line and at least one station per line. The subway lines are circular. That is, if a station is numbered S, the next station after S is the station on the same line with the next largest number, unless S is the greatest number of a station in the line, in which case the next station after S is the station on the same line with the least number.
RMT is conducting a load test of their system using volunteer passengers to ride the subway trains. The test begins with one subway train in each station and for every i, there are Ai passengers in the train at station i. The volunteers do not leave their assigned trains throughout the entire duration of the load test.
Throughout the test, RMT will perform Q actions. Each of the Q actions is one of two types: either they will survey the total number of passengers in the trains at the stations numbered from l to r; or they will operate all the trains on some line x. When a train on line x is operated, it goes to the next station in that line.
You are RMT’s biggest fan, so you have generously volunteered to keep track of RMT’s actions and report the answers to their surveys.
Input Specification
The first line will contain three space-separated integers N , M , and Q (1 ≤ M ≤ N ≤ 150 000; 1 ≤ Q ≤ 150 000). The second line will contain the subway line numbers that each station from 1 to N belongs to: L1,L2,…,LN. The third line will contain N integers A1,A2,…,AN (1 ≤ Ai ≤ 7 000) representing the initial number of passengers at each station from 1 to N .
The next Q lines will each have one of the following forms: • 1 l r,whichrepresentsasurvey(1≤l≤r≤N).
• 2 x, which represents RMT operating line x (1 ≤ x ≤ M ).
For 2 of the 15 available marks, N ≤ 1000 and Q ≤ 1000.
For an additional 2 of the 15 available marks, Li ≤ Li+1 (1 ≤ i < N ). For an additional 3 of the 15 available marks, M ≤ 200. For an additional 3 of the 15 available marks, there will be no more than 200 trains on any single line. Output Specification For every survey, output the answer to the survey on a separate line. Version franc ̧aise sont apre`s la version anglaise Sample Input 1 525 12122 12345 115 21 135 22 113 Output for Sample Input 1 15 10 9 Explanation for Output for Sample Input 1 The subway system is illustrated below, with the stations numbered from 1 to 5 and the lines connecting stations marked as either being line 1 or line 2: 12 2 12345 1 2 Initially, the number of passengers at each station is {1, 2, 3, 4, 5}. The answer to the first survey is 1 + 2 + 3 + 4 + 5 = 15. After line 1 is operated, the number of passengers at each station is {3, 2, 1, 4, 5}. The answer to the second survey is 1 + 4 + 5 = 10. After line 2 is operated, the number of passengers at each station is {3, 5, 1, 2, 4}. The answer to the third survey is 3 + 5 + 1 = 9. Sample Input 2 317 111 114 101 109 111 21 111 Version franc ̧aise sont apre`s la version anglaise 21 111 21 111 Output for Sample Input 2 114 109 101 114 Explanation for Output for Sample Input 2 The subway system is illustrated below, with the stations numbered from 1 to 3 and the lines connecting stations marked as all being line 1: 11213 1 Just before the first survey, the number of passengers at each station is {114, 101, 109}. Just before the second survey, the number of passengers at each station is {109, 114, 101}. Just before the third survey, the number of passengers at each station is {101, 109, 114}. Just before the fourth survey, the number of passengers at each station is {114, 101, 109}. Version franc ̧aise sont apre`s la version anglaise Proble`me S5 : RTM Description du proble`me Le re ́seau de transport me ́tropolitain (RTM) ope`re un re ́seau de me ́tro plutoˆt inhabituel. Il y a N stations de me ́tro nume ́rote ́es de 1 a` N. Il y a M lignes de me ́tro nume ́rote ́es de 1 a` M, chaque station e ́tant rattache ́e a` exactement une ligne et chaque ligne ayant au moins une station. Les lignes de me ́tro sont circulaires et les nume ́ros des stations sur une ligne sont en ordre croissant, a` l’exception du plus grand nume ́ro de station sur la ligne qui est suivi du plus petit nume ́ro de station sur cette ligne. RTM effectue pre ́sentement des tests de charge avec l’aide de passagers volontaires qui voyagent sur les trains. Au de ́part d’un test, il y a un train a` chaque station et pour chaque valeur de i, il y a Ai passagers a` la station i. Les volontaires ne quittent pas le train qui leur a e ́te ́ assigne ́ avant la fin du test de charge. Pendant le test, RTM me`nera Q actions. Chacune des Q actions est d’un de deux types : ou bien on de ́nombrera tous les passagers sur les trains aux stations nume ́rote ́es de l a` r, ou bien on fera fonctionner chaque train d’une ligne x, c’est-a`-dire que chaque train de la ligne x avancera jusqu’a` la station suivante sur cette ligne. Comme vous eˆtes le plus grand admirateur du RTM, vous vous eˆtes porte ́ volontaire pour tenir compte des actions mene ́es et pre ́senter les re ́sultats des de ́nombrements au RTM. Pre ́cisions par rapport aux entre ́es La premie`re ligne d’entre ́e contiendra trois entiers se ́pare ́s d’une espace, soit N, M et Q (1 ≤ M ≤ N ≤ 150 000; 1 ≤ Q ≤ 150 000). La deuxie`me ligne d’entre ́e contiendra les nume ́ros des lignes de me ́tro desservies par les stations de 1 a` N : L1,L2,...,LN. La troisie`me ligne contiendra N entiers, A1, A2, . . . , AN (1 ≤ Ai ≤ 7 000), qui repre ́sentent les nombres initiaux de passagers a` chaque station de 1 a` N . Les Q lignes suivantes auront une des formes suivantes : • 1 l r, qui repre ́sentent un de ́nombrement (1 ≤ l ≤ r ≤ N). • 2 x, qui indiquent que RTM fait fonctionner tous les trains de la ligne x (1 ≤ x ≤ M ). Pour 2 des 15 points disponibles, on aura N ≤ 1 000 et Q ≤ 1 000. Pour 2 autres des 15 points disponibles, on aura Li ≤ Li+1 (1 ≤ i < N ). Pour 3 autres des 15 points disponibles, on aura M ≤ 200. Pour 3 autres des 15 points disponibles, il n’y aura pas plus de 200 trains sur n’importe quelle ligne. Pre ́cisions par rapport aux sorties Pour chaque sondage, la re ́ponse sortira sur une ligne distincte. English version appears before the French version Exemple d’entre ́e 1 525 12122 12345 115 21 135 22 113 Sortie pour l’exemple d’entre ́e 1 15 10 9 Explication de la sortie pour l’exemple d’entre ́e 1 Le syste`me de me ́tro est illustre ́ dans la figure suivante, les stations e ́tant nume ́rote ́es de 1 a` 5 et les lignes entre les stations indiquant qu’elles de ́sservent la ligne 1 ou la ligne 2 : 12 2 12345 1 2 Au de ́part, les nombres respectifs de passagers dans les stations sont {1, 2, 3, 4, 5}. La re ́ponse du premier de ́nombrement est 15 (1 + 2 + 3 + 4 + 5 = 15). Apre`s que l’on a fait marcher les trains de la ligne 1, les nombres respectifs de passagers dans les stations sont {3, 2, 1, 4, 5}. La re ́ponse du deuxie`me de ́nombrement est 10 (1 + 4 + 5 = 10). Apre`s que l’on a fait marcher les trains de la ligne 2, les nombres respectifs de passagers dans les stations sont {3, 5, 1, 2, 4}. La re ́ponse du troisie`me de ́nombrement est 9 (3 + 5 + 1 = 9). Exemple d’entre ́e 2 317 111 114 101 109 111 English version appears before the French version 21 111 21 111 21 111 Sortie pour l’exemple d’entre ́e 2 114 109 101 114 Explication de la sortie pour l’exemple d’entre ́e 2 Le syste`me de me ́tro est illustre ́ dans la figure suivante, les stations e ́tant nume ́rote ́es de 1 a` 3 et les lignes entre les stations indiquant qu’elles desservent toutes la ligne 1 : 11213 1 Avant le premier de ́nombrement, les nombres respectifs de passagers dans les stations sont {114, 101, 109}. Juste avant le deuxie`me de ́nombrement, les nombres respectifs de passagers dans les stations sont {109, 114, 101}. Juste avant le troise`me de ́nombrement, les nombres respectifs de passagers dans les stations sont {101, 109, 114}. Juste avant le quatrie`me de ́nombrement, les nombres respectifs de passagers dans les stations sont {114, 101, 109}. English version appears before the French version