First Masters Championship LATAM 2024
A. Apartment Tycoon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the bustling metropolis of Econopolis, where the skyline is ever-changing and the economy thrives on savvy investments, a young entrepreneur embarks on a journey to become a real estate mogul. Gifted with a single apartment by a mysterious benefactor, this aspiring tycoon sees an opportunity to expand their empire. The strategy is simple yet ambitious: use the rental income from the apartment to acquire more, each becoming a new source of revenue. The goal? To amass a portfolio of $$$C$$$ apartments, transforming the initial gift into a sprawling empire. The journey from a single property to a real estate dynasty will require cunning, patience, and a keen eye for opportunity.

Given that you start with one apartment generating $$$B$$$ dollars per month and can purchase additional apartments for $$$A$$$ dollars each, which also start generating $$$B$$$ dollars per month once acquired, your task is to calculate how many months it will take to own $$$C$$$ apartments. Each month, you can use the income generated to buy more apartments, accelerating your journey toward becoming an apartment tycoon.

Input

The input consists of a single line containing three integers, $$$A$$$, $$$B$$$, and $$$C$$$ ($$$1 \leq A, B, C \leq 1000$$$), representing the cost of an apartment, the monthly income from each apartment, and the target number of apartments, respectively.

Output

Print a single integer, the number of months required to own $$$C$$$ apartments.

Examples
Input
5 1 2
Output
5
Input
10 5 3
Output
3

B. Balindromes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the realm of Numeralia, a fascination with symmetry and balance pervades the culture, especially when it comes to numbers. The Numeralians hold a particular reverence for palindrome numbers, those unique numbers that read the same backward as forward, such as 323 and 111. A challenge has been set forth to the mathematicians of Numeralia: for given ranges, determine how many palindrome numbers exist between two boundaries, inclusive. This task, known as the Palindrome Count Query, tests both the mathematicians' understanding of number properties and their ability to navigate through vast numerical spaces efficiently.

Input

The first line of the input specifies $$$Q$$$ ($$$1 \leq Q \leq 10^4$$$), the number of queries. Each of the following $$$Q$$$ lines contains two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq 10^{18}$$$), representing the lower and upper bounds of the range for that query.

Output

For each query, output a single line containing the number of palindrome numbers that lie within the range $$$[L, R]$$$, inclusive.

Examples
Input
1
1 100
Output
18
Input
1
23 55
Output
3

C. Counting Relative Lists
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a task to count how many lists of $$$N$$$ positive integer numbers, each less than or equal to $$$M$$$, can be formed such that adjacent numbers in the list are relatively prime. Two numbers are relatively prime if their greatest common divisor (GCD) is 1. This problem combines number theory with combinatorial counting, challenging you to explore the intricacies of prime relationships between numbers within a constrained set.

Input

Input consists of a single line containing two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^8$$$) ($$$1 \leq M \leq 100$$$), representing the length of the lists and the maximum possible value of each element in the lists, respectively.

Output

Output a single integer, the total number of lists that can be formed under the given conditions, because the number can be very large print it modulo $$$10^9 + 7$$$.

Examples
Input
2 3
Output
7
Input
2 10
Output
63

D. Dynamic Park Pricing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the bustling city of Metropoville, the demand for parking spaces is as dynamic as its ever-moving traffic. To manage this demand efficiently, the city has introduced a new parking payment system in its central parking structure, known as "Dynamic Park". Unlike traditional parking lots, Dynamic Park utilizes a tiered payment system that adjusts the cost based on the duration of parking, aiming to optimize space usage and provide fair charges for its patrons.

You've spent a day in Metropoville and now need to pay for your parking at Dynamic Park. The parking structure operates on a tiered charging system where the cost per minute changes after certain time thresholds. Given the total time you've parked, expressed in hours and minutes (for example, 19 hours and 38 minutes), calculate the total parking fee based on the tiered rates provided.

Input

The first line contains two integers $$$H$$$ and $$$M$$$ ($$$0 \leq H \lt 24$$$, $$$0 \leq M \lt 60$$$), representing the number of hours and minutes you've parked, respectively.

The second line contains an integer $$$N$$$ ($$$1 \leq N \leq 10$$$), the number of different time tiers.

Each of the next $$$N$$$ lines describes a tier with two integers $$$X_i$$$ and $$$Y_i$$$ ($$$1 \leq X_i \leq 1440$$$, $$$1 \leq Y_i \leq 100$$$). $$$X_i$$$ represents the duration of the tier in minutes, and $$$Y_i$$$ is the cost per minute in that tier.

