Description
Find the root for the equation:
Where x is a real number in [0,1] (i.e., 0 ≤ x ≤ 1)
Input
Input consists of a single test case. The test case consists of 6 integers in a single line: a, b, c, d, e and f (where 0 ≤ a, c ≤
20, −20 ≤ b, d, e ≤ 0, and -10^9 ≤ f ≤ 10^9).
Output
The output should be a single line containing the value x of the root for the above equation, correct up to 4 decimal places
(there should be exactly 4 digits after the decimal point), or the string ‘No solution’, whichever is applicable.
You can assume that there will be only one root in [0,1] if it exists.
Example 1
Input:
0 0 0 0 1 -1
Output:
1.0000
Example 2
Input:
0 0 0 0 1 0
Output:
0.0000
Example 3
Input:
1 0 0 0 0 1
Output:
No solution
Page 1/1
Kou Sort
Kou just finished her first algorithm class and designed a new sorting algorithm: given an array of N distinct numbers, the
algorithm sorts them in ascending order by performing the minimum number of swaps required. A swap is an exchange of
two adjacent elements in the array.
For example, if the array is [9, 1, 0, 5, 4], the smallest number of required swaps to produce the array [0, 1, 4, 5, 9] is 6.
0: [9, 1, 0, 5, 4] (original array)
1: [1, 9, 0, 5, 4] (swap 1)
2: [1, 0, 9, 5, 4]
3: [1, 0, 5, 9, 5]
4: [1, 0, 5, 4, 9]
5: [0, 1, 5, 4, 5]
6: [0, 1, 4, 5, 9] (swap 6)
(Note that there may be other sequences of swaps that lead to the minimum number of swaps.)
Now Kou wants to determine if her algorithm always performs as she claims it does. Given an array of N distinct integers,
your task is to figure out the minimum number of swaps required to sort it. Kou will then make sure that her algorithm
performs exactly that number of swaps.
Input
The first line of the input contains a single integer N (1 <= N <= 500,000), the size of that array. The following N lines
represent the content of the input array. Each of these N lines contains a single integer between 0 and 999,999,999. It is
guaranteed that the array contains no duplicates.
Output
You should print one line containing a single integer: the minimum number of swaps required to sort the given array.
Example 1
Input:
5
9
1
0
5
4
Output:
6
Example 2
Input:
3
1
2
3
Output:
0
Page 1/1
Load Balance
You are an operator of a super computing center and in control of M nodes. One day, a research institute from Light
Kingdom submitted N computational tasks. Given the computational power needed for each task, you are to distribute the
tasks among the available nodes. Restriction: every node can process up to two tasks. You also want to distribute the
workload as evenly as possible, i.e. minimize the following imbalance value
where Avg is average load per node and Loadi
is the load of the i-th node.
Input
The first line of the input contains two integers M (1 <= M <= 5) and N (1 <= N <= 2M), indicating the number of nodes you
control and the number of tasks, respectively.
The second line contains N integers, each of which represents the computational power required for a task. Numbers on
these line are between 1 and 1000.
Output
Print one line IMBALANCE = I where I is the minimum imbalance value rounded to 5 decimal places.
Example 1
Input:
2 3
6 3 8
Output:
IMBALANCE = 1.00000
Example 2
Input:
3 5
51 19 27 14 33
Output:
IMBALANCE = 6.00000
Example 3
Input:
5 9
1 2 3 5 7 11 13 17 19
Output:
IMBALANCE = 11.60000
Page 1/1
Nucleic Acids
For a string S of length N, we can define inversion as follows: If for an integer pair (i,j), we have 0 ≤ i < j < N, and S[i]>S[j],
then (i,j) is a inversion for S.
Define a function Count(S), which returns the number of distinct inversions in S.
For example, Count(“ABC”) = 0 since “ABC” is sorted, and Count(“DAABEC”) = 5, since D is greater than four letters to its
right and E is greater than one letter to its right.
You are responsible for cataloging a sequence of nucleic acid strings, which are strings containing only the four letters A, C,
G, and T. The Count(S) is a measure of “unsortedness” for S. You want to catalog them in order of “unsortedness”, from
“most sorted” to “least sorted”. All the strings are of the same length.
Input
The first line contains 2 integers: a positvie n (0 < n ≤ 50) giving the length of all strings, and a positive integer m (0 < m ≤
100) giving the number of strings, These are followed by m lines, each containing a string of length n.
Output
Output m lines, the list of input strings, arranged from “most sorted” to “least sorted”. If two or more strings are equally
sorted, list them in the same order they are in the input file.
Example 1
Input:
6 3
GATCAG
ACCCTT
AAAAAA
Output:
ACCCTT
AAAAAA
GATCAG
Page 1/1
Party Fee
Saya just graduated from her high school! She and her classmates rented a ballroom and held a party to celebrate their
graduation. They realized that the room fee was not split evenly since some of them did not bring enough money. After
going home, they decided to re-split the fee. However, the payment app they use only allows transfers between friends. As
a kind person, you want to help them out.
You will be given information about how much money each of them owes or is owed and whom the friends are. Your task is
to figure out if it is possible for them to redistribute the party fee evenly.
Input
The first line of the input contains two integers N (2 <= N <= 10,000) and M (0 <= M <= 50,000), representing the number of
students and the number of friendships, respectively.
Each of the following N lines contains a single integer d (-10,000 <= d <= 10,000), indicating how much that student owes (if
d > 0) or is owed (if d < 0). The student had already paid the right amount of the party fee if d is 0. It is guaranteed that sum
of all d’s is 0.
The following M lines describe friendships. Each of these M lines contains two integers a and b (0 <= a < b < N), meaning
that the a-th and the b-th student are friends. Note that a friendship may appear more than once and it is also possible that
someone is friends with themselves.
Output
You should print one line containing POSSIBLE or IMPOSSIBLE , indicating if it is possible for them to redistribute the
party fee only by sending money to their friends.
Example 1
Input:
5 3
100
-75
-25
-42
42
0 1
1 2
3 4
Output:
POSSIBLE
Example 2
Input:
4 2
15
20
-10
-25
0 2
1 3
Output:
IMPOSSIBLE
