Codevita -22-07-2017 655b2e

1.Problem : Digital Time 12 The objective is to form the maximum possible time in the HH:MM:SS format using any six of nine given single digits (not necessarily distinct) Given a set of nine single (not necessarily distinct) digits, say 0, 0, 1, 3, 4, 6, 7, 8, 9, it is possible to form many distinct times in a 12 hour time format HH:MM:SS, such as 10:36:40 or 01:39:46 by using each of the digits only once. The objective is to find the maximum possible valid time (00:00:01 to 12:00:00) that can be formed using some six of the nine digits exactly once. In this case, it is 10:49:38. Input A line consisting of a sequence of 9 (not necessarily distinct) single digits (any of 0-9) separated by commas. The sequence will be non-decreasing Output The maximum possible time in a 12 hour clock (00:00:01 to 12:00:00) in a HH:MM:SS form that can be formed by using some six of the nine given digits (in any order) precisely once each. If no combination of any six digits will form a valid time, the output should be the word - Impossible Example 1 Input: 0,0,1,1,3,5,6,7,7 Output: 11:57:37 The maximum valid time in a 12 hour clock that can be formed using some six of the 9 digits precisely once is 11:57:37 Example 2 Input: 3,3,3,3,3,3,3,3,3 Output: Impossible No set of six digits from the input may be used to form a valid

time.

2.Problem : Prime numbers spelt with prime number of letters If you like numbers, you may have been fascinated by prime numbers. These are numbers that have no divisors other than 1 and themselves. If we consider the primes 2 and 3, and write them in words, we write TWO and THREE. Both have a prime number of letters in their spelling. Not all prime numbers have this property. Write a program to count the number of primes between a given pair of integers (including the given integers if they are primes) that have a prime number of characters when written in words. The blanks are not counted when we write the numbers in words. For example, ONE HUNDRED AND THREE has only 18 characters. Input One line containing two integers separated by space giving N1 and N2 Output One integer M giving the number of primes P such that N1 <= P <= N2 that are such that when P is written in words, it has a prime number of letters. Constraint N2 <= 99999 Example 1 Input: 1 10 Output: 3 Explanation: The primes between 1 and 10 and 2, 3, 5 and 7. Of these, 5 written in words is FIVE and has a non prime number of letters and others have prime number of letters (viz TWO, THREE and

SEVEN). Example 2 Input: 1100 1130 Output: 1 Explanation: The primes between 1100 and 1130 are 1103, 1109, 1117, 1123 and 1129. When these are written in words, we get ONE THOUSAND ONE HUNDRED AND THREE ONE THOUSAND ONE HUNDRED AND NINE ONE THOUSAND ONE HUNDRED AND SEVENTEEN ONE THOUSAND ONE HUNDRED AND TWENTY THREE ONE THOUSAND ONE HUNDRED AND TWENTY NINE The count of characters in the above are 29, 28, 33, 35 and 34 Of these only for 1103 the count of characters is prime.

3.Problem : Fibonacci Right Triangles The Fibonacci series 1,1,2,3,5,8,... is well known. In this series, if Fn is the nth number F1=1, F2=1, Fn=Fn-1+Fn-2 Every alternate number in the series stating with 5 (5,13,34,...) can be the hypotenuse of a right angled triangle. We call each of these a Fibonacci Right Angled Triangle, or FRAT for short. The larger of the remaining two sides is the nearest integer to (2/sqrt(5)) times the hypotenuse. A factor of a positive integer is a positive integer with divides it completely without leaving a remainder. For example, for the number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two factors, 1 and the number k itself. The objective of the program is to find the number of factors of the even side of the smallest FRAT whose hypotenuse is odd and is larger than a given number Input

The input is a positive integer N Output The number of factors of the even side of the smallest FRAT which has an odd hypotenuse greater than N Constraints The even side is less than 5000000 Example 1 Input: 10 Output: 6 Explanation: The smallest FRAT that has an hypotenuse greater than 10 is (13,12,5). As the hypotenuse is odd, we take this. The even side is 12, factors are (1,2,3,4,6,12), a total of 6 factors. The output is 6 Example 2 Input: 20 Output: 10 Explanation: The smallest FRAT that has an (34,30,16). As the hypotenuse which is (89,80,39). The even (1,2,4,5,8,10,16,20,40,80), a 10

hypotenuse greater than 20 is is even, we take the next FRAT, side is 80, factors are total of 10 factors. The output is

4.Problem : Smallest Multiple in permuted digits Given two integers N, d , find the smallest number that is a

multiple of d that could be formed by permuting the digits of N. You must use all the digits of N, and if the smallest multiple of d has leading zeros, they can be dropped. If no such number exists, output -1. Input A line containing two space separated integers, representing N and d. Output A single line giving the permutation of N that is the smallest multiple of d, without any leading zeroes, if any. If not such permutation exists, the output should be -1 Constraints 1≤N≤1000000000000 1≤d≤1000000 Example 1 Input 210 2 Output 12 Example 2 Input 1707693158 853684 Output 513917768 Example 3 Input 531 2 Output -1 Explanation 1. In first test case the minimum number formed using all the three digits divisible by the given divisor is 012 which is

