Professor Mitrovoak has a rectangular image of his Slowbro, but wants to increase its resolution! The image file uses the Adjustable-Compression Photograph Composition (ACPC) image format, which allows its width $$$W$$$ and height $$$H$$$ to be stretched $$$K$$$ times without losing image details $$$(0 \le W, H, K \le 10^4)$$$. Professor Mitrovoak wants his image to have the maximum area possible.
In one stretch operation, either width $$$W$$$ or height $$$H$$$, but not both, can be increased by $$$1$$$. Professor Mitrovoak can stretch his image up to $$$K$$$ times.
Professor Mitrovoak wants the highest resolution possible. Given initial width $$$W$$$, initial height $$$H$$$, and limit $$$K$$$, determine the maximum area of the professor's picture!
The only line of input is three space-separated integers $$$W$$$, $$$H$$$, and $$$K$$$ ($$$0 \le W, H, K \le 10^4$$$).
Output a single integer: the maximum area an image can have after up to $$$K$$$ stretch operations.
3 7 3
42
0 10 0
0
0 0 5
6
In the first test case, the image has a width of $$$3$$$ pixels and a height of $$$7$$$ pixels, and up to $$$3$$$ stretch operations can be done. By stretching the width $$$3$$$ times, the final width is 6 and the final height is 7. Thus, the area of the image $$$(W*H=6*7)$$$ is $$$42$$$. This is the maximum area possible.
Travelers often take freelance work in filling out Pokédex entries, which are written in a special markup language called PokéTeX, which supports regular and bolded text. However, Pokédex entries in the Johto region are written in MarkDunsparce, which also supports bolded text, but is formatted differently and thus incompatible with PokéTeX.
You are tasked with writing a translator program that formats MarkDunsparce entries into PokéTeX entries. In MarkDunsparce, bolded text is formed by **surrounding a phrase by two pairs of asterisks**. But in PokéTeX, bolded text is formed by \bf{beginning the phrase with "\bf" and surrounding it with curly braces}.
Your translator program will be given a string in valid MarkDunsparce format, and it must convert the bold phrases to PokéTeX format.
Every bolded phrase is surrounded by two pairs of asterisks, with $$$4$$$ asterisks per bolded phrase. Asterisks will only appear as part of valid bolded phrases – there are no lone asterisks – and there are no instances of four asterisks in a row without a character in between. Thus, inputs like **Mareep****Bayleef**, **Lugia***, or St*ryu will not be given. All bolded phrases will contain at least one non-space character, and are guaranteed to start and end with a non-space character. The text will not start nor end with a space.
The only line of input is one single MarkDunsparce string $$$M$$$: the line to translate to PokéTeX $$$(1 \le |M| \le 1000)$$$.
Output a single string: the input string translated into PokéTeX.
For clarity, sample input/output are on multiple lines in the printout, but each input and output is only one line.
**This species** was particularly treasured **in the old days**, as they would share **precious salt**.
\bf{This species} was particularly treasured \bf{in the old days}, as they would share \bf{precious salt}.
...it is what you do with **the gift of life** that determines who **you** are.
...it is what you do with \bf{the gift of life} that determines who \bf{you} are.
Th**is i**s not **t**he t**im**e to u**se t**hat.
Th\bf{is i}s not \bf{t}he t\bf{im}e to u\bf{se t}hat.
**Praise** **Helix**
\bf{Praise} \bf{Helix}
This species was particularly treasured in the old days, as they would share precious salt.
...it is what you do with the gift of life that determines who you are.
This is not the time to use that.
Praise Helix
Mr. Mime enjoys walking around town playing tricks on townspeople. In particular, Mr. Mime likes to trap unassuming individuals using invisible walls, forcing them to solve a puzzle for their freedom.
Today, Mr. Mime has trapped you and starts shuffling the air, throwing it at you until suddenly you're able to see a deck of cards being dealt out to a table in front of you! Looks like this deck of cards is your puzzle for the day. It seems to be a $$$52$$$ card deck with $$$4$$$ suits ($$$H$$$, $$$S$$$, $$$D$$$, $$$C$$$) and $$$13$$$ numbered cards for each suit (numbered $$$1$$$ through $$$13$$$). However, some cards are missing its suit, some cards are missing its number, and the rest are missing both. You see that there are $$$N$$$ cards that are missing its suit but not its number and $$$M$$$ cards that are missing its number but not its suit ($$$1 \leq N, M \lt 52$$$, $$$N + M \leq 52$$$). There isn't a single card that is complete with both a suit and number.
As you stare at these cards, Mr. Mime points at the deck and gives you a strange look. It seems that in order to be free, you must determine whether or not this deck is actually a valid $$$52$$$ card deck if you assign missing suits and numbers to all the cards. A valid $$$52$$$ card deck contains all $$$13$$$ unique numbers for each suit. Good luck solving Mr. Mime's puzzle!
The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of the test cases follow.
The first line of each test case consists of two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \lt 52$$$, $$$N + M \leq 52$$$), the number of cards that are either missing its suit or number but not both, respectively.
The second line of each test case consists of $$$N$$$ space-separated integers, providing the number of a card that doesn't have its suit (from $$$1$$$ to $$$13$$$).
The third line of each test case consists of $$$M$$$ space-separated characters, providing the suit of a card that doesn't have its number (either $$$H$$$, $$$S$$$, $$$D$$$, or $$$C$$$).
For each test case, output "YES" if the cards provided are a valid deck. Otherwise, output "NO". You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
53 41 2 3H S D C5 21 1 1 1 1S D12 121 1 1 1 2 2 2 2 3 4 5 6H H H H H H H H H H H H12 111 1 1 1 2 2 2 2 3 4 5 6H H H H H H H H H H H17 191 1 1 2 2 3 3 3 3 4 4 4 4 5 5 5 5H H H H H H H H H S S S S S S S S S H
YES NO NO YES YES
In the first test case, a possible assignment of the cards is $$$(1, H)$$$, $$$(2, H)$$$, $$$(3, H)$$$ for the cards that don't have its suit and $$$(5, H), (6, S), (7, D), (8, C)$$$ for the cards that don't have its number. The remaining cards (missing both suit and number) can be assigned to fill up the remaining $$$45$$$ cards to form a valid deck.
In the second test case, it's not possible for there to be $$$5$$$ cards that have number $$$1$$$. There can only be $$$4$$$ cards with the same number for each suit, so it is not possible to form a valid deck.
Having stayed in the forest his whole life, Shroomish wants to go out and explore the world! Unfortunately, having not evolved a protective hat yet, Shroomish is very afraid of sunlight. You decide to help by making a pair of sunglasses for Shroomish. Unfortunately, Shroomish is quite particular about how these sunglasses should look. Specifically, each of the 2 lenses must be in the shape of an equilateral triangle. Shroomish also demands that each of these lenses have sidelengths $$$a$$$ and $$$b$$$ respectively.
Unfortunately, the only lens store in town sell lenses which are perfect circles, so you need to buy a circular lens and cut out the triangular lenses yourself. While you are able to make cuts, you do not have the tools to merge two pieces together.
Having explained yourself to the store owner, she explains that they have a variety of lens sizes; you are able to buy a circular lens with radius $$$r$$$, for any positive real number $$$r$$$. However, she expresses disdain at the idea of cutting the lenses, and only allows you to buy one lens. Additionally, she dislikes wasting resources, and will only sell you a lens if it is the smallest lens you need to complete your task. Even worse, she wants you to calculate the size of the lens you need to buy!
Given all these requirements, what is the radius of the lens you need to buy to craft the lenses needed to make Shroomish a pair of sunglasses?
The only line of each test case contains two integers $$$a$$$ and $$$b$$$, the sidelengths of the two triangles respectively $$$(1 \leq a, b \leq 10^6)$$$.
Output a single number, the radius of the lens you will buy. Your answer will be accepted if it is within an absolute or relative error of $$$10^{-6}$$$ to the Jury's answer.
Remember to print floating-point numbers with enough precision! This can be done explicitly with f-strings in Python, or with setprecision() in C++.
1 1
0.8660254038
69 420
242.4871130596
1000 2727
1613.8383399523
In test case 1, an optimal arrangement could look like this:
In test case 2, an optimal arrangement could look like this:
In test case 3, an optimal arrangement could look like this:
Espeon has the biggest mouth in the world, always claiming to be the number one psychic-type Pokémon, which incurs the wrath of Mewtwo. Sick of Espeon's constant boasting, Mewtwo challenges Espeon to a psychic duel with a stack of Z-Crystals.
The rules of the game are as follows. Mewtwo and Espeon take turns drawing a Z-Crystal from the top of the stack and reading its strength value $$$s$$$ $$$(1 \le s \le 100)$$$. The player then makes one of the following two choices:
- Discard the drawn Z-Crystal, with no side-effects.
- Crush the Z-Crystal, eliminating the next $$$s$$$ Z-Crystals from the top of the stack.
To any other Pokemon, the strength values would be hidden until drawing the Z-Crystal, but since both Mewtwo and Espeon are Psychic types, they can use Future Sight to learn the strengths of all the Z-Crystals before the first card is drawn. Mewtwo, overly confident as always, allows Espeon to pick whether to go first or second. Unbeknownst to Mewtwo, Espeon is a highly skilled gamer, so Espeon knows that this choice can guarantee victory. Assuming both Mewtwo and Espeon play optimally, determine who wins if Espeon starts first.
The first line will be an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the number of Z-Crystals in the deck.
The next line will contain $$$N$$$ space-separated integers $$$s_i$$$ ($$$1 \leq s_i \leq 100$$$), the strengths of the Z-Crystals in the order they appear in the stack; the leftmost integer represents the Z-Crystal on the top of the stack at the start of the game.
If Espeon can win by going first, output "YES". Otherwise, output "NO". You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
21 1
YES
31 1 1
NO
55 3 1 1 1
NO
Each night, deep in the Dreamyards, a hungry Munna prepares to go on a journey to feast upon the tasty dreams of nearby Pokémon. There are $$$D$$$ $$$(1 \le D \le 10^4)$$$ dreams in total, dream $$$1$$$ to dream $$$D$$$, and each dream has some specific satisfaction $$$D_i$$$ $$$(1 \le D_i \le 10^9)$$$ that Munna gets from eating it. Munna's hunger varies night by night – on any of the $$$H$$$ $$$(1 \le H \le 10^5)$$$ given nights, Munna can eat dreams with satisfaction values whose sum does not exceed its hunger for that night $$$H_i$$$ $$$(0 \le H_i \le 10^{13})$$$.
Munna has a list of $$$P$$$ $$$(0 \le P \lt D)$$$ unique pairs of dreams. Each pair $$$a_i$$$ and $$$b_i$$$ informs Munna that dream $$$b_i$$$ can only be eaten directly after dream $$$a_i$$$. It is guaranteed that there are no cycles – i.e. there is no set of dreams that all depend on each other. Each dream has at most one prerequisite dream, so all values of $$$b_i$$$ are unique.
This particular Munna loves to eat dreams along a path. A path of dreams is a list of dreams to eat where:
- The first dream has no prerequisite dreams.
- For each consecutive pair of dreams $$$d_i$$$ and $$$d_{i+1}$$$ in the path, that pair exists in the list of $$$P$$$ edges.
Each night, Munna has some amount of hunger $$$H_i$$$. For each night, find the path with the highest satisfaction sum that is less than or equal to $$$H_i$$$. If there are multiple such paths, find the path with the minimum number of dreams.
Note: This problem requires the use of 64-bit integers. In C/C++ use long long and in Java use long. Not a concern for Python or Javascript.
The first line consists of three integers $$$D$$$, $$$P$$$, and $$$H$$$: the number of dreams, pairs, and nights.
The second line consists of $$$D$$$ space-separated integers $$$(1 \le D \le 10^4)$$$: the satisfaction values of each dream $$$(1 \le D_i \le 10^9)$$$.
Following these two lines are $$$P$$$ $$$(0 \le P \lt D)$$$ lines, where each line is a pair of space-separated integers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le D, a_i \neq b_i)$$$: dream $$$b_i$$$ can only be eaten directly after dream $$$a_i$$$.
The last line has $$$H$$$ space-separated integers $$$(1 \le H \le 10^5)$$$: Munna's hunger on each night $$$(0 \le H_i \le 10^{13})$$$.
Output $$$H$$$ lines, with line $$$i$$$ containing two space-separated integers: the satisfaction and the number of dreams for the path with highest satisfaction sum less than or equal to $$$H_i$$$. If multiple paths result in the same satisfaction, output the minimum number of dreams of the paths.
7 4 63 1 5 4 15 66 107 52 41 21 34 10 9 30 1 100
4 2 10 1 8 2 25 2 0 0 66 1
On night $$$1$$$, Munna eats dreams $$$1 \rightarrow 2$$$.
On night $$$2$$$, Munna eats dream $$$7$$$.
On night $$$3$$$, Munna can eat $$$1 \rightarrow 2 \rightarrow 4$$$ or $$$1 \rightarrow 3$$$. Munna chooses the shorter path $$$1 \rightarrow 3$$$.
Oleana is choreographing a Falinks Formation Dance. Her Falinks is special: it has $$$n$$$ troopers in its squad. The dance follows a precise set of instructions, represented by a single permutation $$$\pi$$$, where each trooper at position $$$i$$$ moves to a new position $$$\pi _i$$$.
Chairman Rose wants to figure out the exact dance instruction (the permutation), but he has limited information! Initially, he sees the Falinks troopers standing in their standard formation: $$$\bf{1}$$$ through $$$\bf{n}$$$ in order. Then, Oleana commands her Falinks to perform the dance repeatedly, applying $$$\pi$$$ over and over. After each execution of the dance, she tells Chairman Rose how many troopers are back in their original positions.
Chairman Rose, being a little silly, accidentally spills coffee on his notes! Now he can only read the first $$$\lfloor n/2\rfloor$$$ recorded values.
Help Chairman Rose determine the number of possible Formation Dances (permutations) that Oleana could have chosen. Since this number can be large, return the answer modulo $$$10^9+7$$$.
The first line contains one integer $$$2 \leq n \leq 10^5$$$.
The second contains $$$\lfloor n/2\rfloor$$$ integers $$$0 \leq p_i \leq n$$$, the number of Falinks troopers that return to their original position after $$$i$$$ permutations by $$$\pi$$$.
The input is guaranteed to be valid.
Return a single integer mod $$$10^9 + 7$$$, the number of different possible dance instructions (permutations) Oleana could have picked to be $$$\pi$$$.
31
3
51 5
15
In the first test case, there are 6 possible permutations of length 3: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). We know that exactly one trooper returned to their original position on the first dance instruction. This corresponds to exactly the permutations (1, 3, 2), (2, 1, 3), and (3, 2, 1).
Hermione is a world-renowned Pokémon stylist who prefers to emphasize a Pokémon's abilities in their outfit. Her latest idea is a snazzy Spinarak-silk symmetric shawl and she needs your help to bring it into reality.
Hermione's workshop has a weaving station that can weave Spinarak silk into rectangular patterns of tiles. Each tile in the pattern can either have a hole in the middle – like lace – or be fully filled. The weaving station is automated and takes a specific format of ASCII input. The input begins with a declaration of the height $$$h$$$ and width $$$w$$$ of the pattern $$$(1 \le h, w, \le 100)$$$, and then $$$h$$$ lines of $$$w$$$-length strings consisting of '.' and '#' representing holed and filled tiles, respectively.
As a highly experienced stylist, Hermione has a very particular vision for this shawl, such that the design must obey the following rules:
- The pattern must be both horizontally and vertically symmetrical.
- There must be exactly $$$n$$$ filled tiles in the pattern.
- There must be exactly $$$k$$$ areas of filled tiles in the pattern, where an "area" is a cardinally contiguous set of filled tiles.
- The sizes of any two areas must not differ by more than $$$3$$$ – where an area's "size" is the number of filled tiles of which it consists.
Hermione has developed these constraints, but is unsure which combination of $$$n$$$ and $$$k$$$ will look best. She needs your help, so she will send over various combinations of $$$n$$$ and $$$k$$$ to prototype, and she expects you to send back an input pattern that matches all of the above constraints.
To ease your development, Hermione will only send combinations of $$$n$$$ and $$$k$$$ that have the same parity i.e. $$$n$$$ is odd if and only if $$$k$$$ is odd. It is guaranteed that a valid design always exists under these constraints.
The first line contains two integers, $$$n$$$ and $$$k$$$ $$$(0 \lt k \le n \le 10^3, \; n \equiv k \text{ mod } 2)$$$, the number of contiguous areas and the number of filled tiles to include in your design, respectively.
On the first line, output two integers, $$$h$$$ and $$$w$$$ $$$(0 \lt h, w \le 100)$$$, the dimensions of your design. On the next $$$h$$$ lines, print your design using $$$w$$$-length strings consisting of '.' for holed tiles and '#' for filled tiles.
7 5
1 11 #.#.###.#.#
6 4
6 5 ..... ..#.. .#.#. .#.#. ..#.. .....
25 7
9 11 ........... ...##.##... ...##.##... .....#..... .##.###.##. .....#..... ...##.##... ...##.##... ...........
20 8
12 12 ............ ............ ..##....##.. ..##....##.. ....#..#.... ............ ............ ....#..#.... ..##....##.. ..##....##.. ............ ............
As a part of her research into the origin of Pokémon, Professor Juniper is studying a newly-discovered dictionary of words written in ancient Unown symbology. This enormous dictionary contains thousands of words, some of which are thousands of symbols in length. But, most surprisingly, the dictionary uses a large number of never-before-seen Unown symbols, one million of them to be exact, which Professor Juniper has enumerated in the range $$$[0, 10^6)$$$.
As part of her unorthodox research methods, Professor Juniper has decided to play "word ladder" with these Unown words. This is a game where you start with a word from the dictionary and you can perform the following operation any number of times: change a single symbol in your current word as long as the resultant word also exists in the dictionary. Often, the word ladder will have a goal, like getting from "peek" to "hear". In this example, you can go from "peek" to "peel" to "heel" to "heal" to "hear". The score of a word ladder game is the number of operations performed to get from the start to the end, with a lower number being more desirable.
As the professor's favorite data analyst, she wants you to develop an algorithm for finding the lowest word ladder score on a given set of Unown words. More specifically, Professor Juniper gives you a "subdictionary" of $$$n$$$ words – represented as arrays – all with equal length $$$m$$$, and she wants you to find the length of the shortest sequence of legal change operations to get from the first word to the last word. If no such sequence exists, report $$$-1$$$.
Initial analysis shows that the words in the dictionary vary significantly, such that no word can produce $$$100$$$ or more other words in a single operation.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(2 \le n, m \le 10^5, n \times m \le 10^6)$$$ – the number of words in the subdictionary and the length of the words, respectively.
The following $$$n$$$ lines each contain $$$m$$$ space-separated integers that define an Unown word. The $$$j$$$th integer on the $$$i$$$th line is $$$A[i][j]$$$ $$$(0 \le A[i][j] \lt 10^6)$$$. Each word is distinct, i.e. no two words are completely equal.
It is guaranteed that, for any $$$A[i]$$$, the number of words in the subdictionary that $$$A[i]$$$ can produce with a single-element change is less than $$$100$$$.
Output a single integer, the number of operations required to get from $$$A[0]$$$ to $$$A[n-1]$$$ with the above rules. If there is no way to get to $$$A[n-1]$$$, output $$$-1$$$.
8 41 2 3 41 2 4 31 2 3 30 2 3 40 1 3 30 2 3 33 2 3 33 3 3 3
3
4 310 10 1010 20 1020 10 2020 20 20
-1
Gold opens his phone for the first time after 25 hours and immediately receives a barrage of messages from his trainer friends inviting him to rematch battles! In Gold's message history, there are $$$m$$$ distinct friends numbered $$$1$$$ to $$$m$$$ who have sent him messages, arranged in a stack. Gold recalls the starting arrangement of his message history on the previous occasion he checked his phone. He thinks the arrangement may have changed, but he's not sure how.
The arrangement of the friends can only change via a transition, which is defined as taking any element from the stack and moving it to the top of the stack. Note that a transition may move an element that was already on the top of the stack back to the top. Assuming there are exactly $$$t$$$ transitions, how many distinct sequences of transitions could have caused the starting arrangement to change into the one Gold is now seeing? Since this number can be large, return the answer modulo $$$10^9+7$$$.
An example of $$$3$$$ transitions moving $$$3$$$, then $$$1$$$, and then $$$3$$$, transforming the starting arrangement $$$123$$$ as follows: $$$123 \to 312 \to 132 \to 312$$$. This is one of the possible transition sequences (that is, $$$[3, 1, 3]$$$) for sample 1. The first line contains two integers $$$m$$$ and $$$t$$$ $$$(1 \le m, t \le 5000)$$$.
The second line contains $$$m$$$ integers representing the starting arrangement of the elements.
The third line contains $$$m$$$ integers representing the ending arrangement of the elements.
The elements are listed from the top to the bottom of the stack.
Each "arrangement" is a permutation, containing exactly one of each integer in the range $$$[1, m]$$$.
Output the number of distinct $$$t$$$-length transition sequences that can change the starting arrangement to the ending arrangement, modulo $$$10^9+7$$$.
3 31 2 33 1 2
5
5 101 5 3 2 45 4 3 2 1
76630
In sample 1, the following histories of message notifications can take us from the starting arrangement to the ending one: $$$[1, 1, 3]$$$, $$$[1, 3, 3]$$$, $$$[2, 1, 3]$$$, $$$[3, 1, 3]$$$, $$$[3, 3, 3]$$$. The figure in the statement illustrates the sequence $$$[3, 1, 3]$$$.