In an ancient realm, a talented alchemist named Alaric was on a quest to unlock the secrets of immortality. Over time, Alaric stumbled upon an enigma that even challenged his supernatural abilities.
Alaric discovered an ancient parchment describing a set of magical numbers that were pivotal in creating the elixir of immortality. These numbers were arranged in an array, and to unleash the power of the potion, the array had to become a "magic palindrome."
An array is a "magic palindrome" if it is symmetric and reads the same from left to right and from top to bottom. To transform an array into a magic palindrome, Alaric could perform the following operation: take two adjacent numbers in the array and replace them with their sum.
Help Alaric find the minimum number of operations he needs to perform to turn the array of numbers into a "magic palindrome" and unlock the power of the elixir of immortality.
The first line contains an integer $$$N$$$ $$$(1 \leq N \leq 10^6)$$$, the number of elements in the array. The second line contains $$$N$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_N$$$ $$$(1 \leq a_i \leq 10^6)$$$, representing the elements of the array.
An integer, representing the minimum number of operations required to transform the array into a palindrome.
51 2 3 5 1
1
31 10 100
2
22 2
0
An array is a palindrome if it remains the same when its elements are viewed in reverse order. For example:
[1, 2, 1] is a palindrome.
[100] is a palindrome.
[13, 41, 14, 31] is not a palindrome.
In the ancient land of sequential numbers, the renowned Fibonacci family, led by the iconic Fibonacci, reigned supreme for generations. However, in a darker corner of this land, Fibonacci's cousin, Bionaccia, created her own mathematical sequence in an attempt to emulate her famous relative's success. Although Bionaccia's sequence was impressive in its own right, it was overshadowed by Fibonacci's fame.
This unfortunate eclipse prompted Bionaccia to retire and resign from the competition. But her withdrawal did not go unnoticed, and Trinacci, a darker member of the family, felt that Bionaccia had been unjustly victimized. He decided to embark on a vengeful mission. Trinacci not only plans to surpass Fibonacci but also avenge his sister Bionaccia by creating his own sequence, larger and more powerful than Fibonacci's.
The Trinacci sequence is defined as follows:
$$$t(0) = 1$$$
$$$t(1) = 2$$$
$$$t(2) = 3$$$
$$$t(n) = 3t(n - 1) + 2t(n - 2) + t(n - 3) + 3$$$ for $$$n \geq 3$$$
Trinacci and Bionaccia are interested in the value of the $$$K$$$-th term in the Trinacci sequence, i.e., $$$t(K)$$$. They want to know if Trinacci's sequence can surpass the fame of Fibonacci. However, $$$K$$$ is an extremely large number, not less than 1 nor greater than $$$10^{16}$$$.
Your task is to write a program that, given the position $$$K$$$, calculates the value of $$$t(K)$$$ in the Trinacci sequence, and the result should be taken modulo $$$10^9 + 7$$$.
An integer $$$K$$$ ($$$1 \leq K \leq 10^{16}$$$).
An integer: the value of $$$t(K)$$$ in the Trinacci sequence taken modulo $$$10^9 + 7$$$.
6
822
7
2983
10
142401
You are tasked with decorating a wall that consists of $$$N$$$ levels. The decoration should take the shape of a triangle, where each level $$$i$$$ of the triangle contains $$$i$$$ stickers of a certain color.
There are three available colors for the stickers: Red (R), Green (G), and Blue (B). You have a limited supply of stickers for each color: $$$R_i$$$ Red stickers, $$$G_i$$$ Green stickers, and $$$B_i$$$ Blue stickers. A well-decorated wall is defined as follows:
In each level, all stickers must be of the same color. If more than one color is used on a level, each color should appear the same number of times on that level. Your task is to calculate the number of different ways you can decorate the wall while adhering to these well-decorated criteria.
The first line contains an integer $$$N$$$ $$$(1 \leq N \leq 20)$$$, representing the number of levels on the wall.
The second line contains three integers $$$R_i$$$, $$$G_i$$$, and $$$B_i$$$ $$$(0 \leq R_i, G_i, B_i \leq 100)$$$, representing the number of Red, Green, and Blue stickers available, respectively.
A single integer, the number of different ways to decorate the wall while satisfying the well-decorated criteria. Since the answer may be large, output the result modulo $$$10^9 + 7$$$.
3 1 2 3
21
Given an array of integers, your task is to find the largest pool. In this context, a pool is a contiguous subarray $$$(l, r)$$$ such that the minimum between indices $$$l$$$ and $$$r$$$ is greater than all elements within the subarray $$$(l, r)$$$.
The area of the pool is calculated assuming it's filled with water, where $$$L$$$ and $$$R$$$ are the pool's ends, and the pool's height is equal to the value of the minimum between $$$L$$$ and $$$R$$$. However, the area of the pool is affected by the numbers in the middle of the subarray. As you move from the ends toward the center of the subarray, the value of the minimum decreases, reducing the pool's area. Additionally, any excess water beyond the pool's edges spills over.
Write a program to find the largest pool in the array and determine its area, considering the decrease in area as you approach the center of the subarray and the spillover of water beyond the edges.
Example of a pool. The first line contains an integer $$$N$$$ $$$(1 \leq N \leq 10^6)$$$, the length of the array.
The second line contains $$$N$$$ integers separated by spaces, representing the array of integers $$$A$$$ $$$(1 \leq A_i \leq 10^6)$$$.
An integer, the area of the largest pool in the array, taking into account spillover. If no pool is found, the output should be 0.
410 2 3 8
11
51 4 10 4 1
0
95 1 2 1 5 1 2 1 5
11
You want to travel from city S to city T within your country. You have a list of available flights to choose from, and for each flight, you know the origin, destination, and the cost of the flight. However, these flights are not bidirectional, meaning that you can only use them to travel from one city to another, but not the other way around.
In each city you visit during your journey, you have the opportunity to close a deal and earn a profit. For each city i you visit, you can earn a profit of $$$P_i$$$ dollars and this deal can be done each time you visit a city. However, you must decide which cities to visit and which flights to take to maximize your profit.
Your objective is to reach city T with the maximum amount of money possible. To achieve this, you need to plan your journey carefully, taking into account the cost of flights and the potential profits in each city.
The first line contains four integers, $$$N$$$, $$$M$$$, $$$S$$$, and $$$T$$$ ($$$2 \leq N \leq 100, 1 \leq M \leq 10000, 1 \leq S, T \leq N$$$), where $$$N$$$ represents the number of cities in the country, $$$M$$$ represents the number of available flights, $$$S$$$ represents the city where your journey starts, and $$$T$$$ represents the city where you want to arrive.
The next $$$M$$$ lines each describe a flight with three integers: $$$U$$$, $$$V$$$, and $$$C$$$ ($$$1 \leq U, V \leq N$$$, $$$1 \leq C \leq 10^6$$$), where $$$U$$$ is the origin city of the flight, $$$V$$$ is the destination city, and $$$C$$$ is the cost of the flight.
The next line contains $$$N$$$ integers $$$P_1, P_2, \ldots, P_N$$$ ($$$0 \leq P_i \leq 10^6$$$), where $$$P_i$$$ represents the profit you can earn by closing a deal in city i.
An integer, the maximum profit you can earn when traveling from city S to city T. If it is impossible to reach city T from city S, output "Bad trip" and if you can earn infinite money with trading print "Money hack!".
5 5 1 51 2 102 3 93 4 94 2 94 5 1210 10 10 10 10
Money hack!
5 5 1 51 2 102 3 93 4 94 2 94 5 125 5 5 5 5
-20
5 5 1 51 2 102 3 93 4 94 2 204 5 510 10 10 10 10
7
Legendary Huron is in charge of building the floral garden in Huron Park, the new public park in Huronland. The floral garden can be represented as a matrix of flowers consisting of $$$n$$$ rows and $$$m$$$ columns, where the flower at the intersection of the $$$i$$$-th row and the $$$j$$$-th column has beauty $$$a_{i,j}$$$.
The government of Huronland will take a photo of the floral garden to promote tourism in Huron Park. The photo will consist of a submatrix of the floral garden. In other words, the flowers that are located between the rows $$$x_1$$$ and $$$x_2$$$ and between the columns $$$y_1$$$ and $$$y_2$$$, for some $$$1 \leq x_1 \leq x_2 \leq n$$$ and $$$1 \leq y_1 \leq y_2 \leq m$$$, will appear in the photo.
Legendary Huron defines the beauty of a photo to be the product of the sum of the maximum beauty in every row of the photo and the sum of the maximum beauty in every column of the photo. More formally, let $$$r_i$$$ be the maximum beauty in the $$$i$$$-th row of the photo, and let $$$c_j$$$ be the maximum beauty in the $$$j$$$-th column of the photo. The beauty of the photo is defined as $$$(r_1 + r_2 + \dots + r_f)(c_1 + c_2 + \dots + c_g)$$$, where $$$f$$$ is the number of rows and $$$g$$$ is the number of columns.
It has not been decided which submatrix will be photo, but Legendary Huron wants to know the sum of all possible beauties. Help him find the sum of the beauty of all possible photos of the floral garden. Since the answer can be too large, print it modulo $$$998244353$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n,m \leq 1000)$$$ — the number of rows and columns in the floral garden.
The following $$$n$$$ lines contains the beauties of the flowers. The $$$(i+1)$$$-th line contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$|a_{i,j}| \leq 10^9$$$) — the beauty of the flowers in the $$$i$$$-th row.
Print the answer modulo $$$998244353$$$.
2 21 23 4
142
5 33 4 8-3 -4 -84 5 1-1 3 100 0 0
6293
Gojo Satoru, the strongest man alive, is fighting Sukuna in order to save humanity. Unfortunately, Gojo is losing the battle. The only option he has left to defeat Sukuna is to make a 'heavenly restriction' to gain more power.
Initially, Gojo produces one cursed energy unit every minute.
The 'heavenly restriction' allow him to do the following at the beginning of each minute:
Gojo can launch an attack, spending all the cursed energy units he has accumulated up to that point, denoted as N. Once Gojo spends these units, the rate at which he produces cursed energy units per minute becomes N. After Gojo decides to launch an attack, he must wait for M minutes before he can start producing cursed energy units again.
He can repeat this any number of times.
To defeat Sukuna, Gojo must land an attack of at least $$$S$$$ units of cursed energy.
The first line contains two numbers $$$S$$$ ($$$1$$$ $$$\leq$$$ $$$S$$$ $$$\leq$$$ $$$10^{12}$$$) and $$$M$$$ ($$$0$$$ $$$\leq$$$ $$$M$$$ $$$\leq$$$ $$$10^{12}$$$)
The shortest time needed to defeat Sukuna.
10 4
10
9 0
6
Felix is an experienced systems administrator who takes information security in his network very seriously. Recently, he has set up a network of servers in his company, designed to be highly resilient to potential failures. To achieve this, Felix has connected every pair of servers in his network with high-speed connections.
Felix is aware that problems can occur at any time, and one or more connections might break due to failures or malicious attacks. However, he's particularly concerned about the possibility of exactly one connection failing.
To ensure that even if exactly one connection fails, there can still be uninterrupted communication between all servers in the network, Felix needs to know how many new connections he should add to the network at a minimum. Is possible that the initial network is not connected.
Your task is to help Felix calculate the minimum number of new connections he needs to add to his network to achieve his goal of high resilience in the event of exactly one connection failing.
An integer $$$N$$$ ($$$2 \leq N \leq 10^5$$$) representing the number of servers in the network. An integer $$$M$$$ ($$$1 \leq M \leq 10^5$$$) representing the current number of connections in the network. $$$M$$$ following lines, each containing two integers $$$A$$$ and $$$B$$$ ($$$1 \leq A, B \leq N$$$) indicating that servers $$$A$$$ and $$$B$$$ are currently connected.
An integer: the minimum number of new connections to be added to ensure connectivity in the event of exactly one connection failure.
5 41 22 33 44 5
1
3 31 22 33 1
0
4 11 2
3
In a bustling city, the prestigious ICPC Masters programming event was in full swing. Brilliant minds from around the world had gathered to showcase their algorithmic skills and problem-solving prowess. However, this year, something different was at stake.
A massive number of talented programmers had congregated, each with the determination to make their mark in the world of programming. What made this event special was that, unlike previous years, no one had come with a pre-formed team. Instead, they all arrived individually, eager to become part of a winning team.
The ICPC Masters' organization was ready for the challenge. They decided to form teams of exactly $$$K$$$ individuals, whenever possible. Participants, brimming with enthusiasm, clustered around tables in the competition hall, hoping to find like-minded peers with complementary interests and skills.
The organization realized that some participants, unable to form complete teams of $$$K$$$ individuals, might be left without the chance to compete. They wanted everyone to have the opportunity to prove their worth so they let them compete in a team with the remaining participants.
Write a program to help the ICPC Masters' organization determine the minimum number of participants in the team with the fewest members.
A single line with two integers, $$$N$$$ ($$$2 \leq N \leq 1000$$$) and $$$K$$$ ($$$1 \leq K \leq 10$$$), representing the number of participants at the event and the desired team size.
An integer, the number of participants in the team with the fewest members.
5 3
2
21 2
1
8 5
3