Reference no: EM131138214

Problem : Super ASCII String Cost

A string S is said to be "Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets ('a'­'z') and the ascii values will starts from 1 (i.e ascii value of 'a' is 1 and 'z' is 26). Now given a string S, you can perform operations, namely, add, delete and replace of any character present in the string. Every operation will consists of following costs

add = 2 unit

replace = 1 unit

delete = 3 unit

Your task is to convert the string to super ascii with the minimum cost. While converting the string to super ascii, the final string should contain the same characters as in the input string.

Input Format:

First line starts with T i.e. number of test cases, and then T lines will follow each containing a string "S". Output Format:

Print the minimum cost of conversion for each string to a Super Ascii string.

Constraints:

1<=T<=100
1<=|S|<=300, S will contains only lower case alphabets ('a'­'z').

Sample Input and Output

Explanation:

For Case1:
 Need to retain a, b since these are unique characters in this string
 Some of possible ways are

1. Delete two a's and add one 'b'. Total cost = 8
2. Replace one a with b, and delete other 'a'. Total cost = 4.

For Case2:

 Need to retain a, b, c since these are unique characters in this string
 Some of possible ways are

1. Replace 'a' and 'b' with 'c'. Total cost = 2.

2. Delete one 'a' and one 'b' and then add two c's. Total cost = 10.

Problem : The power of compounding

Manish has realized the power of compounding. Since the days he started earning, he has diligently set aside a small corpus which he saves from his monthly salary and deposits in his bank account. Bank pays him interest every month. Manish is also a determined investor and refrains from withdrawing anything from this account because he now believes in power of compounding. Given investment corpus, fixed annual rate of interest and maturity period calculate the amount the Manish will end up saving at the end of his tenure.

Input Format:

First line contains investment corpus P
Second line contains rate of interest per annum R
Third line contains tenure T (in months)

Output Format:

Print the maturity amount after specified tenure in the format "Final_Amount <Value>"

Constraints:
P > 0 ; it can be float value

R >=0 ; it can be float value

T >0 ; it can be integer only

Calculation should be done upto 11 ­digit precision

Maturity amount should be printed, rounded off to its nearest integer value

Problem : TestVita

TCS is working on a new project called "TestVita". There are N modules in the project. Each module (i) has completion time denoted in number of hours (Hi) and may depend on other modules. If Module x depends on Module y then one needs to complete y before x.

As Project manager, you are asked to deliver the project as early as possible. Provide an estimation of amount of time required to complete the project.

Input Format:

First line contains T, number of test cases. For each test case:
1. First line contains N, number of modules.
2. Next N lines, each contain:
? (i) Module ID
? (Hi) Number of hours it takes to complete the module
? (D) Set of module ids that i depends on ­ integers delimited by space.

Output Format:

Output the minimum number of hours required to deliver the project.

Constraints:
1. 1 <= T <= 10
2. 0 < N < 1000; number of modules
3. 0 < i <= N; module ID
4. 0 < Hi < 60; number of hours it takes to complete the module i
5. 0 <= |D| < N; number of dependencies
6. 0 < Dk <= N; module ID of dependencies

Explanation:

Module 2 depends on module 1, hence complete module 1 first

After completing module 1 we can complete module 2 and then module 3

Module 4 and 5 can be started simultaneously in parallel after module 3 is completed. Hence the answer = 5 + 6 + 3 + 2 = 16

Problem : Break The Friendship

In a class room everyone is very friendly and has bonded with others in a short span of time. During the exams, students will sit along with their friends and will write the exams, which actually resulted in the finding that only a few members in the batch are good at studies and others are not. After getting several complaints from the staff members, the Principal has agreed to change the sitting pattern during the exams for which she has formed a committee. Using a spy, committee was able to get a list of close friends for all the students in the class. Now using this list they want to identify two groups of people such that a person in one group must not be a friend to any other in the same group. Your task is to help the committee.

Input Format:

Input consists of two parts, viz.

