Bank Transactions
Name: Bank Transactions
Description: Testing
Languages: C / C++ / Java
Submissions:10 (max)
In one of the internet banks thousands of transactions are being performed every day. Since certain customers do business more actively than others, some of the bank accounts occur many times in the list of operations. So, the Managers/Admins of the bank want to know the number of transactions performed by those customers from time to time. Banks are real time institutions and they need fast solutions.
The internet bank decides to feed the transactions as they are comming into the your program. At any point of time the Managers/Admins will also query your program to find out number of transactions done by any particular customer, till that point of time. Finally, at the end of the day the program should generate a report which tells the number of transactions performed on that day. And List the customers who have made atleast one transaction, along with the number of transactions. One more constraint is the list generated in the report should be sorted based od the customerID.
Each customer of the bank will be given a CustomerID. The length of the CustomerID for all the customers is fixed. But as there is a possibility of changing the width of the CustomerID the bank gives the width to the program only at runtime. The CustomeID contains either numbers from 0 to 9 or upper case alphabets from A to Z.
# It is decided that the program will get three kinds of commands: 1 <CustomerID> - add the transaction to the existing list of transactions.
# 2 <CustomerID> - Output the number transactions done by that customer till that point of time.
# 9 - Generate report and Stop the processing.
Input Format
There will be a single test case. The first line will be the width of the CustomerID. Followed by a blank line. From here onwards for every two lines, first line contains the command, and the second line contains the CustomerID. If the first line contains '9' then there wont be a second line and also the input ends there only.
Output Format
Do not output anything when the command is '1'. When the command is '2', output the number of transactions till that time in one line. When the command is '9' then print a blank line followed by one CustomerID per line followed by a 'space' and then number of transactions.
Sample Input
5
1
12345
1
23F56
1
12345
1
12345
2
23F56
2
34567
1
12345
1
34567
2
12345
2
A654A
9
Sample Output
1
0
4
0
12345 4
23F56 1
34567 1
Note that the first four numbers are the counts of the transactions for the given CustomerID when the call is made.
------
Permutation Sorting
An N-element permutation is an N-element sequence of distinct numbers from the set {1, 2, ...,n}. For example the sequence 2,1,4,5,3 is a 5-element permutation. P is an N-element permutation. Your task is to sort P in ascending order. But because it is very simple, I have a new rule for you. You have two sequences P and Q. P is an N-element permutation and Q is initially empty and formed by sorting P (i.e. finally Q = 1, 2, 3,... , N). You have to implement N steps to sort P. In the i-th step, P has N-i+1 remaining elements, Q has i-1 elements and you have to choose some x-th element (from the N-i+1 available elements) of P and put it to the left or to the right of Q. The cost of this step is equal to x * i. The total cost is the sum of costs of individual steps. After N steps, Q must be an ascending sequence. Your task is to minimize the total cost.
Input Format
The first line of the input file is T (T = 10), the number of test cases. Then descriptions of T test cases follow. The description of each test case consists of two lines. The first line contains a single integer N (1 = N = 1000). The second line contains N distinct integers from the set {1, 2, .., N}, the N-element permutation P.
Output Format
For each test case your program should write one line, containing a single integer - the minimum total cost of sorting.
Sample Input:
1
4
4 1 3 2
Sample Output:
15
----------
Longest Sub-sequence
Given a sequence of integers containing both negative and positive numbers, find out the longest subsequence which is in A.P. (Arithmetic Progression).
Input Format
There will be one sequence of integers separated by space on one line. Number of integers in the sequence will not be given.
Output Format
The longest subsequence which is in A.P.
Sample Input
0 -2 4 1 2 4 6 5 7 6 10
Sample Output
-2 1 4 7 10
-----------
XX - Chromosomes?
Ok, this has nothing to do with the fair chromosomes. The problem here is one with the dry strings. Given a string of arbitrary length and containing arbitrary symbols, our task is to find the shortest and the longest sub-strings of the form XX.
Input Format
There will be one positive integer n on the first line specifying the number of testcases. Next n lines have a string each on them. For simplicity, you can assume that none of the strings has more than 999 characters.
Output Format
For every testcase, you should print the shortest and longest string on a separate line individually. If there are no strings of the form XX, just print two blank lines.
Sample Input
2
asddfghhhh
ILooveKodarenaILooveKodarena
Sample Output
dd
hhhh
oo
ILooveKodarenaILooveKodarena
-----------
Triangle Partitioning
A triangle can be divided into two equal triangles by drawing a median on its largest edge. Then the smaller two triangles can be divided in similar fashion into more sub-triangles. This process can continue forever. Some mathematicians have found that when we split a triangle into smaller ones using the method specified above we have only some "styles" of triangles that only differ in size. So now given the lengths of the sides of the triangle your job is to find out how many different styles of small triangles we have. (Two triangles are of same style if they are similar).
Input Format
There will be a single testcase. The lengths of sides of a triangle will be given on a single line.
Output Format
Output the number of different styles of triangles that will be obtained while following the above process.
Sample Input
2 2 2
Sample Output
3
Hint: Whenever you compare 2 values (int/float/double), assume that they are equal if the difference is less than 0.0001%
-------------
Move the Robot
The MPC Robots is a company engaged in designing and developing software for robots. Now they have to design a robot's software, which decides the movement of the robot. They have decided to allot only a single memory location 'X' for a value which decides the amount of distance the robot has to move. The robot can move only forward or backward. It doesnot have sideward movements. So a negative value in the memory location means that the robot will move backward, and a positive value moves the robot forward.
This particular memory location 'X' has a strange constraint. It is switched off when the robot is not in motion. When ever the robot has to move it is switched on and will have an initial value of '0'. More over, this memory location has to be constantly updated at every instance. And the operations supported by this memory location are either incremented by one or decremented by one. For example, if the current value is '1', the possible values for that location is either '0' or '2', and it cannot be any other number.
The robot moves forward or backward whenever the memory location is changed. If the value of the memory location 'X' is 2 at one instance, then the robot moves forward by two units, at that instance. If it is -3 then it moves backwards by 3 units. So every time the robot's position is to be changed, we give it two inputs, first one is how many times the value of the memory location 'X' has to be changed, and the other one is the amount of displacement from the current location. If we give 8 and 4 as inputs, the robot has to reach a point 4 units forward from its current location by changing the memory location value 8 times, not more or not less, exactly 8. And if a negative value is given, then the displacement should be backward.
The example senario: The robot has to be moved forward by 4 units by changing the memory location 'X' value by 8 times.
The software program can now change the value of the memory location as follows to accomplish this.
0 - initial state; The memory location is switched on.
-1 - second change; robot moves backward.
0 - third change; robot doesnot move.
-1 - fourth change; robot moves back one more step.
0 - fifth change; robot doesnot move.
1 - sixth change; robot moves forward by one unit.
2 - seventh change; robot moves forward by two units.
3 - eighth change; The robot now moves forward one step, and thus reaches the required point.
Now we have to write a program which takes the number of changes to be done to the memory location, and the total displacement of the robot as input. And the output will be the values of the memory location after each update in order to reach the target.
Input Format
The first line will be the number of test cases. Followed by a blank line. Each test case will be seperated by a blank line. For each testcase there will be two numbers as input. One in each line. The first line corresponds to the number of changes. The second number corresponds to the total displacement.
Output Format
For each test case print the values of the memory location, one value in each line. If there are multiple ways to achieve the target print only one such way to move the robot. If there isn't any way to achieve the target then print the string "No". After each test case print a blank line.
Sample Input
2
8
4
3
-1
Sample Output
0
-1
0
-1
0
1
2
3
0
-1
0
-------------
Diffuse The Bomb
Mafia Chief Katti has planted a bomb to bring down club Ciddu. The Bomb has huge set of wires side by side which are labelled alpha-numarically.DoN knows that bomb has been planted and wants to diffuse it. He also knows the particular sequence of wires which causes the bomb to explode.
Help DoN to find out the minimum number of wires to be cut so that above sequence of wires no longer exists in the bomb and thus saving club Ciddu.
Input Format
Input contains some test cases. Each test cases contains two lines.
First Line has the Bomb's entire labelled sequence of wires. (<=10000)
The second line has the paricular sequence of wires which causes the bomb to explode.(<=1000)
Output Format
For each test cases, You should output exactly one integer which is the minimum number of wires to cut to ensure that particular sequence no longer exists in bomb.
Sample Input
ab12121bc
121
xyzxyxyz
xy
Sample Output
1
3
-------------
Help DoN to get Maximum LooT
DoN is in Kuala Lampur. He is in club Ciddu. He has found secret set of lockers containing the whole set of loot and some trap set by his enemies. The lockers will always be arranged in the form of a square. Now DoN has to find the maximum loot (getting gold or cash will increase his loot and opening traps will decrease his loot.
DoN's goal is to get the maximum loot in such a way that he can choose lockers that only form a rectangular block either directly or virtually else a bomb will explode. By virtually it means that the lockers can be assumed to be arranged back to back only on the left and right edges of the lockers square.
Input Format
The input begins with the number of lockers in a row or a column (<=100).
Followed by the loot amount(0 to 127) or the various traps(-127 to -1) in the lockers in row major order.
Output Format
The output should be the maximum loot that DoN can obtain without the bomb exploding.
Sample Input
4
0 -1 -8 0 8 3 -5
2 -4 1 -4 1
-1 8 0 -1
Sample Output
17
------------
Blocks with Rectangles
There are n rectangles drawn on the plane. Each rectangle has sides parallel to the coordinate axes and integer coordinates of vertices.
We define a block as follows:
* each rectangle is a block,
* if two distinct blocks have a common segment then they form the new block otherwise we say that these blocks are separate.
The task is to write a program that for each test case:
* reads the number of rectangles and coordinates of their vertices;
* finds the number of separate blocks formed by the rectangles;
* writes the result to the standard output.
Input Format
The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.
In the first line of a test case there is an integer n, 1 <= n <= 7000, which is the number of rectangles. In the following n lines there are coordinates of rectangles. Each rectangle is described by four numbers: coordinates x, y of the bottom-left vertex and coordinates x, y of the top-right vertex. All these coordinates are non-negative integers not greater than 10000.
Output Format
For each test case you should output one line with the number of separate blocks formed by the given rectangles.
Sample input:
1
9
0 3 2 6
4 5 5 7
4 2 6 4
2 0 3 2
5 3 6 4
3 2 5 3
1 4 4 7
0 0 1 4
0 0 4 1
Sample output:
2