Vincent Adultman and his three friends – Anthony Matureperson, Rene Grownindividual, and Pierre Grandhomme – want to ride a rollercoaster. However, only people who are at least $$$h$$$ inches can ride the rollercoaster.
Vincent's height is $$$v$$$ inches, Anthony's height is $$$a$$$ inches, Rene's height is $$$r$$$ inches, and Pierre's height is $$$p$$$ inches.
Vincent and his friends know that at most three of them can stand on top of each other to "form" a taller "person". The height of this "person" is the height of the three children combined.
Can they choose a set of three people among themselves so that the "person" those three people form can ride the rollercoaster?
The input consists of five lines.
The first line contains a single integer $$$v$$$.
The second line contains a single integer $$$a$$$.
The third line contains a single integer $$$r$$$.
The fourth line contains a single integer $$$p$$$.
The fifth line contains a single integer $$$h$$$.
Output a single line containing a single string which is WAW if they can choose a set of three people among themselves so that the "person" formed by those three people can ride the rollercoaster, or AWW if they cannot.
$$$12 \le v, a, r, p, h \le 150$$$
Subtask 1 (50 points):
$$$v = a = r = p$$$
Subtask 2 (50 points):
No additional constraints.
20 20 20 20 61
AWW
24 55 42 69 143
WAW
In the first sample test case, Vincent's height is $$$20$$$ inches, Anthony's height is $$$20$$$ inches, Rene's height is $$$20$$$ inches, and Pierre's height is $$$20$$$ inches. Also, only people who are at least $$$61$$$ inches can ride the rollercoaster.
There is no way to choose a set of three people among themselves so that the "person" those three people form can ride the rollercoaster, so the answer is AWW.
In the second sample test case, Vincent's height is $$$24$$$ inches, Anthony's height is $$$55$$$ inches, Rene's height is $$$42$$$ inches, and Pierre's height is $$$69$$$ inches. Also, only people who are at least $$$143$$$ inches can ride the rollercoaster.
Vincent, Pierre, and Anthony can form a "person" with height $$$24 + 69 + 55 = 148$$$ inches and this "person" can ride the rollercoaster, so the answer is WAW.
Bogart was disqualified because he did not follow the rules in the coolest online competition ever. He did not intend to cheat. He just did not know that what he was doing was against the rules. Because of this, he cannot join the coolest onsite competition this year. Bogart could have avoided being disqualified by reading the rules of the coolest online competition ever, which is accessible in https://noi.ph/rules.
Bogart is sad because of his disqualification. His friends in his chat group try to console him by saying "F" to pay respects. The message "F" was mentioned $$$n$$$ consecutive times in the chat room, where $$$n$$$ is a positive integer. It was said by his various friends with various usernames.
The first line of input contains $$$n$$$, the number of Bogart's friends. Each of the next $$$n$$$ lines contains the username of one of Bogart's friends. Each username will contain only uppercase letters, lowercase letters, digits, and/or underscore ("_") characters.
Output the chatroom after all Bogart's friends said "F" to pay respects, in the order they were mentioned in the input. For each friend, output that friend's username, a colon, a space, and the letter F, in that order, each in its own line.
Each username consists of at least 1 and at most 12 characters.
Bogart's friends have distinct usernames.
Subtask 1 (20 points): $$$n = 5$$$
Subtask 2 (20 points): $$$1 \le n \le 100$$$
Subtask 3 (60 points): $$$1 \le n \le 10^5$$$
5 hunter2 kevin payton alvin BeRtO
hunter2: F kevin: F payton: F alvin: F BeRtO: F
26 bimb spacestalker boypickup packing69 bbgurl suptokao g00db0y denzel troll5 troll9 keribells keriboomboom JaRed xXx vanilla spwet pepe lotlot tohntohn ciscocisco empoy barce grammy ginny realhuman cassandra
bimb: F spacestalker: F boypickup: F packing69: F bbgurl: F suptokao: F g00db0y: F denzel: F troll5: F troll9: F keribells: F keriboomboom: F JaRed: F xXx: F vanilla: F spwet: F pepe: F lotlot: F tohntohn: F ciscocisco: F empoy: F barce: F grammy: F ginny: F realhuman: F cassandra: F
Reduplication is an interesting linguistic phenomenon through which words are formed. A prominent kind of reduplication is called partial reduplication, which occurs when a part of the the root or stem of the word is repeated in order to produce a new word.
English has several examples of partial reduplication, like super duper, easy peasy, hokey pokey, or walkie-talkie, but it is not a prominent feature of the language. In this respect it is similar to many Indo-European languages, perhaps because this rarely occurred in Proto-Indo-European nouns.
On the other hand, reduplication is a notable feature of Austronesian languages, where it is used to both create vocabulary and serve a grammatical purpose. Tagalog, being an Austronesian language, has multiple examples. For example, some verbs are conjugated through partial reduplication; laro, to play, becomes naglalaro, playing. The vocabulary also has several examples, like halakhak, to laugh, or pamaypay, a fan. Many will be familiar with neologisms such as nahulogloglog, to fall in a particularly surprising manner.
Partial reduplication can be observed even in places such as karenderyas. For example, a certain karenderya serves a dish called TJsilogsilogloglog. The word is formed through partial reduplication of the following roots:
- one serving of Truly Juicy hotdog, which is abbreviated as "TJ",
- two servings of sinangag, fried rice, which is abbreviated as "si",
- four servings of itlog, egg, which is abbreviated as "log".
The karenderya serves many other dishes too, like TJTJsilogsilogloglog, TJsiloglog, or silogsilog. The names of these dishes are constructed by putting several of the abbreviations "TJ", "si", and "log" together, in some order, to make the name. Given the name of such a dish, determine how many servings of hotdog, fried rice, and egg there are.
The first line of input contains $$$t$$$, the number of test cases.
Each test case consists of an integer $$$n$$$, followed by a space, followed by a string $$$s$$$ of length $$$n$$$.
For each test case, output one line containing three space-separated integers: the number of servings of hotdog, fried rice, and egg there are in the dish, respectively.
$$$1 \le t \le 10^5$$$
$$$1 \le n \le 10^5$$$
The sum of $$$n$$$ over all test cases in a single file is less than $$$10^5$$$.
The string $$$s$$$ is guaranteed to be the valid name of a dish.
Subtask 1 (10 points):
$$$1 \le n \le 10$$$
The dish has no servings of fried rice or egg.
Subtask 2 (20 points):
The dish has no servings of fried rice or egg.
Subtask 3 (30 points):
The dish has no servings of egg.
Subtask 4 (40 points):
No additional restrictions.
1 10 TJTJTJTJTJ
5 0 0
2 18 TJsilogsilogloglog 10 silogsilog
1 2 4 0 2 2
Lolo Generoso owns the Sibuyas Unlimited Cookie Company, a company that mass-produces cookies for sale. His son, also the chief engineer of the company, made a mistake in the designs of one of the cookie machines in one of the cookie factories, causing it to produce lots of cookies: so many cookies, in fact, that they couldn't sell it all and had to give some away for Christmas. To make up for the financial losses, Lolo Generoso decided to reduce the wages of the company's employees. Sir Richard the Knight, Sir Poorard the Merchant, Sir Coward the Brave, Sir Alucard the Mage, and other employees of the Sibuyas Unlimited Cookie Company got unhappy about this and decided to found a union, the Frustrated Union of Cookie Cutters, to demand better working conditions.
Negotiations between the Frustrated Union of Cookie Cutters and the Sibuyas Unlimited Cookie Company don't always go well. Sometimes, instead of ending peacefully, Sir Richard and friends would demonstrate their frustrations violently, vandalizing parts of Sibuyas Unlimited Cookie Company factory premises. After a series of demonstrations, the cookie machine mysteriously broke. Lolo Generoso wants to find out who to blame. None of the members of the Frustrated Union of Cookie Cutters would betray each other and name who should be responsible. Lolo Generoso, therefore, hired an investigator to figure out.
Sir Guard the Guard is the Sibuyas Unlimited Cookie Company factory security guard. He has a logbook of people going into and out of the factory premises. Whenever a violent demonstration occurs, he also notes it in his logbook. As part of the investigation, the investigator wants to ask some questions about certain events in the log. Specifically, any time there is a demonstration, she wants to know how many people there are inside the premises. In between certain events in the log, she also wants to know whether or not some employee is inside the premises.
Here's what we know about Sir Guard's logbook:
- Whenever someone enters the premises, he writes a line with a plus (+) symbol followed by either their title followed by their name (for example, "Sir Richard") or their nickname (for example "the Knight").
- Whenever someone leaves the premises, he writes a line with a minus (-) symbol followed by either their title followed by their name or their nickname.
- Whenever there is a demonstration, he writes UNION on a line in the logbook.
Sir Guard the Guard is always on-guard, so the logbook never contains any mistakes or inconsistencies.
The investigator inserts some instructions in between the lines of Sir Guard's logbook. They are of the form FIND $$$x$$$, where $$$x$$$ is the title followed by the name or the nickname of an employee whose presence needs to be determined. She then gives the edited logbook to you. The Sibuyas Unlimited Cookie Company employs lots of cookie cutters, so she doesn't want to obtain the needed info herself. Of course, you must write a program to do this for her. Ninong Generoso is watching and may give you more cookies this Christmas if you help them out.
By the way, we know the following about the employees of the Sibuyas Unlimited Cookie Company:
- All of their titles are one of the following: Sir, Madam, Miss, Honorable, Heneral, Ginoong, Ginang, Binibining, Lolo, Lola, Ninong, Ninang, Darth.
- All of their names are single words only. Names only contain English letters, and always begin with a capital letter followed by any number of small letters.
- All of their nicknames are single words only. Nicknames only contain English letters, and always begin with a capital letter followed by any number of small letters.
- No two employees have the same name.
- No two employees have the same nickname.
The input begins with a list of employees of the Sibuyas Unlimited Cookie Company. Each of these lines is of the form Title Name the Nickname, where Title, Name, and Nickname are the title, name, and nickname of an employee respectively.
This is followed by a line containing ---------- (ten dashes) denoting the end of the list.
Following this are the lines written in Sir Guard's logbook, including the investigator's edits. The lines are given in chronological order. Each of these lines is one of the following forms:
- "+ Title Name" (without the quotes) indicating that the employee with the corresponding title and name entered the premises;
- "+ the Nickname" (without the quotes) indicating that the employee with the corresponding nickname entered the premises;
- "- Title Name" (without the quotes) indicating that the employee with the corresponding title and name left the premises;
- "- the Nickname" (without the quotes) indicating that the employee with the corresponding nickname left the premises;
- "UNION" (without the quotes) indicating that the Frustrated Union of Cookie Cutters made a violent demonstration;
- "FIND Title Name" (without the quotes) indicating that the investigator wants to know if the employee with the corresponding title and name is inside the premises or not at that specific point in time;
- "FIND the Nickname" (without the quotes) indicating that the investigator wants to know if the employee with the corresponding nickname is inside the premises or not at that specific point in time.
The last line of input contains END denoting the end of the logbook. This line should not be processed.
For every entry in the logbook containing UNION, print a line containing the number of employees inside the premises at that specific point in time. For every entry in the logbook containing FIND Title Name or FIND the Nickname, print a line containing FOUND if the mentioned employee is inside the premises at that specific point in time, or the integer 404 if not found. Print the answers in chronological order.
Each name and nickname is at least one and at most $$$13$$$ characters long.
Names and nicknames only contain English letters, and always begin with a capital letter followed by any number of small letters.
Each title is one of the following: Sir, Madam, Miss, Honorable, Heneral, Ginoong, Ginang, Binibining, Lolo, Lola, Ninong, Ninang, Darth.
No two employees have the same name.
No two employees have the same nickname.
It is guaranteed that the logbook only contains titles, names, and nicknames of legitimate employees. That is, the titles, names, and nicknames appearing in the logbook all appear in the list of employees of the Sibuyas Unlimited Cookie Company.
Let $$$e$$$ denote the number of employees, and $$$n$$$ denote the number of lines in the logbook.
Subtask 1 (45 points):
$$$1 \le n \le 50$$$
$$$1 \le e \le 50$$$
Subtask 2 (22 points):
$$$1 \le n \le 8000$$$
$$$1 \le e \le 8000$$$
Subtask 3 (33 points):
$$$1 \le n \le 10^5$$$
$$$1 \le e \le 10^5$$$
Sir Richard the Knight Sir Poorard the Merchant Sir Coward the Brave Sir Alucard the Mage Sir Strongard the Weak Sir Weakard the Mighty Sir Cheapard the Extravagant Sir Goodard the Cruel Sir Forward the Backward Sir Standard the Unusual Sir Bernard the Frozen Sir Seculard the Pious Sir Niggard the Generous Sir Donard the Duck ---------- + Sir Richard + the Merchant FIND the Knight UNION - the Knight FIND Sir Richard + the Duck - Sir Poorard FIND the Duck FIND Sir Donard - Sir Donard END
FOUND 2 404 FOUND FOUND
Honorable Jejeman the Honorable Honorable Rodrix the Thirtieth Heneral Luna the General Heneral Heneroso the Specific Lolo Generoso the Brandy Ninong Generous the Lostcookie Heneral Grievous the Grieving Sir Jabba the Hutt Madam Pizza the Hut Sir Chew the Baka Darth Plagueis the Wise Darth Aegis the Band Miss Taylor the Swift Sir Freddie the Mercurial Sir Shia the Buff Sir Pew the Pie Miss Ter the Jay Binibining Pilipinas the Pageant Madam Damin the Madamdamin Madam Sibuyas the Onion Lola Ynidora the Odorous Sir Plato the Contemplator Miss Gora the Explorer Honorable Ben the Solver Darth Eric the Tester ---------- + Lolo Generoso UNION FIND the Wise FIND the Swift FIND the Onion - Lolo Generoso UNION + Lolo Generoso UNION UNION - Lolo Generoso UNION UNION UNION END
1 404 404 404 0 1 1 0 0 0
Darth Josh the Incider Darth Andrew the Android Darth Carl the Smooth Sir Martin the Martian Sir Cisco the Router Sir Robin the Hood Sir Robbin the Bank Sir Tim the Mol Madam Tonette the Lawyer Sir Guessmo the Fortuneteller Sir Kevin the Spacey Honorable Marte the President Sir Vernon the Master Binibining Sara the Bukalangloob Ginoong Jingdong the Jengdung Sir Jabba the Wookiee ---------- FIND Ginoong Jingdong END
404
Your friend did not read the rules for qualifying to the NOI.PH on-site finals round. He wants to know who gets invited and who are eligible for medals. Luckily, you read the rules written at the official NOI.PH rules page, https://noi.ph/rules, and are able to explain to your friend how it works. In fact, you decide to make a program that automates this for your friend.
There are several numbers on the rules which we will vary for this problem. They are the following:
- The initial value $$$c$$$ of Cap.
- the maximum number $$$s$$$ of finalists allowed per school. For the $$$2020$$$ edition of the contest, $$$s = 6$$$ according to III.3.1.4. Every occurrence of $$$6$$$ in the rules is replaced by $$$s$$$.
- the maximum number $$$f$$$ of finalists allowed. For the $$$2020$$$ edition of the contest, $$$f = 30$$$ according to III.3.1. Every occurrence of $$$30$$$ in the rules is replaced by $$$f$$$.
- the shortlist will be the union of the following sets of participants:
- the top $$$p$$$ participants, based on the official scoreboard. For the $$$2020$$$ edition of the contest, $$$p = 40$$$ according to the first bullet point of VII.3.1.
- the top $$$q$$$ school-qualifying participants. For the $$$2020$$$ edition of the contest, $$$q = 40$$$ according to the second bullet point of VII.3.1.
For this problem, you will be given the data of the official scoreboard, containing only eligible participants and not containing disqualified participants. In particular, you will be given the username, the first name, the last name, the school, the score, and the time penalty of a contestant in the Elimination Round. Assume that no two people with the same score have the same time penalty. The data is not necessarily given in any particular order.
We will simulate the chain of events after the elimination round but before the finals. We will detail it here, in words. You may refer to the input format for more specific details on how these events will be communicated. We will not include observers in this simulation; assume that there will be no observers.
A participant is said to be invited (to attend the on-site finals) if and only if the participant is in the shortlist. Exactly one invitation will be sent to each invited participant and contains a confirmation of whether the participant is willing and able to attend the on-site finals or not. An invited participant may either accept or decline.
Participants in the waitlist are still invited, although they are only confirming their willingness and ability to attend the on-site finals in case they get promoted to either an official finalist or a non-finalist participant.
With respect to individual participants, the following events may happen:
- a participant becomes disqualified.
- an invited participant accepts the invitation.
- an invited participant declines the invitation.
With respect to logistics, the following can happen:
- the deadline for confirmation passes. This only happens once.
- Cap changes its value.
At any time during these events, we can query the contents of the following lists, sorted by rank (as described in the rules page).
- the (ordered) list of official finalists.
- the (ordered) list of non-finalist participants.
- the (ordered) list of waitlisted participants.
Some events may be invalid. Here is the list of criteria for when an event is valid or invalid.
- Each participant can only accept once and can only decline once. If a participant accepts a second time or declines a second time, then such an event is invalid. For the purposes of this criterion, a disqualification is equivalent to a declination.
- A participant may decline even if he/she has accepted earlier.
- An event where a non-invited participant accepts or declines an invitation is considered invalid. For the purposes of this criterion, a disqualification is NOT considered a declination.
- Any student in the official scoreboard can be disqualified. In particular, students who are in the official scoreboard but not in the initial shortlist may be disqualified. Such an event is considered valid if and only if the student has not been disqualified before. When a student not in the initial shortlist is disqualified, nothing happens to the shortlist.
- Any event which contradicts the NOI.PH rules (with the updated numbers) is invalid.
- Any other event is considered valid.
The first line of input contains a single integer $$$t$$$ denoting the number of test cases.
The first line of each test case contains five space-separated integers $$$c$$$, $$$s$$$, $$$f$$$, $$$p$$$, $$$q$$$ in that order, the values they represent are written in the problem statement.
The next several lines contain data about the official scoreboard. Each of those lines will be of the following form:
USERNAME/FIRSTNAME/LASTNAME/SCHOOL/SCORE/PENALTY
USERNAME, FIRSTNAME, LASTNAME, SCHOOL, SCORE and PENALTY is the username, first name, last name, school, score and time penalty of the student being described.
If the line is not of the above form, then the line is guaranteed to be END OF SCOREBOARD. This line marks the end of the input concerning the data of the official scoreboard.
The next several lines of input are either events or queries. The events are of the following form:
- DQ $$$u$$$, which means that the participant with username $$$u$$$ has been disqualified.
- AC $$$u$$$, which means that the participant with username $$$u$$$ has accepted the invitation.
- DE $$$u$$$, which means that the participant with username $$$u$$$ has declined the invitation.
- CAP $$$c'$$$, which means that the value of Cap is updated to $$$c'$$$.
- CONFIRMATION DEADLINE, which means that the deadline for confirmation has passed. This event will happen exactly once for each test case.
- PRINT NAMETAGS, which means that the input for this test case is done, and no more events or queries follow. Clearly, this string will appear exactly once for each test case.
Comparing any two strings should be done case insensitively (i.e., Kevin and keVIN are viewed to be the same string).
The queries are of the following form:
- OF $$$i$$$, which means that your program must output the username of the $$$i$$$th participant in the current ordered list of official finalists.
- NP $$$i$$$, which means that your program must output the username of the $$$i$$$th participant in the current ordered list of non-finalist participants.
- WL $$$i$$$, which means that your program must output the username of the $$$i$$$th participant in the current ordered list of waitlisted participants.
For each event, if it is valid, process it and output a single line containing the integer $$$1$$$; if it is not valid, output a single line containing the integer $$$0$$$.
For each query, output the username of the participant who is currently in the $$$i$$$th position of the specified list. (We mention "currently" to clarify that valid events happening before the query may change the contents of the list.) If the specified list contains less than $$$i$$$ participants, print the string DOES NOT EXIST instead.
When outputting a username, it should exactly match how it is given in the input, including case.
After processing the last event (PRINT NAMETAGS), output a sorted list of all participants who are coming to the finals. Output each entry of the list, in order, using the following format:
LASTNAME, FIRSTNAME/SCHOOL/STATUS/MEDALS?
(Note that there is a space after the comma.)
Here, FIRSTNAME and LASTNAME are the first and last names of the student. SCHOOL is their school. STATUS is one of the following:
- OF if the student is an official finalist.
- NP if the student is a non-finalist participant.
MEDALS? must be YES if the attendee is eligible to receive medals. Otherwise, it must be NO.
This list, unlike the queries (which are sorted by rank), must be alphabetically sorted by last name. Ties for the last name are broken by first name. Ties for the first name are broken by username. The username is unique and therefore there should be no ties at all. Any two strings must be compared lexicographically. Comparing two strings should be done case insensitively (i.e., Kelvin and kelVIN are viewed to be the same string). The lexicographic ordering of all valid characters is: [space]_abcdefghijklmnopqrstuvwxyz0123456789, where [space] represents the space character.
We denote the number of entries in the official scoreboard by $$$n$$$, and the number of events and queries $$$e$$$.
$$$1 \le t \le 10^4$$$
$$$1 \le n \le 10^5$$$
$$$2 \le e \le 10^5$$$
The sum of the $$$n$$$s in a single test file is $$$\le 10^5$$$
The sum of the $$$e$$$s in a single test file is $$$\le 10^5$$$
$$$1 \le c', c, s, f, p, q \le 10^5$$$
$$$c', c \ge f$$$
USERNAME and $$$u$$$ are nonempty strings of at most $$$24$$$ characters that can only contain letters, underscores and numbers.
FIRSTNAME, LASTNAME, SCHOOL are nonempty strings that can only contain letters and spaces.
SCORE and PENALTY are positive integers with value at most $$$10^9$$$.
The USERNAME, FIRSTNAME, LASTNAME and SCHOOL is at most $$$100$$$ characters in total.
The USERNAMEs that appear on the official scoreboard are unique.
For each query, $$$1 \le i \le 10^5$$$
Each FIRSTNAME, LASTNAME and SCHOOL does not contain leading or trailing spaces and does not contain two consecutive spaces.
No two participants with the same score have the same time penalty.
Subtask 1 (20 points):
$$$n \le 1000$$$
$$$e \le 1000$$$
The sum of the $$$n$$$s in a single file is not over $$$9000$$$
The sum of the $$$e$$$s in a single file is not over $$$9000$$$
$$$c', c \le 100$$$
$$$s = 6$$$
$$$f = 30$$$
$$$p = q = 40$$$
Subtask 2 (38 points):
$$$n \le 1000$$$
$$$e \le 1000$$$
The sum of the $$$n$$$s in a single file is not over $$$9000$$$
The sum of the $$$e$$$s in a single file is not over $$$9000$$$
$$$c', c, s, f, p, q \le 100$$$
Subtask 3 (27 points):
Cap never decreases.
Subtask 4 (15 points):
No additional constraints.
1 30 5 12 25 29 bimb/Bimby/Aquino/Pilipinas School KNB/1000/3 spacestalker/Space/Stalker/Our Lady of Perpetual Sorrow High School Other Campus/999/1 chakalakachakalaka/Chakalaka Chakalaka/Boom/Our Lady of Perpetual Sorrow High School Main Campus/999/2 boypickup/Pickup/Boy/Jejeman Senior High/10/3 packing69/Miguel/Enriquez/Our Lady of Perpetual Sorrow High School Other Campus/999/4 bbgurl/Pabebe/Gurl/Our Lady of Perpetual Sorrow High School Main Campus/999/5 suptokao/Supokato/Dipakotliu/Our Lady of Eternal Bleeding High School/10/6 g00db0y/Good/Boy/Jejeman Senior High/10/7 denzel/Denzel/Wetta/Disc III Junior High/10/8 troll5/Zzzzyzyzzyzz/Aaaabbaab/Our Lady of Perpetual Sorrow High School Other Campus/999/51 troll9/Zzzzyzyzzyz/Aaaabbaab/Our Lady of Perpetual Sorrow High School Other Campus/999/9 keribells/Bells/Keri/Our Lady of Perpetual Sorrow High School Other Campus/999/11 keriboomboom/Boomboom/Keri/Our Lady of Perpetual Sorrow High School Other Campus/999/12 xXx_alliwant4xXxmas_xXx/Mariah/Keri/Our Lady of Perpetual Sorrow High School Main Campus/999/13 bogart/Bogart/Bogart/Our Lady of Questionable Choices High School/10/14 vanilla/Vanilla/Ice Ice Baby/Mount Mayon Elementary School/2/4 spwet/Spwet/Spwetot/Mount Mayon Elementary School/15/5 pepe/Pe/Pe/Pe/789/495 pepepe/Pe/Pepe/Pe/798/801 pe_pepe/Pe/Pe Pe/Pe/782/512 pepe_pe/Pe Pe/Pe/Pe/798/43 jason/Jason/ILoveGames/MaTURONgin Erementaly Schoor/9/550 plutarcoplutarco/Plutarco/Plutarco/Plutarco/7/818 empoy/Empoy/Brandy/Our Lady of Generous Giving High School/6/967 barce/Barce/Brandy/Our Lady of Generous Giving High School/16/59 grammy/Gramatdor/Tandy/Our Lady of Generous Giving High School/15/4 easilyamazed/Wow May Comma Before This Sentence/Wow May Comma After This Sentence/Scool Bcool/1/9 ginny/Ginebrador/Tandy/Our Lady of Generous Giving High School/3/2 realhuman/Juan/de la Cruz/Totally Human School/18/1 cassandra/Cassandra/de la Cruz/Our Lady of Perpetual Sorrow High School Other Campus/2/9 kuyakim/Kim/Atienza/Our Lady of Otaku Elementary School/9/9 chuuyachim/Nakahara/Chuuya/Our Lady of Otaku Elementary School/2/537 nittanurtter/Hina/Nitta/Our Lady of Otaku Elementary School/13/3 emma1andonly/Emma/Doqueza de Jesus Fuentabella/Barangay Adamya Elementary School/5/167 genevaconvention/Geneva/Ferrer Takahashi/Barangay Adamya Elementary School/9/773 nadinepadine/Nadine/Lustre/Barangay Adamya Elementary School/8/901 yourbestreid/James/Reid/Barangay Adamya Elementary School/19/3 jedith/Kylo/Rey/Death Star University/5/5 jingding/JD/Dantes/Ateneo de Diliman University of the Philippines Manila Campus/11/11 max_cost_min_flow/Kyle/See/University of Ford Fulkerson/55/55 fetch/Payton/Yao/South Shore High School/80/80 cgpgray01/Catriona/Gray/Our Lady School/8/677 cgpgray02/Catriona/Gray/Our Lady School/18/2 cgpgray03/Catriona/Gray/Our Lady School/4/453 cgpgray04/Catriona/Gray/Our Lady School/11/1 cgpgray05/Catriona/Gray/Our Lady School/17/3 cgpgray06/Catriona/Gray/Our Lady School/18/5 cgpgray07/Catriona/Gray/Our Lady School/20/3 cgpgray08/Catriona/Gray/Our Lady School/14/8 cgpgray09/Catriona/Gray/Our Lady School/3/923 cgpgray10/Catriona/Gray/Our Lady School/10/947 cgpgray11/Catriona/Gray/Our Lady School/316/23 cgpgray12/Catriona/Gray/Our Lady School/7/722 cgpgray13/Catriona/Gray/Our Lady School/19/2 cgpgray14/Catriona/Gray/Our Lady School/17/131 cgpgray15/Catriona/Gray/Our Lady School/19/7 cgpgray16/Catriona/Gray/Our Lady School/19/206 cgpgray17/Catriona/Gray/Our Lady School/18/6 cgpgray18/Catriona/Gray/Our Lady School/9/1 cgpgray19/Catriona/Gray/Our Lady School/6/213 cgpgray20/Catriona/Gray/Our Lady School/10/984 cgpgray21/Catriona/Gray/Our Lady School/6/7 cgpgray22/Catriona/Gray/Our Lady School/18/3 cgpgray23/Catriona/Gray/Our Lady School/14/945 cgpgray24/Catriona/Gray/Our Lady School/317/5 and_so_on/Catriona/Gray/Our Lady School/16/10 cgpgray49/Catriona/Gray/Our Lady School/13/8 cgpgray50/Catriona/Gray/Our Lady School/14/10 END OF SCOREBOARD DQ bogart AC supokato AC pepe AC spacestalker AC chakalakachakalaka OF 50 AC packing69 AC bbgurl AC keribells AC keriboomboom AC xXx_alliwant4xXxmas_xXx AC boypickup DQ boypickup DQ g00db0y DE denzel OF 1 AC sutpokao DE troll9 AC barce AC grammy AC cgpgray02 AC cgpgray11 AC cgpgray24 AC cgpgray9999 AC NittaNurtter AC pe_PEPE AC troll5 AC troll9 DE troll9 DQ realhuman NP 2 AC pepe_pe AC troll9 DE troll5 AC troll9 DE troll9 AC troll9 DE troll5 AC troll5 AC pepepe OF 3 CONFIRMATION DEADLINE OF 3 DE troll9 AC troll9 AC bimb WL 2 DE troll5 AC troll9 DE troll9 AC troll9 DE troll5 OF 3 PRINT NAMETAGS
1 0 1 1 1 DOES NOT EXIST 1 1 1 1 1 1 1 1 0 bimb 0 1 1 1 1 1 1 0 1 1 1 0 0 1 cgpgray24 1 0 1 0 0 0 0 0 1 chakalakachakalaka 1 packing69 0 0 0 DOES NOT EXIST 0 0 0 0 0 packing69 1 Boom, Chakalaka Chakalaka/Our Lady of Perpetual Sorrow High School Main Campus/OF/YES Brandy, Barce/Our Lady of Generous Giving High School/NP/NO Enriquez, Miguel/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES Gray, Catriona/Our Lady School/NP/NO Gray, Catriona/Our Lady School/NP/NO Gray, Catriona/Our Lady School/OF/YES Gurl, Pabebe/Our Lady of Perpetual Sorrow High School Main Campus/OF/YES Keri, Bells/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES Keri, Boomboom/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES Keri, Mariah/Our Lady of Perpetual Sorrow High School Main Campus/OF/YES Nitta, Hina/Our Lady of Otaku Elementary School/NP/NO Pe, Pe/Pe/OF/YES Pe, Pe Pe/Pe/OF/YES Pe Pe, Pe/Pe/OF/YES Pepe, Pe/Pe/OF/YES Stalker, Space/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES Tandy, Gramatdor/Our Lady of Generous Giving High School/NP/NO
In the heart of the city, there is an infinite set of ulams. The ulams are indexed by positive integers. For any positive integer $$$a$$$, ulam $$$a$$$ can feed $$$a$$$ persons. The ulams are positioned in an infinite two dimensional grid like so:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 24 25 ...
One may wonder why they are positioned like this. It is because according to a popular Filipino song: kung ulam sa puso ay tunay ngang gan'yan.
This problem will be about subrectangles of this ulam spiral. Suppose Ulam $$$69420$$$ is on cell $$$(0, 0)$$$. A cell which is $$$a$$$ cells up and $$$b$$$ cells right of Ulam $$$69420$$$ is called cell $$$(a, b)$$$.
The subrectangle $$$R_{w,x,y,z}$$$ is the set of cells whose coordinates $$$(a, b)$$$ satisfy $$$w \leq a \leq x$$$ and $$$y \leq b \leq z$$$. One could notice that the four corners of the subrectangle $$$R_{w,x,y,z}$$$ are $$$(w, y)$$$, $$$(w, z)$$$, $$$(x, y)$$$, and $$$(x, z)$$$. The size of a subrectangle is defined to be the number of cells contained in it. We say that subrectangle $$$R_{w,x,y,z}$$$ contains ulam $$$i$$$ if ulam $$$i$$$ is on a cell contained in $$$R_{w,x,y,z}$$$.
Given two positive integers $$$i$$$ and $$$j$$$, your task is to figure out the smallest subrectangle $$$R$$$ containing ulams $$$i$$$ and $$$j$$$, and find how many people the ulams contained in $$$R$$$ can feed.
The answer may be very large. Output the answer modulo $$$10^9 + 7$$$.
The first line of input contains $$$t$$$, the number of test cases.
Each test case consists of a single line containing two space-separated integers $$$i$$$ and $$$j$$$.
For each test case, output a single line containing a single integer denoting the answer for that test case.
$$$1 \le t \le 20000$$$
$$$1 \le i, j \le 10^{18}$$$
Subtask 1 (25 points):
$$$i, j \le 50$$$
Subtask 2 (20 points):
$$$i, j \le 10^6$$$
Subtask 3 (18 points):
$$$i, j \le 10^9$$$
Subtask 4 (11 points):
$$$i, j \le 10^{12}$$$
Subtask 5 (11 points):
$$$t \le 4000$$$
$$$|i - j| \le 16$$$
Subtask 6 (9 points):
$$$t \le 4000$$$
$$$|i - j| \le 5000$$$
Subtask 7 (6 points):
No additional constraints.
3 2 12 9 7 7 9
28 24 24
Congratulations!
Today is your day
You're off to a galaxy far, far away
You have fuel in your tank
You have goo with your crew
Now it's time to prepare for your mission anew
There are planets and giants and comets to see
But alas you are limited in Delta V
It is this that you use to move between stars
And planets and orbits and even to Mars
There are $$$n$$$ little planets to visit and see
And $$$m$$$ routes between them you can follow with glee
For a route between two planets we call $$$a$$$ and $$$b$$$
There is cost $$$c_{a,b}$$$ given in Delta V
Your ship has a tank with a limit called $$$V$$$
How sad in this world that nothing is free
And one more thing that makes it much harder to do
Is the route between things are just one way for you
The rocket ship works for just one way you see
Just blame the developers of KSP
If you go to a planet there is no way back
Not a hole or a mole or even a crack
There's no cycles or circuits or loops to be had
In this galaxy that is a little bit sad
Each planet you visit will have science $$$s_i$$$
The total you get, you must make it high
As high as you can, as high as the sky
As high as it goes, as high as a TIE
On Kerbin you start which is planet zero
And onward you go our almighty hero
Think back on your friends, on Alvin and Berto
And chocolates shared and other dessert-o
"This is your last chance," I say with a sigh
Oh poor Jebediah your fate is to die
—
As the captain, pilot, and only crew member of the next mission of the Kerbal Space Program, you must maximize the total science collected by your ship. As your ship passes by a planet $$$i$$$, your ship collects $$$s_i$$$ science points.
Your ship has a fuel capacity $$$V$$$ given in Delta V. It costs $$$c_{a,b}$$$ Delta V to move from planet $$$a$$$ to planet $$$b$$$. In addition, the Kerbal solar system has a peculiar property where it is guaranteed that there is no way to return to any planet $$$a$$$ once you've left that planet.
You start on planet zero, also known as Kerbin.
The first line of input contains $$$t$$$, the number of test cases.
The first line of input contains three space-separated integers $$$n$$$, $$$m$$$ and $$$V$$$. The planets are numbered $$$0$$$ to $$$n-1$$$.
The second line contains $$$n$$$ space-separated integers $$$s_0, s_1, \ldots, s_{n-1}$$$.
The next $$$m$$$ lines describe the routes. Each line contains three space-separated integers $$$a$$$, $$$b$$$ and $$$c_{a,b}$$$ indicating that there is a route that lets you move from planet $$$a$$$ to planet $$$b$$$ with a cost of $$$c_{a,b}$$$ Delta V.
For each test case, output a single line containing a single integer denoting the maximum total science your ship can collect.
$$$1 \le t \le 1000$$$
$$$1 \le n \le 6000$$$
$$$0 \le m \le 12000$$$
$$$0 \le V \le 6000$$$
The sum of the $$$n$$$s in a single file is $$$\le 6000$$$.
The sum of the $$$m$$$s in a single file is $$$\le 12000$$$.
$$$0 \le a, b \lt n$$$
$$$a \not= b$$$
For every pair of planets $$$(a, b)$$$, there is at most one route from $$$a$$$ to $$$b$$$.
For every planet, there is a sequence of routes from planet $$$0$$$ to that planet.
There is no way to return to any planet $$$a$$$ once you've left that planet.
$$$0 \le c_{a,b} \le 10^9$$$
$$$0 \le s_i \le 10^9$$$
Subtask 1 (20 points):
$$$n \le 8$$$
The sum of the $$$n$$$s in a single file is $$$\le 600$$$.
Subtask 2 (20 points):
$$$n \le 20$$$
The sum of the $$$n$$$s in a single file is $$$\le 600$$$.
Subtask 3 (30 points):
$$$n \le 120$$$
The sum of the $$$n$$$s in a single file is $$$\le 600$$$.
Subtask 4 (15 points):
$$$c_{a,b} = 1$$$
$$$s_i = 1$$$
Subtask 5 (15 points):
No additional constraints.
1 6 8 1200 4200 9000 5000 2000 4800 5000 0 1 350 0 2 300 1 3 400 2 3 300 2 5 9001 3 4 500 3 5 650 4 5 200
16000
Miguel used to pack sopas, and pack pasta. He realized that he wasn't satisfied with his packing job. So he looked deep inside himself, and remembered how his mother used to pack sheets. This was inspiration for him to become a CloudSound wrapper.
CloudSound is a rapidly growing groceries startup. Their idea is to take substandard vegetables that supermarkets wouldn't sell, and deliver them directly to consumers at marked down prices. Miguel works in the root crop packaging division. In particular, his job involves wrapping sick beets in sheets.
Abra also works in CloudSound, and his job involves bringing stacks of sheets to other CloudSound wrappers to use for packaging. To help save the environment, CloudSound uses recycled documents from businesses, which were thrown away due to misprints.
Today, Abra brought Miguel a stack of $$$n$$$ sheets, which originally came from $$$2n$$$ pages of what was supposed to be a religious document. Because of a misprint, the first sheet has page $$$1$$$ printed on the front and page $$$2$$$ printed at the back. The second sheet has page $$$2$$$ printed on the front and page $$$3$$$ printed at the back. And in general, the $$$i$$$th sheet has page $$$i$$$ printed on the front and $$$i+1$$$ printed on the back. As Miguel was cleaning up for the day, however, he bumped into Abra and dropped the stack of sheets. In other words, Miguel messed up while he packed up.
Abra put the $$$n$$$ sheets in a stack which is now disorganized. But then Miguel noticed something divine. Consider two sheets $$$s$$$ and $$$t$$$ such that $$$s$$$ is closer to the top of the disorganized stack than $$$t$$$. If both page numbers of $$$s$$$ are larger than both page numbers of $$$t$$$, Miguel considers this a divine pair of holy packing sheets.
Miguel counts $$$k$$$ different pairs of holy packing sheets in Abra's stack. Now Abra asks: How many ways are there to arrange the $$$n$$$ sheets such that there are exactly $$$k$$$ different pairs of holy packing sheets? Help our two CloudSound wrappers collaborate by answering this question. Note that we ignore the orientation of the sheets in the stack, so there are exactly $$$n!$$$ arrangements in total. In other words, we don't give a sheet about the orientation.
The first line of input contains $$$t$$$, the number of test cases.
Each test case consists of a single line containing two space-separated integers $$$n$$$ and $$$k$$$, the number of sheets and the number of pairs of holy packing sheets.
For each test case, print a single line containing the number of ways to arrange the $$$n$$$ sheets such that there are $$$k$$$ pairs of holy packing sheets. Since the answer can be very large, print the answer modulo $$$987654321$$$.
$$$1 \le t \le 10^5$$$
$$$0 \le n, k \le 750$$$
Subtask 1 (15 points): $$$n \le 5$$$
Subtask 2 (20 points): $$$n \le 8$$$
Subtask 3 (15 points): $$$n \le 16$$$
Subtask 4 (24 points): $$$n \le 24$$$
Subtask 5 (11 points): $$$n \le 50$$$
Subtask 6 (7 points): $$$n \le 100$$$
Subtask 7 (8 points): No additional constraints.
1 4 2
7
Recall that due to the misprint, the 1st sheet has pages 1 and 2, the 2nd sheet has pages 2 and 3, the 3rd sheet has pages 3 and 4, while the 4th sheet has pages 4 and 5.
One possible way to arrange them such that there are exactly 2 different divine pairs of holy packing sheets is in the order $$$3, 2, 4, 1$$$, where $$$3$$$ is on top of the stack and $$$1$$$ is at the bottom. Note that $$$3$$$ and $$$1$$$ form a divine pair of holy packing sheets because both pages $$$3$$$ and $$$4$$$ are greater than pages $$$1$$$ and $$$2$$$. Similarly, $$$4$$$ and $$$1$$$ form the other divine pair of holy packing sheets because pages $$$4$$$ and $$$5$$$ are both greater than pages $$$1$$$ and $$$2$$$.
Note also that in this arrangement, $$$3$$$ and $$$2$$$ do not form a divine pair of holy packing sheets because the page 3 on the 3rd sheet is not greater than the page 3 on the 2nd sheet. Also, $$$2$$$ and $$$4$$$ do not form a divine pair of holy packing sheets because $$$2$$$ is the one that is closer to the top of the stack than $$$4$$$ is.
Using this same notation, the 7 total arrangements are,
- 2 3 4 1
- 2 4 3 1
- 3 2 4 1
- 3 1 4 2
- 4 1 2 3
- 4 2 1 3
- 4 1 3 2
The city hall of Lucban made lots of kiping, or rice wafers, as part of their yearly Pahiyas Festival. The festival is for expressing gratitude for a bountiful harvest, much like the similar holiday of Thankskiping.
Last year, Isidro was in charge of distributing kiping. But because there was so much to give away, kiping track of the inventory took a long time. This year, in order to reduce waiting time, Isidro decided to have several lines for distribution.
There are $$$n$$$ people who want kiping, and the $$$i$$$th person wants $$$a_i$$$ wafers of kiping. Helping Isidro are $$$k$$$ people handling distribution, or in other words, shopkiping. Each of the $$$k$$$ shopkeepers can give kiping at a rate of one wafer per second.
Isidro wants to arrange the $$$n$$$ people into $$$k$$$ lines, one for each shopkeeper. When a person is at the front of the line, they take $$$a_i$$$ kiping, which will take $$$a_i$$$ seconds. After the shopkeeper is done kiping away their kiping, the next person in line receives their kiping.
A person's waiting time is how long they have to wait, in seconds, before they start receiving kiping. In other words, it is the sum of the $$$a_i$$$ of everyone lined up in front of them. Isidro wants to arrange people into lines so that everyone's total waiting time as small as possible. And for bookkiping purposes, he also wants to know how many ways there are to arrange the people such that the total waiting time is as small as possible.
Help Isidro compute these two numbers. Since both answers can be very large, output both answers modulo $$$10^9 + 7$$$.
Two arrangements are distinct if the sequence of people lined up in some cashier in the first arrangement is different from the sequence of people lined up in the corresponding cashier in the second arrangement.
The first line of input contains $$$t$$$, the number of test cases.
The first line of each test case contains two space-separated integers $$$n$$$ and $$$k$$$. The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$.
For each test case, print a single line containing two space-separated integers denoting the answer. The first integer should be the minimum sum of everyone's waiting times, and the second integer should be the number of distinct ways to arrange people to achieve this. Since both answers can be very large, output both answers modulo $$$10^9 + 7$$$.
$$$1 \le t \le 100$$$
$$$1 \le n \le 10^5$$$
$$$1 \le k \le 10^5$$$
$$$1 \le a_i \le 10^9$$$
The sum of $$$n$$$s in a single test file is at most $$$10^5$$$.
Subtask 1 (7 points):
$$$k \ge n$$$
Subtask 2 (7 points):
$$$1 \le n \le 6$$$
$$$1 \le k \le 3$$$
Subtask 3 (19 points):
$$$k = 1$$$
Subtask 4 (23 points):
All the $$$a_i$$$ are distinct.
$$$1 \le n \le 10$$$
$$$1 \le k \le 3$$$
Subtask 5 (27 points):
All the $$$a_i$$$ are distinct.
Subtask 6 (17 points):
No additional restrictions.
1 1 1 1
0 1
3 3 2 2 5 8 3 3 2 5 8 3 4 2 5 8
2 4 0 6 0 24
In the first test case, it can be shown that the minimum sum of everyone's waiting times is $$$2$$$. There are $$$4$$$ different ways to achieve this:
In the first way in the picture above, person 1 waits $$$0$$$ seconds, person 2 waits $$$2$$$ seconds, and person 3 waits $$$0$$$ seconds, making a total of $$$2$$$ seconds.
In the second test case, it can be shown that the minimum sum of everyone's waiting times is $$$0$$$, and there are $$$6$$$ different ways to achieve this:
Similar reasoning can be applied for the third test case.
Rohatma Gandhi is the king of an archipelago. This archipelago consists of islands, all of which are under his reign. After building bridges between the islands and then destroying them, he became bored playing with his islands, and started wanting more. Through several nuclear threats, he claimed the Spratly Islands.
There are $$$n$$$ islands numbered $$$1, 2, \ldots, n$$$. Between them are $$$b$$$ bridges connecting pairs of islands, numbered $$$1, 2, \ldots, b$$$. The bridges are two-way bridges that can be crossed in either direction. Due to the inefficiency of the previous government who controlled the islands, some of these bridges may even connect the same pair of islands, and some bridges might even connect the same island to itself!
The poor infrastructure further increased Gandhi's aggression, and once again, he wanted to destroy several bridges by nuking them. The project manager originally in charge had several suggestions, however. She proposes that Gandhi can destroy as many bridges as he wants, but after destroying the bridges, it should be possible to travel from one island to any other island by crossing a series of bridges. Let's call any way Gandhi can destroy the maximum number of bridges while following the project manager's condition a max destruction. Note that every max destruction destroys the same number of bridges.
Another consideration is that each of the $$$n$$$ bridges has a certain amount of culture. The $$$i$$$th bridge has a culture value of $$$c_i$$$. After Gandhi destroys bridges, the sum of the culture values of the remaining bridges is called the total culture. The project manager computes $$$m$$$, which is the maximum possible total culture over all possible max destructions.
However, the project manager knows that some of Gandhi's citizens might protest (in a non-violent way). She is considering $$$q$$$ possibilities. In each possibility, the protest would ask for a certain set $$$S$$$ of the bridges to be kept, rather than be destroyed.
The project manager is now very stressed out, because she has to satisfy so many requirements. So she decides that she will instead do her best to partially satisfy protest, rather than follow it completely. In particular, for each of the $$$q$$$ possibilities, she wants to know the answer to the following: At most how many bridges in $$$S$$$ can be kept, if Gandhi destroys the maximum number of bridges, while the project manager's condition of travelling between islands is kept, while the total culture is still $$$m$$$?
The first line of input contains $$$t$$$, the number of test cases.
The first line of each test case contains two space-separated integers $$$n$$$ and $$$b$$$, the number of islands and the number of bridges.
Each of the next $$$b$$$ lines contains three space-separated integers $$$x_i$$$, $$$y_i$$$ and $$$c_i$$$, such that the $$$i$$$th bridge connects the isalnds $$$x_i$$$ and $$$y_i$$$ and has cultural value $$$c_i$$$.
The next line of the test case contains $$$q$$$, the number of protest possibilities.
The next $$$q$$$ lines contain each of the protest possibilities. In particular, the $$$i$$$th line contains $$$|S_i| + 1$$$ space-separated integers, the first of which is $$$|S_i|$$$, and the rest are the bridges in set $$$S_i$$$. ($$$|S_i|$$$ is defined as the number of bridges in $$$S_i$$$.)
For each of the $$$q$$$ possible protests, print a single line containing an integer denoting the answer.
$$$1 \le t \le 616$$$
$$$1 \le n \le 66666$$$
$$$1 \le b \le 133332$$$
The sum of the $$$n$$$s is $$$\le 66666$$$.
The sum of the $$$b$$$s is $$$\le 133332$$$.
$$$q \ge 1$$$.
$$$0 \le c_i \le 133332$$$
$$$1 \le x_i, y_i \le n$$$
$$$|S_i| \ge 1$$$.
The sum of the $$$|S_i|$$$s in a single test case is $$$\le b$$$.
The elements of $$$S_i$$$ are distinct.
$$$1 \le j \le b$$$ for every $$$j$$$ in $$$S_i$$$.
It is possible to go from any island to any other island using the bridges.
Subtask 1 (30 points):
The sum of the $$$n$$$s is $$$\le 1000$$$.
The sum of the $$$b$$$s is $$$\le 2000$$$.
Subtask 2 (4 points):
The sum of the $$$n$$$s is $$$\le 4000$$$.
The sum of the $$$b$$$s is $$$\le 8000$$$.
Subtask 3 (6 points):
The $$$c_i$$$s are distinct.
$$$|S_i| = 1$$$
Subtask 4 (6 points):
The $$$c_i$$$s are distinct.
Subtask 5 (26 points):
$$$|S_i| = 1$$$
Subtask 6 (28 points):
No additional constraints.
1 4 4 1 3 40 3 4 20 1 2 30 2 4 10 2 2 2 4 2 2 3
1 2
Sasha, the suspiciously sassy Swiss, sells seashells by the seashores of Sorsogon. But being a businessperson by the beachfront becomes boring. So, Sasha sets up a scheme so that she has something to do to pass the time.
Sasha draws a giant $$$j \times g$$$ grid in the sand. She then makes $$$p$$$ pairs of paper shoes. Each pair possesses a particular pattern and no two pairs possess the same pattern. The goal is then to put the $$$2p$$$ paper shoes in such a way each of them is either exactly $$$c$$$ cells to the left, exactly $$$c$$$ cells to the right, exactly $$$c$$$ cells to the top or exactly $$$c$$$ cells to the bottom of its pair. A clarification: each cell must contain at most one shoe. As the perusing programmer of this problem, we petition you to pronounce if it is possible to achieve this ambition.
Fun fact: Sasha, the suspiciously sassy Swiss selling seashells by the seashores of Sorsogon, decided that the distance of the $$$p$$$ pairs of paper shoes should be $$$c$$$ cells as she was selling seashells.
The first line of input contains $$$t$$$, the number of test cases.
Each test case consists of a single line containing four space-separated integers $$$j, g, c, p$$$.
For each test case, output a single line containing a single string which is one of the following:
- YAY if it is possible to put the $$$2p$$$ paper shoes;
- NAY otherwise.
$$$1 \le t \le 10^5$$$
$$$1 \le j, g, c, p \le 10^{18}$$$
Subtask 1 (17 points):
$$$t \le 500$$$
$$$j, g \le 5$$$
$$$p \le 10^6$$$
Subtask 2 (7 points):
$$$t \le 10^4$$$
$$$j, g \le 5$$$
$$$p \le 10^6$$$
Subtask 3 (22 points):
$$$j, g \le 10$$$
$$$p \le 10^6$$$
Subtask 4 (21 points):
$$$t \le 200$$$
$$$j, g \le 500$$$
$$$p \le 10^6$$$
Subtask 5 (17 points):
$$$j, g \le 10^9$$$
Subtask 6 (16 points):
No additional constraints.
2 1 2 1 1 3 3 2 3
YAY YAY
Jason Vincent Ben Eric is the cook for his school's arnis team! He has a row of $$$n$$$ boxes, one for each member of the team, and he's filling the boxes with balls of pastillas. Inspired by a different game involving desserts in boxes, he decides to play a game to put desserts into the boxes, to make his job a little more fun.
Initially, the $$$i$$$th box contains $$$A_i$$$ balls. Each of the boxes can be either open or closed. Jason can do three different actions to the boxes of pastillas, which are named after three of his favorite sweet dishes.
The first is turon. Turn off what is on, and TUR-ON what is off! When Jason does a turon move, he selects two integers $$$L$$$ and $$$R$$$. For all boxes between the $$$L$$$th and the $$$R$$$th boxes, inclusive, he closes the boxes that are open, and he opens the boxes that are closed.
The next is puto. If a box is open, PUT-O more desserts! When Jason does a puto move, he selects two integers $$$L$$$ and $$$R$$$, and an integer $$$v$$$. For all open boxes between the $$$L$$$th and the $$$R$$$th boxes, inclusive, he adds $$$v$$$ balls.
The last is taho. TA-HOW many desserts are there? When Jason does a taho move, he selects two integers $$$L$$$ and $$$R$$$. For all boxes between the $$$L$$$th and the $$$R$$$th boxes, inclusive, he counts the number of balls, and then adds them.
You are given the $$$m$$$ moves that Jason does. Help Jason check his work by computing the answer to all of his taho moves.
The first line contains two space-separated integers $$$n$$$ and $$$m$$$.
The next line contains $$$n$$$ space-separated integers such that the $$$i$$$th integer is $$$A_i$$$, the initial number of balls in the $$$i$$$th box.
The line after that contains $$$n$$$ space-separated integers, with each equal to 0 or 1. If the $$$i$$$th integer is 0, then the $$$i$$$th box is initially closed, and if the $$$i$$$th number is 1, then $$$i$$$ is initially open.
Following this are $$$m$$$ lines, each representing one of Jason's moves. Each line will be of one of three forms,
- 1 L R represents a turon move with integers $$$L$$$ and $$$R$$$. The number $$$1$$$ is chosen because it's tur-ONE.
- 2 L R v represents a puto move with integers $$$L$$$, $$$R$$$, and $$$v$$$. The number $$$2$$$ is chosen because it's pu-TWO.
- 3 L R represents a taho move with integers $$$L$$$ and $$$R$$$. The number $$$3$$$ is chosen because people can throw taho in THREE different directions.
For each taho move Jason makes, print a single line containing the answer he should have computed, assuming all of his moves were done correctly.
$$$1 \le n, m \le 3.2\times 10^5$$$
$$$1 \le A_i, v \le 10^6$$$
$$$1 \le L \le R \le n$$$
Subtask 1 (11 points):
$$$1 \le n,m \le 3000$$$
Subtask 2 (11 points):
All boxes are initially open.
There are no turon moves.
All taho moves will have $$$L=R$$$.
Subtask 3 (11 points):
All boxes are initially open.
There are no turon moves.
Subtask 4 (11 points):
There are no turon moves.
All taho moves will have $$$L=R$$$.
Subtask 5 (14 points):
There are no turon moves.
Subtask 6 (14 points):
All taho moves will have $$$L=R$$$.
Subtask 7 (14 points):
$$$1 \le n,m \le 10^5$$$
Subtask 8 (14 points):
No additional constraints.
5 6 1 2 4 8 16 1 0 1 0 1 3 2 4 2 1 5 6 3 2 4 1 1 5 2 1 5 7 3 2 4
14 20 34
Here, the boxes initially contain $$$1, 2, 4, 8, 16$$$ balls, respectively. Furthermore, the 1st, 3rd, and 5th boxes are initially open, while the 2nd and 4th boxes are initially closed.
The following queries then occur, in order:
- The sum of the boxes in [2,4] is equal to $$$2+4+8=14$$$.
- All boxes in [1,5] that are open—which are the 1st, 3rd and 5th boxes—each get 6 balls added to them. The 2nd and 4th boxes are closed, so they are ignored. Thus, the boxes now contain $$$7, 2, 10, 8, 22$$$ balls, respectively.
- The sum of the boxes in [2,4] is now equal to $$$2+10+8=20$$$.
- We now perform a turon move on the boxes in range $$$[1,5]$$$. So, now the 1st, 3rd, and 5th boxes are closed while the 2nd and 4th boxes are now open.
- All boxes in [1,5] that are open—this time, these are the 2nd and 4th boxes—each get 7 balls added to them. Thus, the boxes now contain $$$7, 9, 10, 15, 22$$$ balls, respectively.
- The sum of the boxes in [2,4] is finally equal to $$$9+10+15=34$$$.
Camila, like many young Filipinos, is a girl in love. She has fallen hopelessly in love with Shawn, her upperclassman in their Programming Club who always helps her debug her code. She wishes that she could pretend she didn't need him, but she knows that he overhears her complaining about her loops not terminating at the right times. "It's true," she lalala-ed. "It should be running."
She doesn't think Shawn even knows her name, since every time they talk, he calls her "señorita." That's perfectly fine with her, since she loves it when he calls her señorita. Thus, to win over his heart, she needs to plan out the perfect outfit for each of the next few days, so she can keep hearing him call her señorita.
She has two stacks of shirts in her cabinet, one with $$$m$$$ shirts and the other with $$$n$$$ shirts. She is going to wear each of these shirts exactly once over the course of the next $$$m+n$$$ days, and each shirt has been assigned a number from $$$1$$$ to $$$m+n$$$ to indicate on what day she wants to wear it.
On day $$$i$$$, Camila wants to wear shirt $$$i$$$ from her cabinet. Unfortunately, the shirt that she needs for the day might not be on top, and could be buried under the other shirts. Since her shirts are organized into stacks, Camila only has two operations available to her:
- Camila can take the top shirt of one stack and move it to the top of the other stack. This takes $$$1$$$ unit of energy.
- If the desired shirt $$$i$$$ is on top of either of the stacks, Camila takes it and wears it for the day. This does not cost any energy. The shirt is then thrown into the laundry, and thus permanently removed from the stack (since Camila does not do her own laundry).
She asked her mom if she could arrange her clothes differently, but her mom just replied, "Well, señorita, if you have the energy to complain about the way I do the laundry, maybe you have the energy to do it yourself, then!" Camila decided she doesn't enjoy it as much when it is her mom who calls her señorita. Regardless, her mom is right in that Camila is very lazy, and doesn't want to expend more energy than is necessary in retrieving her shirts.
Given the initial ordering of her shirts, what is the minimum amount of energy that Camila will have to expend in total in order to be able to wear the correct shirt on each of the next $$$m+n$$$ days, and have Shawn call her señorita?
Input consists of two lines. The first line begins with a single integer $$$m$$$. Then if $$$m \gt 0$$$, this is followed by a space, then $$$m$$$ space-separated integers. Similarly, the second line begins with a single integer $$$n$$$. Then, if $$$n \gt 0$$$, this is followed by a space, then $$$n$$$ space-separated integers. These represent the two stacks of clothes, with $$$m$$$ and $$$n$$$ shirts in each stack, respectively, and with the integers themselves representing the day when Camila wishes to wear each shirt. These integers are given in the order the shirts appear in the stack, with the first integer representing the shirt at the bottom of that stack, and the last integer of each line representing the shirt at the top of that stack.
Each of the integers from $$$1$$$ to $$$m+n$$$ is guaranteed to appear exactly once among the integers in the stacks.
Output one line containing the minimum amount of energy that Camila must expend.
$$$0 \le m, n $$$
$$$1 \le m+n \le 4 \times 10^5$$$
Subtask 1 (30 pts):
$$$1 \le m+n \le 4000$$$
Subtask 2 (1 point):
For each stack, if $$$i \lt j$$$, then shirt $$$i$$$ is on top of shirt $$$j$$$.
Subtask 3 (19 points):
For each stack, if $$$i \lt j$$$, then shirt $$$i$$$ is underneath shirt $$$j$$$.
Subtask 4 (50 points):
No further restrictions.
3 1 5 3 4 7 2 6 4
8
First, to retrieve shirt 1, Camila moves shirt 3 and shirt 5 to the other stack, expending 2 units of energy. Then, she can remove shirt 1 from the stacks.
Now, Camila has to retrieve shirt 2. To do this, she moves shirts 5, then 3, then 4, then 6, which are on top of shirt 2, onto the other stack. This costs 4 units of energy. Then, she can remove shirt 2 from the stacks.
Next, Camila has to retrieve shirt 3. To do this, she moves shirt 6 then shirt 4 over to the other stack, expending 2 units of energy. Then, she can remove shirt 3 from the stacks.
From this position, we can show that Camila can retrieve the remainder of her shirts without expending any more energy. We can also show that this series of moves is optimal for minimizing the amount of energy spent. Thus, Camila must spend $$$2+4+2=8$$$ units of energy in total.
A row of $$$10^9$$$ cigarettes are on the ground. They have never been touched by an angel before. Today the lives of those cigarettes are going to change. We index these $$$10^9$$$ cigarettes from $$$1$$$ to $$$10^9$$$.
$$$10^9$$$ angels walk through the ground one-by-one. The first angel skips the first cigarette, touches the second, skips the third, touches the fourth and so on. After the first angel finishes, the second angel arrives. The second angel skips the first two cigarettes, touches the next two cigarettes and so on. The third angel arrives when the second angel finishes and so on. For $$$i = 1, \ldots, 10^9$$$, the $$$i$$$th angel skips the first $$$2^{i-1}$$$ cigarettes, touches the next $$$2^{i-1}$$$ cigarettes, skips the next $$$2^{i-1}$$$ cigarettes, and so on. Once the $$$i$$$th angel has touched or has skipped the last cigarette, he then leaves. After the last angel leaves, no other angel comes and the cigarettes are never touched by any angel again.
Between two cigarettes on the ground, the holier cigarette between them is the one which has been touched more times. If the two cigarettes we are comparing have been touched the same number of times, then the holier one between the two of them is the one which has been touched more recently.
Let $$$L$$$ and $$$R$$$ be two integers, with $$$1 \le L \leq R \leq 10^9$$$. We can rank the set of cigarettes with indices $$$L, L+1, \ldots, R$$$ according to holiness. We define the positive integer $$$r_k$$$ to be index of the $$$k$$$th holiest cigarette in this set. In other words, cigarette $$$r_k$$$ is the $$$k$$$th holiest in the set. Given two integers $$$a$$$ and $$$b$$$ with $$$a \leq b$$$, find the sum of $$$r_a + r_{a+1} + \ldots + r_b$$$.
The first line of input contains $$$T$$$, the number of test cases.
Each test case consists of one line containing four space-separated integers $$$L$$$, $$$R$$$, $$$a$$$, $$$b$$$, respectively.
For each test case, output one line containing the answer to that test case.
$$$1 \le T \le 5 \times 10^4$$$
$$$1 \le L \le R \leq 10^9$$$
$$$1 \leq a \leq b \leq R-L+1$$$
Subtask 1 (10 points):
$$$R \le 100$$$
Subtask 2 (15 points):
$$$R \le 2\times 10^5$$$
$$$L$$$ will be the same across all test cases.
$$$R$$$ will be the same across all test cases.
Subtask 3 (30 points):
$$$L$$$ and $$$R$$$ are powers of 2.
$$$a=b$$$
Subtask 4 (25 points):
$$$a=b$$$
Subtask 5 (20 points):
No additional constraints.
1 1 1 1 1
1
3 2 11 6 8 2 11 1 1 2 17 12 14
18 8 31
We will examine the second sample test case.
For the first query, we are concerned with the cigarettes indexed 2 to 11. Then, if we were to sort only these cigarettes according to their holiness, we must find the sum of the 6th holiest, 7th holiest, and 8th holiest cigarettes. You can verify that $$$r_6 = 4$$$, $$$r_7 = 9$$$, and $$$r_8=5$$$. We see that cigarette 4 is holier than cigarette 9, since cigarette 4 was touched by two angels while cigarette 9 was only touched by one angel. Meanwhile, cigarette 9 and cigarette 5 were both only touched by one angel. However, we can show that cigarette 9 was touched by the 4th angel, while cigarette 9 was touched by the 3rd angel, and so cigarette 9 must be the holier one since it was touched more recently. Thus, $$$r_6+r_7+r_8=4+9+5=18$$$.
For the second query, we can verify that no cigarette in the set was touched more than 3 times, and the only cigarette to be touched exactly 3 times is cigarette 8. Thus, the holiest cigarette in the set is equal to 8, and $$$r_1=8$$$.
For the third query, we consider a different set of cigarettes, and we can verify that $$$r_{12} = 17$$$, $$$r_{13} = 9$$$, and $$$r_{14}=5$$$, so $$$r_{12}+r_{13}+r_{14}=17+9+5=31$$$. Notice that since the set of cigarettes is different, the ranks of cigarette 9 and cigarette 5 are different from what they were in the first query.
After hearing reports of a girl with incredible gravitational powers from members of the Port Mafia, Chuuya Nakahara eagerly went to visit this potential rival by the name of Nitta Hina. To his shock upon seeing her, however, Hina was merely a teen! After a momentary revelling in his height superiority, Chuuya challenged Hina to a game testing their gravitational ability. Hina was hesitant, but agreed on the condition that Chuuya would buy her a bowl of ikura afterwards.
Of course, having heard rumors of Hina and her yakuza father Yoshifumi's exploits (such as their elimination of a rival gang without help; massacred, dude), and as the vessel of the powerful Arahabaki, Chuuya was aware that a one on one match of power between them would lead to large-scale destruction. Instead, Chuuya suggested a game of control. The game would take place in a Port Mafia owned warehouse. The warehouse contains $$$n$$$ piles of crates lined up in a row, with each pile having a stack of $$$A_i$$$ crates. Define a subrange $$$[l, r]$$$ of all these piles to contain the piles $$$A_l, A_{l+1}, \ldots, A_r$$$. Now the instability of a subrange is the maximum difference in crate height between any two piles contained in the subrange. More formally, given a subrange $$$[l, r]$$$, its instability is defined as the maximum value of $$$|A_i - A_j|$$$ where $$$l \le i, j \le r$$$. Now, the game Hina and Chuuya will play goes as follows. First, they will agree on a subrange $$$[l, r]$$$ and a value $$$k$$$. Then they take turns transferring crates one at a time, carried only by their gravitational powers, from another Port Mafia warehouse with unlimited crates onto the subrange $$$[l, r]$$$. They cannot move crates already in the subrange $$$[l, r]$$$. There will be exactly $$$k$$$ turns altogether (and hence $$$k$$$ crates moved). If either of them destroy or drop a crate during their turn, they lose! Otherwise, Hina's goal is to maximize the instability of the selected subrange while Chuuya's goal is to minimize it.
Upon arrival at the warehouse, however, Hina decided to take a nap. For her, this fight was rather reminiscent to the challenges of a certain blonde-haired girl. Little did she know, this carefree confident behavior was for Chuuya rather reminiscent of a certain dark brown-haired guy. Hina's behavior thus infuriated Chuuya, making him determined to utterly win against Hina. Chuuya believes he utterly wins if the instability of the chosen subrange is minimized after the $$$k$$$ turns, assuming he places the crates on the piles optimally and Hina places them as stupidly as possible (as if she's playing to lose). Let's call this minimal value $$$c$$$. While Hina was sleeping, Chuuya was able to think of $$$q$$$ likely games with their own $$$l$$$, $$$r$$$, and $$$k$$$, in the warehouse. However, he has yet to compute each game's $$$c$$$. Help Chuuya compute this!
The first line of input contains $$$n$$$ and $$$q$$$, the number of piles in the warehouse and the number of possible games Chuuya is thinking of, respectively.
The second line of input contains $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$, the number of crates in each pile.
The next $$$q$$$ lines each contain three space-separated integers $$$l$$$, $$$r$$$, and $$$k$$$, describing a game setting Chuuya is thinking of.
For each query, print a single line containing a single integer denoting the value $$$c$$$ for the game Chuuya is thinking of. Since $$$c$$$ may be very large, only output its remainder when divided by $$$1234567890$$$.
$$$1 \le n \le 3 \cdot 10^5$$$
$$$1 \le q \le 3 \cdot 10^5$$$
$$$1 \le A_i \le 10^9$$$
$$$1 \le k \le 10^{12}$$$
Subtask 1 (25 points): $$$n, q \le 200$$$
Subtask 2 (24 points): $$$n, q \le 5000$$$
Subtask 3 (36 points): $$$n, q \le 60000$$$
Subtask 4 (15 points): $$$n, q \le 300000$$$
5 5 1 2 3 7 4 3 5 10 1 4 8 2 5 1 2 5 2 2 5 3
0 3 4 4 3
For the first query, we consider the boxes in the range $$$[3,5]$$$, which have 3, 7, and 4 crates in each pile, respectively. There are 10 turns in total, meaning Hina and Chuuya each get 5 turns, and thus 5 crates each to move onto the piles. If Hina were stupid enough to place all 5 of her crates on the 3rd pile, and Chuuya were smart enough to put 1 crate on the 4th pile and 4 crates on the 5th pile, then all three piles would have 8 crates in them, giving an instability of 0.
For the third query, it can be verified that placing the 1 crate on the 2nd pile would give the smallest instability of 4.
A national beauty pageant is the qualifier for an international beauty pageant, whose evening gown segment is held on a lava lake. Catriona, Emma, and Nadine are the three finalists of this. In preparation for the international pageant's evening gown segment, the night gown segment of this pageant is held on a $$$16 \times 16$$$ grid of squares, each containing a different sort of liquid.
Exactly one of the squares is a stone that the three contestants start on. Each step consists of walking from a square to the square in front of it, behind it, to its left, or to its right. Each square contains one of three things: lava, water, or lemonade.
Fortunately, all three contestants are fireproof, immune to lava, and can walk on liquids. Unfortunately, the contestants are wearing different colors of gowns, which means they can only walk on liquids that match the colors of their gowns:
- Catriona is wearing an orange gown. Since orange is red mixed with yellow, she can walk on only lava or lemonade.
- Emma is wearing a green gown. Since green is yellow mixed with blue, she can walk on only lemonade or water.
- Nadine is wearing a purple gown. Since purple is blue mixed with red, she can walk on only water or lava.
Can you find a possible layout of the grid that satisfies this? If there is no such layout, say so.
The first line of input contains $$$t$$$, the number of test cases.
Each test case consists of a single line containing three space-separated integers $$$c$$$, $$$e$$$ and $$$n$$$.
For each test case, first output a single line containing either YES or NO denoting whether it is possible. If you printed YES, output 16 more lines, each containing 16 characters from the following:
- S, which represents the starting stone.
- ., which represents lava.
- #, which represents water.
- $$$\sim$$$, which represents lemonade.
$$$0 \le t \le 60000$$$
$$$9 \le c, e, n \le 111$$$
Subtask 1 (4 points):
$$$t \le 1000$$$
$$$c = e = n = 21$$$
Subtask 2 (7 points):
$$$t \le 1000$$$
$$$c$$$, $$$e$$$ and $$$n$$$ belong to the set $$$\{21, 42\}$$$
Subtask 3 (8 points):
$$$t \le 20000$$$
$$$c = 16$$$
$$$e \ge 32$$$
$$$n \ge e + 16$$$
Subtask 4 (18 points):
$$$t \le 20000$$$
$$$21 \le c, e, n \le 42$$$
Subtask 5 (42 points):
$$$c + e + n \le 168$$$
Subtask 6 (21 points):
No additional constraints.
1 110 89 101
YES #####.#~~~####.. ####..##~~####.. ......##~~#####. .##....##~~####. .###.##.#~~.##.# ###..##.~~..S.#. .##.#..~~~...... ...##.~.~~..###. #.##.~.~~...#### ##..~.~~..###### ##.~~~~~~..##### #.~~~~~~~.#..### .~~##.~~~.#.##.. .~.###..~~.####. .~~....~~~.##### #.~~~~~~~.######
A long time ago...
In a galaxy far far away...
Where nobody cared about how chocolates should be shared...
There was Og.
One day, Og was very bored. He has not done anything interesting after discovering fire a few months back. And so he decided to write a program in [C+]+. (It is the predecessor of the languages C, C++, C++++, C++C+CC+++C, and so on.)
[C+]+ is very similar to C++, but it has a Python-like syntax and has infinite memory. In particular, ints are arbitrary precision. Arrays are zero-indexed.
Here is Og's program.
Let L = new empty list of pairs
L.push_right( pair(root, 0) )
while L is not empty:
(node, i) = L.pop_right()
print(node.index)
if i != node.children.length:
L.push_right( pair(node, i+1) )
L.push_right( pair(node.children[i], 0) )
Nodes are numbered 1 to $$$n$$$. Ug, Og's brother, edited the program while Og was not looking. He inserted lines in Og's code. In particular, an else clause is inserted, so the code now looks like:
Let L = new empty list of pairs
L.push_right( pair(root, 0) )
while L is not empty:
(node, i) = L.pop_right()
print(node.index)
if i != node.children.length:
L.push_right( pair(node, i+1) )
L.push_right( pair(node.children[i], 0) )
else:
L.push_left( pair(node, 0) )
Og was expecting his code to halt quickly. However, after Ug's shenanigans, it continued printing numbers. Og waited patiently. After $$$10^{10^{10^{100}}}$$$ years, Og is still waiting. It has printed at least $$$10^{100}$$$ numbers at this point. Og got bored again. To pass the time, he decided to look at the $$$i_1$$$th element, $$$i_2$$$th element, ..., $$$i_k$$$th element of the list. What are the $$$k$$$ numbers that Og will see?
The first line of input contains two space-separated integers $$$n$$$ and $$$k$$$. The nodes are indexed from $$$1$$$ to $$$n$$$. The tree is rooted at node $$$1$$$.
The $$$i$$$th of the next $$$n$$$ lines describes the children of node $$$i$$$. Specifically, it contains $$$c_i+1$$$ space-separated integers $$$c_i, x_1, x_2, \ldots, x_{c_i}$$$, where $$$c_i$$$ is the number of children of node $$$i$$$, and $$$(x_1, x_2, \ldots, x_{c_i})$$$ are the children of node $$$i$$$.
The $$$j$$$th of the next $$$k$$$ lines contains $$$i_k$$$, as described in the problem statement.
Output $$$k$$$ lines. The $$$j$$$th line must contain an integer denoting the $$$i_j$$$th element of the list.
$$$1 \le n \le 50$$$
$$$1 \le k \le 143$$$
$$$0 \le c_i \lt n$$$
$$$1 \le x_i \le n$$$
It is guaranteed that the input describes a tree rooted at node $$$1$$$.
Subtask 1 (27 points): $$$1 \le i_j \le 10^{5}$$$
Subtask 2 (25 points): $$$1 \le i_j \le 10^{9}$$$
Subtask 3 (18 points): $$$1 \le i_j \le 10^{15}$$$
Subtask 4 (25 points): $$$1 \le i_j \le 10^{18}$$$
Subtask 5 (5 points): $$$1 \le i_j \le 10^{100}$$$
4 7 2 2 4 1 3 0 0 6 9 69 143 214 241 420
4 2 2 3 3 3 3