Output

Output a single integer, the total cost of parking. If the parking duration exceeds the specified tiers, calculate the cost up to the last tier for the remaining time.

Examples
Input
1 10
2
60 1
20 100
Output
1060
Input
23 59
2
10 10
20 20
Output
500

E. Enchanted Labyrinth
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Deep within the verdant embrace of an ancient, whispering forest lies a marvel of arcane construction: the Enchanted Labyrinth. Conceived by the archmages of a forgotten era, this labyrinth guards the legendary Crystal of Aeternum, a gem of untold power. While many have braved the labyrinth's convoluted corridors in search of glory, only the echoes of their valor remain, a testament to the maze's perilous nature. The labyrinth is a network of $$$N$$$ mystic chambers, linked by $$$M$$$ pathways of uniform length, with only $$$K$$$ chambers harboring portals that lead back to the realm of men.

Elisa, a daring explorer driven by tales of the ancient relic, finds herself ensnared within the labyrinth's spellbound walls. From the initial chamber labeled $$$1$$$, she must navigate through the maze to reach a portal that promises freedom. However, the labyrinth is not without its sentinel – a cunning Minotaur, tasked with thwarting the escape of intruders by manipulating the very fabric of the maze.

The Minotaur, bound to the magic of the labyrinth, has the power to seal any one pathway leading from the chamber in which Elisa currently resides, effectively blocking her passage through that route. However, its power is limited to the chamber's confines at Elisa's location, and once she embarks upon an unsealed pathway, the beast cannot obstruct her until she arrives at the subsequent chamber. In this deadly game of wits and wills, your challenge is to determine the shortest path that Elisa can take to ensure her escape or to despairingly conclude that the Minotaur's guile renders escape impossible, in which case, return $$$-1$$$.

Input

The first line contains three integers, $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \leq N \leq 10^6$$$, $$$1 \leq M \leq 2 \times 10^6$$$, $$$1 \leq K \leq N$$$), the number of chambers, the number of pathways, and the number of escape portals, respectively.

The next $$$M$$$ lines each describe a pathway with two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq N$$$), indicating a bidirectional path between chambers $$$a$$$ and $$$b$$$.

The last line enumerates $$$K$$$ distinct integers, the indices of chambers containing escape portals.

Output

Output the minimum distance Elisa must traverse to ensure her escape. If the Minotaur's machinations make escape an impossibility, print $$$-1$$$.

Examples
Input
5 7 2
1 2
1 3
2 3
2 4
3 4
4 5
3 5
3 5
Output
3
Input
5 7 1
1 2
1 3
2 3
2 4
3 4
4 5
3 5
5
Output
-1
Input
5 7 3
1 2
1 3
2 3
2 4
3 4
4 5
3 5
3 4 5
Output
2

F. Friends Reunion at the Park
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the heart of the enchanting town of Graphville lies Vertex Park, an expanse of lush landscapes intertwined with a complex network of pathways. This park, renowned for its verdant groves and serene ambiance, serves as a cherished rendezvous for three inseparable friends: Alice, Bob, and Carol. Unlike the typical parks, Vertex Park boasts a unique design resembling a tree structure, with pathways ensuring direct and loop-free connections between its various junctions.

One sunny afternoon, inspired by the interconnectedness of the park, the trio conceives a playful challenge: starting from different locations within the park, they aim to ascertain the minimal steps necessary for a joint gathering at a single junction. This venture seeks not just to test their understanding of the park's layout but to maximize their time together amidst nature's bounty. Given the uniform length of the pathways and the strategic starting points of Alice, Bob, and Carol, your task is to calculate the fewest steps required for their reunion, thereby facilitating an extended companionship in their verdant haven.

Input

The narrative unfolds with an integer $$$N$$$ ($$$3 \leq N \leq 2*10^5$$$), symbolizing the number of junctions adorning Vertex Park. Subsequently, $$$N-1$$$ lines follow, each bearing two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$, $$$u \neq v$$$), delineating a pathway linking junctions $$$u$$$ and $$$v$$$. A new chapter begins with an integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), indicating the number of queries or challenges proposed by the friends. Each query is articulated through a line comprising three distinct integers $$$A$$$, $$$B$$$, and $$$C$$$ ($$$1 \leq A, B, C \leq N$$$), representing the initial positions of Alice, Bob, and Carol within the park's expanse.

Output

