Gason and his bestie Gteve love the letter 'G', and they successfully hacked into the Villager News' director's computer where the director stores all of the news headlines to be broadcasted. Since Gason loves the letter 'G' so much, he decides to replace the first character of every single headline with the uppercase letter 'G'! Now Gason is watching the Villager News (with Gteve) and is wondering how many headlines he modified made it into the actual news broadcast.

Given the initial headlines stored on the news director's computer and the final headlines which were actually broadcasted, determine how many headlines in the news broadcast were those possibly modified by Gason and Gteve.

Everything is case-sensitive!!!

The Potato King is plotting his next moves to bring a decisive victory in the Great Potato War! Manually planting and harvesting potatoes for $$$11$$$ hours a day is giving him carpal tunnel, so he's looking into trading with a group of $$$N$$$ ($$$2 \le N \le 1,000$$$) villagers to get potatoes. For each of the $$$N$$$ villagers, villager $$$i$$$ has an exchange rate of $$$P_i$$$ ($$$1 \le P_i \le 1,000$$$); that villager is willing to trade $$$P_i$$$ potatoes for an emerald, or one emerald for $$$P_i$$$ potatoes.

The Potato King can do some amount of trade operations. In a single trade, he first selects two villagers $$$i$$$ and $$$j$$$. Then, he spends $$$P_i$$$ potatoes to get an emerald from villager $$$i$$$, then spends that emerald to get $$$P_j$$$ potatoes from villager $$$j$$$. This results in a net gain of $$$P_j-P_i$$$ potatoes. Each villager may be selected no more than once; otherwise, the villagers may get suspicious and start to undergo mitosis. Note that the Potato King has enough potatoes initially to trade with any villager.

Given $$$N$$$ villagers where the $$$i$$$th villager buys or sells potatoes at the exchange rate of $$$P_i$$$ potatoes per emerald, find the maximum number of potatoes that the Potato King can gain!

A horrifying new species of slime was just discovered, the "tree slime". A normal slime splits into smaller slimes when it is killed. Tree slimes work differently.

On command, a tree slime of size $$$k \gt 1$$$ will spawn 2 smaller tree slimes of size $$$k-1$$$; the larger tree slime remains unharmed in the process, though it can only do this once in its life. Those smaller tree slimes can also spawn 2 tree slimes of size $$$k-2$$$, until tree slimes of size 1 are spawned, which are the smallest possible tree slime and cannot spawn any smaller tree slimes.

Luckily, the scientists in the village have made a breakthrough. They've found that, if any of the tree slimes die, the tree slime they spawned from – the "parent" – also dies. So, if you hit a tree slime to kill it, then its parent will also die if it's still alive, and the parent's parent as well, and so on.

Suddenly, you hear a terrifying rumble. The village lookout spots a massive tree slime approaching the village. Right before your eyes, this tree slime and all of its descendants spawn all the tree slimes they possibly can. The lookout counts and says there is a line of $$$2^n$$$ size 1 tree slimes leading the charge, with all of the parent tree slimes following behind. The blacksmith has forged you a sword in a hurry, but it only has $$$h$$$ hits before it breaks. What's the maximum number of tree slimes you can kill?

