Solution to Programming Question

King Arthur has a large kingdom that can be represented as a tree, where nodes correspond to cities and edges correspond to the roads between cities. The kingdom has a total of cities numbered from to . The King wants to divide his kingdom between his two children, Reggie and Betty, by giving each of them or more cities; however, they don't get along so he must divide the kingdom in such a way that they will not invade each other's cities. The first sibling will invade the second sibling's city if the second sibling has no other cities directly connected to it. For example, consider the kingdom configurations below:   Given a map of the kingdom's cities, find and print the number of ways King Arthur can divide it between his two children such that they will not invade each other. As this answer can be quite large, it must be modulo . Input Format The first line contains a single integer denoting (the number of cities in the kingdom). Each of the...

Samantha and Sam are playing a game. They have 'N' balls in front of them, each ball numbered from 0 to 9, except the first ball which is numbered from 1 to 9. Samantha calculates all the sub-strings of the number thus formed, one by one. If the sub-string is S, Sam has to throw 'S' candies into an initially empty box. At the end of the game, Sam has to find out the total number of candies in the box, T. As T can be large, Samantha asks Sam to tell T % (10 9 +7) instead. If Sam answers correctly, he can keep all the candies. Sam can't take all this Maths and asks for your help. Help him! Input Format A single line containing a string of numbers that appear on the first, second, third ball and so on. Output Format A single line which is the number of candies in the box, T % (10 9 +7) Constraints 1 ≤ N ≤ 2*10 5 Sample Input #00 16 Sample Output #00 23 Explanation #00 The substring of number 16 are 16, 1 and 6. Whose sum is 23 ...

Given an array of integers , we have line segments, such that, the endpoints of segment are and . Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of integers, , where is equal to length of ray shot from the top of segment . We define . For example, if we have , then , as shown in the picture below: For each permutation of , we can calculate . If we choose a uniformly random permutation of , what is the expected value of ? Input Format The first line contains a single integer T (1 <= T <= 100). T test cases follow. The first line of each test-case is a single integer N (1 <= n <= 50), and the next line contains positive integer numbers separated by a single space ( ). Output Format For each test-case output expected value of , rounded to two digits after the decimal point. Sample Input 6 3 1 2 3 3 3 3 ...