With Valentine's Day just around the corner, Sophie is ready to release her new dating app, Cinder. She assigns you the job of writing the program to generate usernames for each new person who registers for the app based on their given name. Sophie is very particular about her app so she asks for the following scheme for the usernames:
Each time a user registers, the system is sent a request with their name (call this string $$$s$$$). If $$$s$$$ is not yet in the database, it is inserted into the database and the user gets the response OK to signify that they were able to register. If $$$s$$$ is already in the database, the system will create a new string $$$s'$$$ and insert $$$s'$$$ into the database before returning $$$s'$$$ back to the user as their new username. The string $$$s'$$$ is formed by adding a number to the end of $$$s$$$ (so $$$s$$$, $$$s1$$$, $$$s2$$$, $$$s3$$$ ...) where each time the number $$$i$$$ appended is the smallest positive integer such that $$$s'$$$ = $$$s$$$ + $$$i$$$ is not already in the system.
Given $$$n$$$ users, implement a program that will return the right username for each person (or OK if the name wasn't in the system already).
The first line will contain a single integer $$$n$$$ (where $$$1 \leq n \leq 10^{5}$$$) representing the number of new users (aka incoming requests),
The following $$$n$$$ lines will each contain a request (name of the new user) in the order the system gets the requests. Each request is a non-empty string consisting of only lowercase letters and will not be longer than $$$32$$$ characters.
For each of the $$$n$$$ request lines, print the system response (so OK if the name wasn't in the database already or the new username if it was already there).
4 marta mia mia alexia
OK OK mia1 OK
6 weston mohamed gabriel weston mohamed gabriel
OK OK OK weston1 mohamed1 gabriel1
Sadio has set up a grand night for Valentine's day. After dinner and dessert, he plans to take his significant other to the top of the tallest building in the city and use the lens he set up there to show his significant other the $$$n$$$ places around the city where they had memorable moments (date spots, favorite restaurants, etc).
Sadio goes to test the lens out before the big night and realizes that moving and refocusing the lens takes way too much time. To fix this, he decides to buy a new lens that captures enough of an angle in order to see all $$$n$$$ places at the same time. The cost of the lens increases linearly with the angle that it captures (so a lens that captures $$$90$$$ degrees would cost more than that which captures $$$89$$$ degrees). Note, when we say that the lens captures x degrees, it is equivalent to having two rays from the origin which make an angle of x degrees, and all the points on/within the two rays are seen.
The city can be represented as a grid where the tallest building (so where Sadio and his partner will be) is at $$$(0, 0)$$$ and each of the $$$n$$$ special points is located at integer coordinates $$$(x, y)$$$. Given that Sadio has already spent so much money planning tonight, he wants to spend as little as possible on the new lens. What is the minimum angle such that the lens with that angle can view all $$$n$$$ locations? The lens can view a location even if that location is on the very border of what the lens can see.
The first line contains a single integer $$$n$$$ (where $$$1 \leq n \leq 10^{5}$$$) which represents the number of special places.
The next $$$n$$$ lines each contain two space-separated integers $$$x_{i}$$$ and $$$y_i$$$ which represent the coordinates of the $$$i$$$th special place ($$$-1000 \leq x_i, y_i \leq 1000$$$).
It is guaranteed that no two special places are at the same point and there is no special place at $$$(0, 0)$$$.
A single decimal which equals the minimum angle, in degrees, such that all $$$n$$$ points are contained. The answer will be considered valid if the relative or absolute error doesn't exceed $$$10^{-6}$$$.
2 3 0 0 3
90.0000000000
3 -3 0 0 3 -3 -3
135.0000000000
admin'OR1=1 is tired of celebrating Singles Awareness Day – not once have they ever had success with dating! This year, things are going to be different. admin'OR1=1 is going to change their name!
The reason is simple: admin'OR1=1 is simply not a name that is compatible with many other names. And as we all know, name compatibility is the key to successful relationships. The compatibility score $$$t$$$ of two names, $$$s_1$$$ and $$$s_2$$$ is defined as the sum of minimum occurrences of each letter. In other words, $$$$$$t = \sum_{a \in A} min(c_{s_1,a}, c_{s_2,a})$$$$$$ where $$$A$$$ denotes the set of letters, and $$$c_{s,a}$$$ denotes the number of times $$$a$$$ appears in $$$s$$$.
admin'OR1=1 has already compiled the names of $$$n$$$ people they plan on asking out (after the name change). In order to maximize their chances, admin'OR1=1 wants to maximize the total sum of compatability scores between their new name and all of the $$$n$$$ names. However, due to governmental restrictions, their new name can only be $$$m$$$ characters long. Can you help admin'OR1=1 pick a new name?
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 1000$$$), representing the number of names and the maximum length of admin'OR1=1's new name.
Then, $$$n$$$ lines follow, where the $$$i$$$-th line contains $$$s_i$$$, the name of the $$$i$$$-th person. Names will only consist of lowercase Latin letters.
The sum of lengths of all $$$s_i$$$ will be no more than $$$1000$$$.
Output a string consisting only of lowercase Latin characters of length at most $$$m$$$, which maximizes the sum of compatibility scores with all given names.
If there are multiple names that maximize the compatibility, output any of them.
3 5 alice bob charlie
alice
3 3 umar winston lulu
uwu
In preparation for Valentine's Day, Yaroslav is searching for the perfect date. He has decided to take his partner Rostislav hiking to the top of a local mountain to view the sunset.
The hiking area is described as a $$$N \times N$$$ grid of height values $$$h_{i,j}$$$ and the two will be starting at $$$(0, 0)$$$, traveling to the peak (maximal height) within the area.
Yaroslav wants to minimize the total energy expended during their hike, instead preferring to stare into Rostislav's dreamy eyes. Ascending or descending by $$$d$$$ costs $$$d^2$$$ energy. Since they are still novice hikers, they can only travel between grid cells that share a side.
Given the height grid of the surrounding land, help Yaroslav find the easiest hike and make their sunset date perfect.
The first line contains a single integer $$$1 \leq N \leq 500$$$
The $$$i+1$$$th line contain $$$N$$$ integers $$$1 \leq h_{i,j} \leq 1000$$$
A single integer, denoting the minimum energy spent to climb to the peak.
3 1 2 4 4 5 6 4 8 7
11
There will be a unique peak.
As Valentine's Day approaches, Harmony wants to get a gift for her sweetheart. Specifically, she has in mind to buy a brilliant ruby gemstone, representing her heart. When she goes to look at different rubies at the jewelry store, Harmony sees that each one is cut uniquely with a different number and arrangement of facets. In fact, each stone can be represented as a binary tree that has been reflected and connected with edges across the leaves, producing a symmetrical pattern of connected facets.
In order to select the best ruby out of the available stones, Harmony comes up with a metric for the quality of a ruby. A ruby's radiance is equal to the number of unique cycles which can be found within its facet pattern. Write a program to help Harmony evaluate radiance and select the finest ruby!
The first line of input contains an integer $$$V$$$ ($$$2 \leq V \leq 10^6$$$) denoting the number of vertices in the binary tree representing a ruby's facet pattern. $$$V - 1$$$ lines follow, each containing two space-separated integers $$$u$$$ and $$$v$$$ which represent endpoints for an edge in the tree (in general, any tree with $$$n$$$ vertices has exactly $$$n - 1$$$ edges). You are also given that $$$u$$$ is a parent of $$$v$$$ in the tree, and the tree will always be rooted at the first vertex $$$1$$$.
Print the number of unique cycles which can be found in the graph generated by connecting each leaf vertex in the binary tree to its equivalent in a reflected copy of the tree.
11 1 9 5 3 2 7 1 5 9 2 8 10 2 8 5 4 3 6 3 11
10
Carmen ended up falling asleep in the GDC the entire weekend, leaving her barely any time to shop for a Valentine's Day gift! Although she doesn't want to disappoint her significant other with a basic gift, she is really craving some chocolate to energize herself after a long nap. Carmen decides to order a jar of M&Ms, each one with a unique personalized design etched upon its surface (the idea being to say "awwww" then "ahhhh" as you consume them). Her plan for the date itself is then to play the following game in front of (yes not with) her significant other involving the M&Ms:
All of the M&Ms will initially be arranged in a single pile. While a pile still exists with at least two candies, Carmen picks one such pile to divide into two non-empty piles by choosing any nonempty subset of M&Ms to form a new pile. Given that Carmen has purchased $$$n$$$ M&Ms, she wonders how many possible different "games" she can play. Two piles of candies are considered the same if they contain the same set of candies. Two games are considered equal if Carmen makes the same sequence of choices and divides the piles in the same way.
The first and only line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$), indicating the number of M&Ms in the jar Carmen bought.
A single integer representing the number of possible games Carmen can play with her significant other modulo $$$10^9+7$$$ (the prime that signifies love of programming contests and UTPC).
3
3
4
18
For the first sample case, $$$N = 3$$$. Let the unique candies be designated by ABC. The $$$3$$$ possible games are decided by the very first move deciding what candy to isolate in its own pile (e.g. split into AB/C, AC/B, or BC/A).
For the second sample case, $$$N = 4$$$. Let the unique candies be designated by ABCD.
1: splitting into two piles AB and CD, dividing CD into C and D, and dividing AB into A and B
2: splitting into two piles AB and CD, dividing AB into A and B, and dividing CD into C and D
3: splitting into two piles ABD and C, dividing ABD into AD and B, and dividing AD into A and D
Action sequences 1, 2, and 3 are all considered unique games Carmen can play. 1 and 2 are different because the order of dividing up the smaller piles is switched. 1 and 2 are different from 3 because the first action divides the initial pile into different piles.
It's Valentine's Day, and Rufus is late to his dinner date! Even worse, he forgot to buy a present for his girlfriend.
There are $$$n$$$ intersections in the city, and $$$m$$$ two-way roads connecting the intersections. Rufus is currently at intersection 1. His dinner date is at intersection $$$n$$$.
Whenever Rufus travels along the $$$i$$$th road (between intersections), he visits a store and buys a present for his date with cost $$$w_i$$$. The total cost of his presents is the product of the cost of the presents he buys. He knows his girlfriend loves the number $$$10^k$$$ and will only accept presents if their total cost is divisible by $$$10^k$$$. If Rufus desires, he can revisit the road and purchase the gift another time.
However, Rufus is also very frugal, so he wants the total cost to be as small as possible. Help him find the lowest total cost of all paths from his location to his dinner date where the cost is divisible by $$$10^k$$$.
Since this number, $$$cost$$$, can be very large, output $$$\log_{10}(cost)$$$. If no path exists that satisfies the constraints, output $$$-1$$$. Your answer will be judged as correct if it is within $$$10^{-6}$$$ of the true answer.
The first line contains $$$n$$$, $$$m$$$, and $$$k$$$ where $$$n$$$ is the number of intersections, $$$m$$$ is the number of roads connecting the intersections, and $$$10^k$$$ is the number Rufus' girlfriend loves. $$$(1 \leq n \leq 10^3, 1 \leq m \leq 10^4, 1 \le k \le 10)$$$
The next $$$m$$$ lines contain 3 values $$$u_i, v_i, $$$ and $$$ w_i$$$ where the intersections $$$u_i$$$ and $$$v_i$$$ are connected by a road, and $$$w_i$$$ is the cost of the present on that road. $$$(1 \le u_i, v_i \le n, 1 \le w_i \le 100)$$$
Output $$$\log_{10} (cost)$$$, where $$$cost$$$ is the lowest total cost of all paths from intersection 1 to intersection $$$n$$$, such that $$$cost$$$ is divisible by $$$10^k$$$. If no such path exists, output $$$-1$$$. Your answer will be judged as correct if it is within $$$10^{-6}$$$ of the true answer.
4 4 1 1 2 1 2 3 2 3 4 3 3 4 5
1.0000000000
4 3 1 1 2 1 2 3 2 3 4 3
-1
In the first test case, Rufus wants to purchase gifts at the first, second, and fourth roads, resulting in a total cost of $$$10$$$, and $$$\log_{10}(10) = 1$$$.
In the second test case, there is no way to get from $$$1$$$ to $$$n$$$ and have a total cost divisible by $$$10$$$.
In the spirit of treating yourself for Satisfied Staying Single Day (February 11th), you decide to make a reservation at Uchi... for just yourself. However, you made the mistake of booking a seat at the Miami restaurant instead of at the Austin location! The fortunate opening of a straight (undersea) train route from Austin to Miami gives you the chance to still make it in time to your dinner. There are $$$N-1$$$ cities along this railway labeled with consecutive integers $$$2$$$ to $$$N$$$ in order of increasing distance from Austin; Austin is labeled as city $$$1$$$ and Miami is labeled as city $$$N+1$$$. The cities are connected by $$$N$$$ segments of railroad, with the $$$i$$$-th segment connecting cities $$$i$$$ and $$$i+1$$$. Every segment of the railroad has periodic maintenance every $$$a_i$$$ units of time.
In order to get from city $$$x$$$ to $$$y$$$ (where $$$x \lt y$$$, this railway is unidirectional towards Miami/city $$$N+1$$$), train drivers follow a set of rules based on $$$x$$$ and the current time $$$t$$$ until they arrive in city $$$y$$$.
To pass the time while traveling, you decide to compute the number of units of time it would take for the ride from city $$$x$$$ to city $$$y$$$ after starting at time $$$t$$$, and how it would hypothetically change if the maintenance frequencies were modified.
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of railway segments that connect the $$$N+1$$$ cities. The second line of input contains $$$N$$$ space separated integers $$$a_i$$$ ($$$2 \leq a_i \leq 5$$$), denoting the initial maintenance frequencies on segments $$$i$$$. The third line of input contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), representing the number of queries that will be made. The next $$$Q$$$ lines are either of the format "1 x y t" or "2 s b". For the latter type, hypothetical changes are made to the maintenance frequency of rail segment $$$s$$$ ($$$1 \leq s \leq N$$$) by setting $$$a_i = b$$$ ($$$2 \leq b \leq 5$$$). These changes are persisted for following queries. For the former type, you must output the number of units of time it would take for the ride from city $$$x$$$ to city $$$y$$$ ($$$1 \leq x \lt y \leq N+1$$$) after starting at time $$$t$$$ (calculations assume values of $$$a_i$$$ are either the initial ones given or the last $$$b$$$ value in queries of type $$$2$$$ where $$$i = s$$$). The initial $$$t$$$ is a nonnegative integer at most $$$10^5$$$ in every query.
For each query of the first type output a single integer - the hypothetical number of time units spent traveling by train from city $$$x$$$ to city $$$y$$$ assuming all queries are made in the order they are given.
8 2 5 3 2 3 5 3 4 10 2 8 3 1 2 6 0 1 1 3 0 2 3 4 1 3 9 0 1 4 6 0 1 5 6 0 2 7 3 1 7 8 0 1 2 5 0
5 3 9 3 2 2 4