NOTE: Both the input and output may be large, make sure to use 64-bit integers (C/C++: long long, C#/Java: long, Python: doesn't matter)

You have just invited your friend to your Minecraft server and want to play a fun game with them! You have prepared $$$n$$$ chests in a row that contain random loot. The chests are numbered from $$$1$$$ to $$$n$$$ (left to right). Chest $$$i$$$ contains loot that has value $$$v_i$$$. Your friend will start at the chest on the very left and open them in order to the right. To make the chest opening as dramatic as possible for your friend, you want the loot to generally increase in value in comparison to the loot found previously. To quantify this, we define the "drama" of chest $$$i$$$ to be how much greater its value is compared to all the previous chests opened with a smaller value. Formally, the drama of chest $$$i$$$ is $$$\sum_{j=0}^{i-1} \max(0, v_i - v_j)$$$. Then, the total drama from the chest opening would be the total sum of the drama of each chest $$$i$$$.

You have peeked ahead at all the loot in each chest, and you notice that the value of loot is nonincreasing from left to right, resulting in a total drama of $$$0$$$! That's not going to be very dramatic for your friend, so you now want to rearrange the chests. You can rearrange the chests by taking a prefix of them and moving them to the end of the row. Specifically, if your chests initially had loot with values $$$v_1, v_2, \ldots, v_{n-1}, v_n$$$ (left to right), then it can be rearranged to $$$v_l, v_{l+1},\ldots, v_n, v_1, v_2,\ldots, v_{l-1}$$$ (left to right) for any $$$1\leq l\leq n$$$. Find the maximum total drama of the chest opening over all the possible rearrangements so that your friend can have a dramatic time.

Standard stack sizes in Minecraft are $$$2^6=64$$$ for most blocks and items, $$$2^4=16$$$ for select items, and $$$2^0=1$$$ for tools and special items. However, Mojang's latest update has a lot of bugs, forcing items to stack to exactly any integer power of $$$2$$$, including powers greater than $$$64$$$: $$$128$$$, $$$256$$$, and so on! Since you were down in your mineshaft before the update dropped, you decide to use the opportunity to start moving your supply of gems back to your base above ground.

You have diamonds and emeralds in the mineshaft's storage that you want to bring, but you can't put them in your inventory since you're carrying lots of other important items (i.e. Pigstep and deadbushes). But, you do have a bundle, a portable container that fits exactly $$$N$$$ items. Due to another bug in the update, you can only insert stacks of items in alternating order, but you can start with either diamonds or emeralds. For example, if you first insert a power-of-two stack of diamonds, the next stack you insert must be a power-of-two stack of emeralds.

For example, the bundle might be able to fit $$$4$$$ gems. There are $$$12$$$ possible ways to put them in, shown below. Note that each sequence of the same item must have a length matching some power of $$$2$$$; as such, a length of $$$3$$$ is unable to be added to the bundle.

DEDE, EDED, DDED, EEDE, DEED, EDDE, DEDD, EDEE, DDEE, EEDD, DDDD, EEEE

You're curious about how many different ways you could completely fill your bundle. Given the capacity of the bundle $$$N$$$, determine how many different ways the bundle can be filled. Assume that you have at least $$$N$$$ gems of each type.

You have $$$n$$$ chicken jockeys, as one does, and you want to showcase them in your ULTIMATE ultra-secure OP hidden secret minecraft base in as square of a bounded area as possible. Each chicken jockey fills a 1 block by 1 block area on the floor. The $$$i^{th}$$$ chicken jockey has a height of $$$h_i$$$ chickens. You must lay the chicken jockeys out in a grid, where each chicken jockey is connected* to every other chicken jockey. Furthermore, every row and column must have at least one chicken jockey in it.

Finally, you MUST ensure that a chicken jockey is strictly taller than the one in front of it so that you can see each zombie's face, because otherwise what's the point (you love chickens and zombies).

Formally, if a chicken jockey $$$a$$$ is in row $$$i$$$ and column $$$j$$$ and another chicken jockey $$$b$$$ in row $$$i+k$$$ and column $$$j$$$ for $$$k \gt 0$$$, you must ensure that $$$h_a \lt h_b$$$. You can maximize the "squareness" of your minecraft base by minimizing the absolute difference between the number of rows and the number of columns used in your grid.

Given a list of chicken jockey heights, output the absolute difference of the dimensions of the most square bounded minecraft base such that you can see each zombie's face.

*Connected means you can reach any chicken jockey from another by take steps going up, down, left, or right walking on top of zombie heads.

You've invented the Armorstand Circle Placement Constructor (ACPC), a command to generate circles in Minecraft! Using repeating command blocks, ACPC generates a circle on the ground of a given radius $$$r$$$ by first spawning a central armor stand, which then repeatedly spawns another armor stand entity $$$r$$$ blocks in front of it and rotates slightly clockwise. The central armor stand then forces all the other armor stands to face inwards, creating the illusion of a circle.

You're planning to use ACPC to generate a circle as part of a house you're designing in a plains biome. You select a $$$N \times N$$$ area to place your circle, where $$$N$$$ is even, given as a 2D grid. Your circle will be centered at the middle of the grid. Within the grid, certain blocks have tall grass growing on them; you want to use this foliage as part of your design. A block without tall grass is marked as ., while a block with tall grass is marked as #.

You want to find the smallest radius $$$r$$$ to use such that the circle touches the most blocks with tall grass. Tall grass touches the circle if the circumference of the circle intersects or is tangent to the perimeter of that tile. A circle may have a radius of $$$0$$$, where it is just a point at the center of the grid. In this case, blocks with perimeters that contain this point are touching the circle. Notably, we're only considering the distance of the circle's circumference from the central point, disregarding the base areas of the individual armor stands. Additionally, the circle may extend out of the grid.

Given a $$$N \times N$$$ grid where $$$N$$$ is even, output the radius of the smallest circle centered in the middle of the grid with the circumference that touches the most tall grass!

Chat, we've done it! We've made a computer... in Minecraft! The only thing is, it has a peculiar instruction set called RSC-IV, or "Redstone Computer 4". "Redstone Computer" because the logic is built with redstone, and "4" because there are only 4 values that it understands.

Because it only understands 4 values, RSC-IV only has 4 instructions that a program can contain. A program is just a 1-dimensional line of wood blocks. The only valid wood blocks are Acacia, Birch, Cherry, and Dark Oak. From here on out, we will just refer to these blocks by their first letters: A, B, C, and D.

RSC-IV has only four components.

1. A line of blocks for the input program.
2. A line of blocks for the output string. The output string consists of the same 4 wood blocks we use for the input program.
3. An instruction pointer that starts at the beginning of the program and determines the next block from the program to be interpreted.
4. A 2-bit (4-value) register that starts at the value 0.

Each block in the program is one instruction that either acts on the register, the instruction pointer, or the output. Here are the effects of the 4 program blocks:

There are three caveats to note:

• The value in the register can overflow. In this case, we still just keep the bottom 2 bits. You can think of this as $$$R = f(R)\text{ mod }4$$$ for every operation done to the register $$$R$$$.
• You may have noticed that we can do a C/JMP while our register holds the value 0. This is known as a "halt". To be a valid RSC-IV program, the program line must end with a halt – it is invalid for a program to halt before reaching the last block in the program line, and it is invalid for a program to never halt or have the instruction pointer go beyond the end of the program line.

One fun thing computer scientists like to do is make a "quine" – a program that outputs itself. We won't have you make a quine, but we'll ask for something similar. The challenge we have for you is the following: take a given output string $$$S$$$ and make a valid RSC-IV program $$$P$$$ with the following constraints:

• $$$P$$$ contains $$$S$$$ as a substring.
• Upon halting, $$$P$$$ must have produced exactly $$$S$$$ as the output string.

There are $$$N$$$ witch huts each with a witch in it. One of these witches is evil. You want to find which witch hut has the evil witch.

To do this, you assign other players to check these witch huts. You start with $$$K$$$ (an initial value you choose) players. You can assign each player to investigate any amount of witch huts. They all disperse and take $$$C$$$ time to check the assigned witch huts and come back to you at the same time.

When the players come back to you, they either have the "Bad Luck" effect on them if they checked the evil witch hut or they have "Good Luck" effect on them if they did NOT visit the evil witch hut. The players that checked the evil witch don't know which one of the witch huts they visited gave them the "Bad Luck" effect though (the "Bad Luck" effect is the only indicator). Additionally, because the players with the "Bad Luck" effect have bad luck, one of them is chosen at random and permanently dies, meaning they can't help with the witch hut checking anymore. If no players come back with the "Bad Luck" effect, no players die.

You want to find the evil witch within $$$T$$$ time, but not very many players are willing to help out. What's the minimum number of players $$$K$$$ you need to start with to guarantee finding the evil witch?

You have found $$$N$$$ villages that are all connected by $$$N - 1$$$ roads so that one can start at any village and visit any other village using these roads. However, the villagers in these villages don't want to be all connected because they think there are too many people competing over trading. So they ask for your help to break the villages up by removing roads.

Each road $$$i$$$ has a time $$$t_i$$$ that it takes to remove, but you only have $$$T$$$ time before your mom tells you to stop gaming. Therefore, the total time of the roads you remove must be at most $$$T$$$. Also, after removing roads, the villages are split into smaller communities where villages within a community can still visit each other using roads, but villages in different communities cannot visit each other anymore. To keep the villagers as happy as possible, you want to minimize the number of villages in the largest community. Help the villagers out as much as possible using your limited gaming time and find the minimum number of villages in the largest community!

You want to create a zombie farm. Luckily you've recently stumbled upon a zombie spawner. However, you can't break the spawner to move it elsewhere, so the farm needs to be built around it. Additionally, to trap the zombies in, you need to build a fence around the spawner.

However, due to the new update, the farm requires a very specific type of fence. The fence needs to be a non-degenerate triangle with vertices at 3 of $$$N$$$ pre-determined fence posts, located on a 2d grid. If needed, the spawner can lie directly on the fence.

To give the mobs more space to spawn (maximizing profits), you want to make the area enclosed by the fence as large as possible. What is the largest possible area that such a fence can enclose, if one exists?