For every query, a single integer is to be revealed, symbolizing the minimal number of steps the trio must embark upon to achieve their reunion at a singular junction. This figure not only embodies the solution to their playful challenge but also epitomizes the essence of their friendship, intertwined within the labyrinthine paths of Vertex Park.

Example
Input
6
1 3
2 5
3 4
3 5
5 6
2
1 4 6
3 2 6
Output
2
1

G. Gridtopia
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the realm of Gridtopia, adventurers find themselves facing a sprawling $$$N \times M$$$ grid. Starting from the upper left corner, their goal is to traverse to the lower right corner, collecting scattered magical artifacts along the way. However, Gridtopia has a peculiar rule: movement is restricted to only rightward or downward steps. Furthermore, each cell of the grid may contain at most one artifact. Given the adventurers are faced with the challenge of planning the minimum number of trips required to ensure all artifacts are collected and no treasure is left unclaimed in their quest across Gridtopia.

Input

The adventure begins with an input of two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 50$$$), representing the grid's dimensions. Following this, $$$N$$$ lines are provided, each containing $$$M$$$ integers. These integers are either $$$0$$$ or $$$1$$$, where $$$0$$$ signifies an empty cell and $$$1$$$ indicates a cell containing an artifact. The task is to navigate this grid, adhering to the movement restrictions, and determine the optimal path to collect all artifacts.

Output

Reveal in a single integer the minimum number of trips required to collect all artifacts from the grid, ensuring that each trip starts at the grid's upper left corner and concludes at the lower right corner. This number represents the adventurer's efficiency and strategic planning in overcoming the unique challenges of Gridtopia.

Examples
Input
2 2
0 1
1 0
Output
2
Input
3 3
1 0 0
0 1 1
1 1 0
Output
2
Input
5 5
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0
Output
5

H. Hidden Textland Pattern
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the digital expanse of Textland, a land renowned for its affinity with strings and textual puzzles, a challenge has arisen that has piqued the curiosity of its inhabitants. The challenge involves a mystical string, said to hold secrets to the ancient algorithms of Textland. This string, composed of lowercase letters, is rumored to contain hidden patterns that repeat throughout its length. The quest is to uncover the most repeated substring within this enigmatic string. However, the challenge comes with a twist: if multiple substrings are equally repeated, the quest seeks the longest among them. Should a tie still persist, the preference shifts to the substring that is smallest lexicographically. The citizens of Textland are intrigued, for deciphering this puzzle would mean unlocking a piece of the lost lore of their digital realm.

Input

The adventure begins with two lines. The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the length of the mystical string $$$S$$$. The second line contains the string $$$S$$$, composed of lowercase English letters. This string, a relic from the ancient coders of Textland, is the key to the challenge.

Output

Reveal the most repeated substring according to the rules of the challenge. If the string is a unique sequence of characters with no repetitions, return the entire string itself as it stands as the only substring of its kind.

Examples
Input
3
acb
Output
acb
Input
8
abdabdab
Output
ab

I. Inspecting Spells
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the mystical realm of Lexicovia, a land where magic weaves through words and letters with the power to manifest the deepest desires, a group of friends skilled in the art of Spellcraft gather. These friends, known throughout the land for their wisdom and camaraderie, possess a unique collection of enchanted words—each a spell in its own right. As the annual Festival of the Arcane Words approaches, they embark on a quest to combine their spells in a way that summons a specific magical effect, encapsulated in a secret word known only to them. This year, the word they seek to manifest is a symbol of their enduring bond, a testament to the magic of friendship that has kept them united through every trial.

Your task is to assist this circle of friends in determining whether they can arrange their collection of enchanted words in such a manner that, when combined without altering the sequence of letters within each word, they can create a magical phrase that contains a specific secret word $$$S$$$ as a substring. The magical essence of their spells allows for the words to be reordered but forbids any alteration to the letters within each word, preserving the spell's integrity.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^3$$$), the number of enchanted words in the friends' collection.

Each of the next $$$N$$$ lines contains a string representing an enchanted word. Each word consists of lowercase English letters, and the total length of all words combined will not exceed $$$10^6$$$.

The following line presents the secret word $$$S$$$, a string of lowercase English, the length of the word will not exceed 1000 characters.

Output

Print "YES" if the friends can arrange their enchanted words in such a manner that the resulting magical phrase contains the secret word $$$S$$$ as a substring. Otherwise, print "NO".

Examples
Input
2
aho
la
holala
Output
YES
Input
4
la
tam
mas
ter
tamas
Output
NO