Diego, knowing that calculating $$$A+B$$$ is the easiest problem ever created, decided to give you a problem that is just a little bit harder.
You are given 3 positive integers, $$$A$$$, $$$B$$$ and $$$C$$$. Your task is to compute $$$\frac{A+B}{C}$$$.
In the first line, an integer, $$$T$$$ $$$(1 \le T \le 10^4)$$$, representing the amount of test cases.
Then, $$$T$$$ lines, each containing the 3 space-separated integers $$$A$$$, $$$B$$$, and $$$C$$$ $$$(1 \le A, B, C \lt 10^{50})$$$.
$$$T$$$ lines, each containing the requested value with exactly 50 digits after the decimal point.
If the value would has more than 50 decimals, the rest should be *truncated*.
3 1 3 2 10 25 5 99 89 17
2.00000000000000000000000000000000000000000000000000 7.00000000000000000000000000000000000000000000000000 11.05882352941176470588235294117647058823529411764705
Diego knows that the sum of all integers between $$$1$$$ and $$$N$$$ is $$$\frac{N(N+1)}{2}$$$. However, he is wondering how to compute the exclusive or of all integers between $$$1$$$ and $$$N$$$.
Exclusive or is also known as xor. Most programming languages represent it with the character ^.
First, a single integer, $$$T$$$ $$$(1 \le T \le 10^5)$$$: the number of test cases.
Then $$$T$$$ lines, each of which contains a single integer, $$$N$$$ $$$(1 \le N \le 10^{18})$$$.
For each test case output a line containing a single integer: the exclusive or of every number between $$$1$$$ and $$$N$$$.
3 1 2 5
1 3 1
Diego has a tree with exactly $$$N$$$ nodes, numbered from $$$1$$$ to $$$N$$$, where every edge is bidirectional and has an arbitrary number $$$X$$$ written on it.
Diego is wondering for every unordered pair or nodes (i,j) within the tree what is the sum of the exclusive ors between the path of nodes (i,j). For this problem a path between two nodes is a simple path (no cycles) and also the shortest path between said nodes.
Just to be clear, he wants to know: $$$\sum\limits_{i=1}^N \sum\limits_{j=i+1}^N P(i,j)$$$ Where $$$P(a,b)$$$ represents the exclusive or of every edge within the path of node a to node b.
An integer N $$$(1\le N \le 10^5)$$$, the amount of nodes in the tree that Diego has. Followed by $$$N-1$$$ lines, each line comes in the format u v X $$$(1 \le u,v \le N, u \neq v, 1 \le X \le 10^9)$$$, which indicates that there is a bidirectional edge between nodes u and v which has value $$$X$$$ written on it. It is guaranteed that the input will be a tree.
A single integer, the sum of the exclusive or between the path of every unordered pair of nodes.
4 1 2 1 2 3 4 2 4 2
21
If you don't know what an exclusive or is you can look at problem 'Xor sums' for its definition.
Diego is about to enter a raffle, however this raffle has some weird properties, instead of choosing the winning ticket at random with each ticket having the same probability of winning, they will chose which ticket wins based on a process, you have to help Diego guarantee that he will win the lottery!
Every ticket has an ID, all IDs are different and are bigger or equal to 1, additionally if ticket with ID $$$X$$$ exists all tickets with IDs $$$[1,X-1]$$$ must exist as well. In order to choose a winning ticket they will first sort all the tickets from left to right in ascending order by ID, then choose a starting ticket $$$S$$$ and some integer $$$K$$$. On each step they will move $$$K$$$ tickets to the right and eliminate the ticket where they land. Keep in mind that once a ticket is eliminated it's not in the list of tickets anymore, which means that if the current ticket has ID $$$X$$$, by moving $$$K$$$ tickets to the right, the ticket we land on may not have ID $$$X+K$$$ if some tickets in the middle already got eliminated. Additionally, when the end of the list is reached the next ticket is the first in the list, you can think of the list as cyclic.
Once a ticket gets eliminated the new starting ticket becomes the one to the left of the eliminated ticket (if the eliminated ticket was the first then the last one becomes the starting ticket). This process will continue until there is only 1 ticket left, that ticket will be crowned the winning ticket! Help Diego find the ID of the winning ticket.
An integer T $$$(1 \le T \le 10^5)$$$ the amount of test cases.
Followed by T lines, each with 3 integers $$$N, S, K$$$ $$$(1 \le S \le N \le 10^{18}, 1 \le K \le 10)$$$. Where $$$N$$$ represents the biggest ID that a ticket has, $$$S$$$ the starting position and $$$K$$$ the amount of tickets to move to the right before eliminating the next ticket.
$$$T$$$ integers, one per test case (in the order they were provided, of course). The ID of the winning ticket.
1 5 3 2
1
In the sample case, the following steps happen:
Step 1: [1,2,3,4,5], current position=3
Step 2: [1,2,3,4], current position=4
Step 3: [1,3,4], current position=1
Step 4: [1,3], current position=2
Step 5: [1] 1 is the winning ticket!
Diego and Googles are playing a game, in this game there are exactly $$$2*N$$$ numbers laid out around a circle such that for every position $$$i$$$, the numbers with positions $$$i+1 \mod 2*N$$$ and $$$i-1 \mod 2*N$$$ are beside it.
In this game first is Diego's turn, he will grab exactly $$$N$$$ consecutive numbers and then is Googles' turn, he will grab the remaining $$$N$$$ numbers. Then both of them sum all the numbers they grabbed and whoever has the biggest number will win. Googles immediately realized that if Diego plays perfectly there is no way for Googles to win, in the best case scenario they can tie. Therefore Googles asked Diego if he can reorder the numbers however he wants before Diego's turn, and he agreed.
Now, given $$$2*N$$$ numbers, what you have to do is find a permutation such that if Diego plays perfectly Googles can obtain the maximum amount of points possible.
An integer $$$N$$$ $$$(1 \le N \le 6)$$$, there are exactly $$$2*N$$$ numbers.
Followed by a line with $$$2*N$$$ positive integer numbers, each smaller or equal to 1 million.
$$$2*N$$$ numbers in a single line (separated by a single space), a permutation of the original $$$2*N$$$ numbers such that it doesn't matter what Diego does Googles' score is maximized. If there are several possible solutions, print any of them.
5 992 100 115 102 101 117 100 145 147 982
992 100 115 102 147 982 101 117 100 145
In the first case the maximum Diego can get given the permutation is $$$1456$$$ which means that Googles can get $$$1445$$$.
Diego wants to message his friend Ketzia, for this he will first grab a word and encode it as numbers and then apply some encryption to the numbers and send it to her. Ironically, after coming up with this solution he realized that this system has to send word by word, only works for words were every letter is in alphabetical order and also there are many chat services that are free and will encrypt messages securely so there was no need to invent this encryption system.
In order to encrypt Diego will first grab a word of $$$N$$$ characters and convert every character into its numerical ASCII (for example 'A' -> 65, '0' -> 48, 'a' -> 97). After that he will have exactly $$$N$$$ positive numbers.
Given those $$$N$$$ numbers, he will generate all possible $$$2^N$$$ subsets and then for each subset get the sum of all the numbers in the subset, he will then sort the sums and send them to Ketzia. She will decrypt the message by doing the inverse of the encryption steps.
For this particular problem, he will do the encryption of the message.
An integer $$$N$$$ $$$(1 \le N \le 20)$$$, the amount of characters that the word that Diego is sending to Ketzia has. The word will have its characters sorted in non-decreasing order by ASCII value.
A single word of length $$$N$$$ containing only lower and upper case letters and numbers.
$$$2^N$$$ numbers sorted in non-decreasing order in the same line, the encrypted word.
5 Beery
0 66 101 101 114 121 167 167 180 187 202 215 215 222 222 235 268 281 281 288 288 301 316 323 336 336 382 389 402 402 437 503
Diego wants to message his friend Ketzia, for this he will first grab a word and encode it as numbers and then apply some encryption to the numbers and send it to her. Ironically, after coming up with this solution he realized that this system has to send word by word, only works for words were every letter is in alphabetical order and also there are many chat services that are free and will encrypt messages securely so there was no need to invent this encryption system.
In order to encrypt Diego will first grab a word of $$$N$$$ characters and convert every character into its numerical ASCII (for example 'A' -> 65, '0' -> 48, 'a' -> 97). After that he will have exactly $$$N$$$ positive numbers.
Given those $$$N$$$ numbers, he will generate all possible $$$2^N$$$ subsets and then for each subset get the sum of all the numbers in the subset, he will then sort the sums and send them to Ketzia. She will decrypt the message by doing the inverse of the encryption steps.
For this particular problem, he will do the decryption of the message.
An integer $$$N$$$ $$$(1 \le N \le 20)$$$, the amount of characters the word Diego sent Ketzia originally had.
Followed by 1 line with $$$2^N$$$ integers $$$(0 \lt =a_i \lt =2440)$$$, all the sorted sums of all possible subsets of the $$$N$$$ numbers generated by converting all characters to their ASCII representation of the original word.
A single line with exactly $$$N$$$ alphanumeric characters sorted in non-decreasing order by ASCII value, the original word Diego sent Ketzia.
5 0 66 101 101 114 121 167 167 180 187 202 215 215 222 222 235 268 281 281 288 288 301 316 323 336 336 382 389 402 402 437 503
Beery
Diego is playing a very awesome RPG, in this game he is a knight and has to fight a dragon to the death, but before fighting the dragon he can buy some equipment which will make the fight easier. Help Diego get from the first room to the final room with as many coins as possible, and if there are many such answers tell Diego what in how many different ways he can reach the final room.
Every room is numbered from $$$1$$$ to $$$N$$$, they are sorted from left to right and can only move to the right (to rooms with bigger index). Also, every room $$$i$$$ has an amount of coins $$$c_i$$$, and from the room in position $$$i$$$, Diego can jump to any room with position $$$[i+1, i+k_i]$$$.
Given the $$$N$$$ rooms and their respective $$$k$$$ and $$$c$$$ values, tell Diego what is the maximum amount of coins he can get to the final room with and also in how many ways he can get there, since this number can be quite large print it modulo $$$10^9+7$$$.
An integer $$$N$$$ $$$(2 \le N \le 10^5)$$$, the amount of rooms. No input is provided for the last room since it's the room with the dragon.
Followed by a line with $$$N - 1$$$ integers $$$(0 \le c_i \le 10^9)$$$, the amount of coins in the room.
Followed by another line with $$$N - 1$$$ integers $$$(1 \le k_i \le N - 1)$$$, how many rooms to the right Diego can move to. It is guaranteed that $$$i+k_i \le N$$$.
2 integer numbers separated by a space, $$$C$$$ and $$$W$$$, the maximum amount of coins Diego can collect and all the ways he can collect them modulo $$$10^9+7$$$ respectively.
5 0 0 0 0 4 3 2 1
0 8
5 0 0 0 0 2 2 2 1
0 5
7 100 0 0 0 0 0 2 2 2 2 2 1
100 13
The city of Diegopolis has been growing to the point of reaching exactly 5 million people (making it 74th most populated city in the world), but to Diego's surprise (Diego is the mayor of Diegopolis), Thanos is about to snap his fingers and reduce the universe's population in approximately half. Because of this Diego wants to know what is the probability that at least K of his people survive Thanos's snap, since this number can be quite small make sure you print it modulo $$$10^9+7$$$. You should assume that any person has exactly 50% chance of surviving Thanos's snap.
A number $$$T$$$ $$$(1 \lt =T \lt =10^5)$$$, the amount of test cases.
Followed by $$$T$$$ lines, each line has an integer $$$K$$$ $$$(1 \lt =K \lt =5000000)$$$.
For each test case print a single integer $$$P$$$ $$$(0 \lt =P \lt 10^9+7)$$$, the probability that at least $$$K$$$ people survive Thano's snap.
2 0 5000000
1 195206359
In the sample test case there is a 100% chance that at least 0 people survive while the chances of all 5 million Diegopolians surviving is $$$\frac{1}{2^{5000000}} \equiv 195206359 \mod 10^9+7$$$.
Diego is out with $$$3$$$ of his friends (Jorge, Juan and Bob), when out of nowhere one of them realizes that there is a gigantic bar or chocolate, every single one of them is greedy so they want to eat as much chocolate as possible.
After many hours of arguing who gets to eat the most chocolate they came up with the following: the best division is one such that the difference between the person who eats the most chocolate and the person who eats the least chocolate is as small as possible.
As they are about to begin distributing the chocolate bar they came up to a realization, this bar has the shape of a rectangle, has exactly length $$$L$$$ and also has exactly $$$N-1$$$ different cutting spots, each spot located at a specific position $$$x_i$$$ (assuming that the chocolate bar begins in position $$$0$$$). So they must cut the chocolate bar in exactly $$$3$$$ of the cutting spots.
Help Diego find out the optimal way of dividing the chocolate bar in $$$4$$$ such that the difference between whoever eats less and whoever eats most is minimal.
A line with 2 integers, $$$N, L$$$ $$$(4 \le N \le 10^5, 4 \le L \le 10^{15})$$$, the amount of cutting spots within the chocolate bar and the length of the chocolate bar.
Followed by a line with $$$N-1$$$ integers in increasing order, representing the position of the ith cutting spot $$$(1 \le x_i \lt 10^{15})$$$. It's guaranteed that $$$x_i \lt x_{i+1}$$$ for $$$1 \le i \lt N - 1$$$.
A single integer $$$M$$$, the minimal delta between the smallest and biggest piece of chocolate if we divide the bar into exactly $$$4$$$ pieces.
8 18 3 4 5 8 10 12 15
2
In the test case, given the positions it's the equivalent of saying that we have 8 pieces of the following lengths: 3 1 1 3 2 2 3 3 There are 2 optimal answers, we can either split it in such a way that the 4 chocolate pieces the friends are going to eat are of sizes 5 5 5 3, or of sizes 4 4 4 6.
Lending money to friends can be problematic. In this task you will simplify an already problematic situation by solving a problem.
Imagine a group of $$$N$$$ people numbered from $$$0$$$ to $$$N-1$$$, each of which has been lending money to each other. However, they now want to settle all their debts and would like to do so in the most efficient manner.
Notice that for example, if person A lent $1 to person B and then person B lent $1 to person C, the most efficient way to settle the group's debts would be to have A pay C $1 directly.
Given a list of loans, find a sequence of payments such that the debts are settled. Moreover, this sequence of transactions must minimize the total amount of money transferred, and additionally minimize the number of transactions needed. (That is, first minimize the total amount, and then minimize the number of transactions.)
In the first line two integers, $$$N \le 18$$$ and $$$K \le 10^5$$$, representing the number of people and loans that happened between them.
The next $$$K$$$ lines contain three integers each: $$$a$$$, $$$b$$$, and $$$1 \le c \le 1000$$$, representing that $$$a$$$ lent $$$b$$$ $$$$c$$$.
In the first line one integer, $$$T \le 1000$$$, the amount of transactions needed to settle the debts.
The next $$$T$$$ lines contain three integers each: $$$a$$$, $$$b$$$, and $$$1 \le c \le 10^5$$$, representing that $$$a$$$ should pay $$$b$$$ $$$$c$$$.
2 1 1 0 1
1 0 1 1
3 4 2 0 2 1 0 1 1 0 1 2 0 1
2 0 2 3 0 1 2