equivalent to 12 and this is a multiple of d = 2. Hence the output is 12. 2. In second test case the minimum number formed using all the digits divisible by the given divisor is 0513917768. So in this case the output will be 513917768. 3. In the last case all permutations of digits of N are odd and hence not divisible by d.

5.Problem : A Complicated Bomb Drop Game TCS India has developed a funny and entertaining game. When you begin, the screen contains a number of lines. An enemy plane drops a bomb of certain radius R at a certain location (x,y) on the screen and all the portions of the lines that are within a circle of

radius R with center (x,y) are destroyed.

After the bomb destroys the portions of the lines, compute the sum of the lengths of the lines remaining. Input The input consists of N+3 lines, where N is the number of lines. The first line is N, the number of lines. The second line is R, the radius of the bomb The third line contains the coordinates of the point at which the bomb is dropped, as a pair of space separated integers (x and y) The next N input lines contain the coordinates of the start and the end of a line on the screen. This is a set of 4 space separated integers (may be negative or 0) representing the x and y coordinates of the starting and ending point respectively of the line on the screen. Output A single line containing the sum of the lengths of the residual lines. This must be expressed as a number correct to two decimal

places. Note that the output must always be shown with two decimal places even if the residual length is an integer. Thus, if the residual length is 16, the output must be 16.00, and if the residual length is 0, the output must be shown as 0.00 Constraints 1 <20 -1000<x,y coordinates of lines, bomb drop <1000 0 <1000 Example 1 Input: 4 4 2 4 2 6 2 12 2 -10 2 -6 4 4 10 4 -8 4 -4 4 Output: 16.00 Explanation: Before the bomb drop, the lines on the screen were as follows After the bomb is dropped at (2,4) with radius 4, the position on the screen is There are 4 lines, each of length 4, and hence, the total residual length is 16. The output is 16.00 Example 2 Input: 7 4 3 5 3 9 3 13 3 -3 3 -15 4 9 16 9 -1 9 -11 9 11 13 3 5 9 8 4 6 -1 5 -5 5 Output: 52.04

Explanation: There are initially 7 lines, and the bomb is dropped at (3,5) with a radius 4. Only the fifth and sixth lines are affected by the bomb, and become 7.31 and 2.72 in length. The total residual length (correct to two decimals is 52.04, which is the output.

6.Problem : Counting Squares Mr Smith, the Mathematics teacher for Standard VI, is an exasperated person. He wants to device a way to keep his class of excited students quiet, so he can catch a bit of sleep (he went to late night showing of Baahubali 2 the previous night). He drew ten equally spaced horizontal lines an ten equally spaced vertical lines so that they formed 100 1 x 1 squares. He then erased at random various segments of lines ing points of the grid, and asked the class to count squares of all sizes with sides along the lines that are remaining on the board. He believed that this would take at least an hour. The class had been taught programming in the summer, and so some students quickly wrote some code to count the squares, and Mr Smith did not get much sleep ! Can you emulate the students? You will be given a set of N horizontal and vertical lines with some missing segments. You need to count the number of squares of all sizes (1 x 1, 2 x 2, ... N x N) with sides fully present in the remaining lines.

The above, for example is a set of 4 horizontal and 4 vertical equally spaced lines with a number of segments removed. We need to count squares of all sizes with sides along the remaining lines Input The first line of the input is a positive integer N giving the number of horizontal and vertical lines. The second line is a non-negative number m giving the number of segments removed. Then there are m lines, each containing V,i,j or H,i,j, where i

and j are positive integers. H,i,j indicates a horizontal gap in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in the ith vertical line between the jth and (j+1)th point on the line. Output The output is a single line giving the total number of squares in the figure, with sides along the remaining lines in the figure Constraints 4≤N≤20 0≤m≤40 I≤N J≤(N-1) Example 1 Input 4 4 H,2,1 H,3,1 V,2,2 V,2,3 Output 5 Explanation There are 4 vertical and horizontal lines, and 4 line segments missing. The first missing horizontal segment is on the second horizontal line, between the first and second point, and the other missing horizontal segment is on the third horizontal line at the same position. The two missing vertical segments are on the second vertical line, and between the second and third, and the third and fourth points respectively. It can be seen that this describes the above figure. There is one 3 x 3 square, zero 2 x 2 squares and four 1 x 1 squares, a total of 5 squares. Hence the output is 5. Example 2 Input 4 2 V,2,2 V,2,3

Output 8 Explanation It has four vertical lines and four horizontal lines. Two vertical segments are missing, on the second line, between the second and third point and the third and fourth point. There is one 3x3 square, two 2 x 2 squares and five 1 x 1 squares with sides along the remaining lines. Hence there are a total of 8 squares remaining, and the output is 8.