1. First Line contains, number of students in the class room (N) and number of friendship connections (M)
2. Next M line contains a list that represents two integers i and j, which represents that i and j are friends

Print "Yes" if the committee can divide the students in two groups of people, else print "No". Constraints:
1 <= N <= 50
1 <= M <= N * (N­1)/2
1 <= I, j <= N

Problem : FEN Processor

Background

A Chess board position is accurately captured by Forsyth­Edwards notation and is abbreviated as FEN. A FEN "record" defines a particular game position, all in one text line and using only the ASCII character set. A FEN record contains six fields. A complete description of the FEN format to represent Chess positions can be found at here

For the purpose of this problem only consider first of the six fields of FEN. Before we describe the problem, let us look at how FEN maps to a board position. The following 5 images show board positions and its corresponding FEN representation.

This board position depicts initial position before any side has made a move. In FEN format this board position is represented as

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

Let's say, White plays e4. Then the board position looks like shown below

This board position depicts the Chess board after White has played e4. In FEN format this board position is represented as rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

Similarly, 3 more half­moves are depicted in following diagrams

The FENs corresponding to Figure 3, 4 and 5 are represented as

3. rnbqkbnr/pppp1ppp/8/4P3/4P3/8/PPPP1PPP/RNBQKBNR

4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR

5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR

Wikipedia describes first field of FEN format as follows

Piece placement (from white's perspective). Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file "a" through file "h". Following the Standard Algebraic Notation (SAN), each piece is identified by a single letter taken from the standard English names (pawn = "P", knight = "N", bishop = "B", rook = "R", queen = "Q" and king = "K").[1] White pieces are designated using upper­case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks

Statement

You will be given FENs of successive board positions. Your task is to construct a move list in standard algebraic formatfrom these FENs. For e.g. the five FENs depicted above will show the following move list

1) e4 e5
2) f4 exf4

You will also have to print the total (White + Black) number of captures that have happened in the game.

Sections below describe the Input and Output specifications followed by examples. Input has to be read from console and output has to be written back to console.

Input Format:

1. Each input will correspond to a one game only i.e. all successive FEN inputs will represent successive board positions that are a part of the same game.
2. Each input will begin with FEN corresponding to Initial Position in chess as depicted in Fig 1.
3. One line will contain only one FEN record 4. There can be arbitrary number of FEN records provided as input 5. Input will be terminated by ­1

Output Format:

1. Each line of output should correspond to a tuple <Move number, White's move, Black's move>

2. Move Number is the move number followed by ')'

3. White's move is move played by white, denoted in Algebraic notation

4. Black's move is move played by black, denoted in Algebraic notation

5. All parts of the tuple should be printed using a single space character as delimiter

6. A capture must be denoted by x. See example output how a move representing a capture is printed.

7. Print the entire Move List represented by input FENs

8. At the end of the Move List, the output must print Number of Captures : <n>, where n corresponds to total number of captures by White and Black together.

9. See example outputs for better understanding

Constraints:

1. A check in algebraic notation is depicted by '+' symbol. We don't expect checks to be detected. Hence the output should be printed without '+' symbol. Ditto for double checks.

2. Similarly, a check mate is usually denoted by #. We don't expect check mate to be detected. Hence the output should be printed without '#' symbol.

3. Similarly, castling is usually denoted by o­o (short castle) or o­o­o (long castle). We don't expect castling to be detected. Hence our test cases don't contain FENs which give rise to such positions.

4. Algebraic notation provides a way to disambiguate a move. We don't expect disambiguation to be implemented. Hence we have ensured test cases don't have ambiguous move. The following diagram explains the ambiguity and the corresponding disambiguation method.

Problem : Milk Man and His Bottles

A Milkman serves milk in packaged bottles of varied sizes. The possible size of the bottles are {1, 5, 7 and 10} litres. He wants to supply desired quantity using as less bottles as possible irrespective of the size. Your objective is to help him find the minimum number of bottles required to supply the given demand of milk.

Input Format:

First line contains number of test cases N
Next N lines, each contain a positive integer Li which corresponds to the demand of milk.