Data compression reduces the data redundancy ,increases effective data density and speeds up data transfer. One method to compress data is :
Replace any maximal sequence of n 1's with the binary version of n whenever it shortens the length of the message.
Example:
The compressed form of the data 11111111001001111111111111110011 becomes 10000010011110011. The original data is 32 bits long while the compressed data is only 17 bits long. The drawback of this method is that sometimes the decompression process yields more than one result for the original message, making it impossible to obtain the original message.
Write a program that determines if the original message can be obtained from the compressed data when the length of the original message (L), the number of 1’s in the original message (N) and the compressed data are given. The original message will be no longer than 16 Kbytes and the compressed data will be no longer than 40 bits.
Input:
The input contains several test cases. Each test case has two lines. The first line contains L and N and the second line contains the compressed data.
The last case is followed by a line containing two zeroes.
Output :
For each test case, output a line containing the case number (starting with 1) and a message YES, NO or NOT UNIQUE. YES means that the original message can be obtained. NO means that the compressed data has been corrupted and the original message cannot be obtained. NOT UNIQUE means that more than one message could have been the original message. Follow the format shown in the sample output.
Sample Input:
32 26
10000010011110011
9 7
1010101
14 14
111111
0 0
Sample Output:
Case #1: YES
Case #2: NOT UNIQUE
Case #3: NO
riangles
Write a program that accepts a set of n line segments in a plane as input and gives the number of distinct triangles formed by these line segments as output.
Input to the program
The first line of input gives the number of line segments (n). The next n lines specify a line segment each by specifying the coordinates of its end points, i.e., x1, y1, x2, y2 (all integers) where (x1, y1) and (x2, y2) are the coordinates of the end points of the line segment. The four numbers appear on the same line, separated by blanks. You can assume that -20 <= x1, y1, x2, y2 <= 20. Further assume that n <= 20. Also assume that no two line segments can be fully or partially overlapping. Two lines segments may share an end point but not if they are parallel.
Output of the program
The output of the program should just be a single integer that is the number of distinct triangles formed by the given line segments.
Sample Input
6
3 1 5 1
3 1 3 2
3 2 4 2
4 2 5 1
3 2 5 1
3 1 4 2
Output for the sample input
8
TRANSFORMATION
Statement :
The following transform is used in one of the methods for text compression :
Step 1 : Let t be the size of the input text (in our example t = 6). We obtain a matrix M with dimensions t x t. The first line of M corresponds to the input text. The i-th line, for i = 2,....,t, corresopnds to a circular left shift of i-1 positions with respect to the input text.
For BANANA, we obtain the following matrix M:
1 2 3 4 5 6
1 B A N A N A
2 A N A N A B
3 N A N A B A
4 A N A B A N
5 N A B A N A
6 A B A N A N
Step 2 : We sort the lines of matrix M lexicographically to obtain a new matrix P. In our example, we get the following matrix P:
1 2 3 4 5 6
1 A B A N A N
2 A N A B A N
3 A N A N A B
4 B A N A N A
5 N A B A N A
6 N A N A B A
Step 3 : The transform for the given text is then given by the last column (i.e. column t) of matrix P and by the number of the row of P that corresponds to the input text. In our example, the last column of P is NNBAAA and the row of P which contains BANANA is the fourth one. Therefore, the transform for BANANA is the pair (NNBAAA, 4).
The goal of this problem is to implement the Inverse of this transform. Given the last column of a matrix P and the number of the row of P which contains the input text, your program should obtain the input text.
Input Format :
The input may contain several instances of the problem, occuring consecutively in the input, without any blank lines separating them. Each instance has 2 lines :
1. The first line contains the entries in the last column of matrix P, starting from the first row. Each entry is an uppercase letter, NOT separated by any blank spaces from its neighbouring entries.
2. The second line contains the integer number corresponding to the row of P which contains the input text.
The last instance of the input consists of the two lines
END
0
You may assume that the input text of each instance contains at most 300 letters.
Output Format :
For each instance of the problem, your program should print the input text as consecutive letters in a single line. The output of each instance is separated from the next by a blank line.
Sample Input :
NNBAAA
4
OMOEULCG
1
END
0
Sample Output :
BANANA
COGUMELO
Now a days Air fare is too high.So many travelers try to be smart ,sometimes using only parts of the tickets with stops in various cities to achieve lower-cost travel.However, the airlines are aware of this behavior, and usually require that the travel covered by a ticket be completed in order and without intervening travel.
Example:
if you have a ticket for travel from City-1 to City-2 then to City-3, you are not allowed to use only the portion of the ticket for travel from City-2 to City-3. You must always start at the first city on the ticket. In addition, you are not allowed to travel from City-1 to City-2, fly elsewhere and return, and then continue your journey from City-2 to City-3.
Let’s consider an example. Suppose you are allowed to purchase three types of tickets:
Ticket #1: City-1 to City-3 to City-4 $225.00
Ticket #2: City-1 to City-2 $200.00
Ticket #3: City-2 to City-3 $50.00
Suppose you wanted to travel from City-1 to City-3. There are two ways to get there using only the available ticket choices:
Purchase Ticket #1 for $225.00 and use only the first leg of the ticket.
Purchase Ticket #2 for $200.00 and Ticket #3 for $50.
The first choice is the cheapest.
for a given a set of airline ticket offers, and one or more trip itineraries, write a program to determine how to purchase tickets in order to minimize the cost of travel. Each trip will be possible.
Input:
Input consists of multiple test cases, each describing a set of ticket offers and a set of trip itineraries.
Each case begins with a line containing NT, the number of ticket offers, followed by NT offer descriptions, one to a line.Each description consists of a positive integer specifying the price of the ticket, the number of cities in the ticket’s route, and then that many cities. Each city in a case has an arbitrary, but unique, integer identification number. Note that several tickets may be purchased from the same offer.
The next line contains NI, the number of trips that are to have their cost minimized. NI lines follow, giving the itineraries for each trip. Each line consists of the number of cities in the itinerary (including the starting city), followed by that many city identification numbers, given in the order they are to be visited.
There will be no more than 20 ticket offers or 20 itineraries in a test case. Each offer and itinerary lists from 2 to 10 cities. No ticket price exceeds $10,000. Adjacent cities in a route or itinerary will be distinct. Tickets and trips are numbered sequentially in each set, starting with 1.
The last case is followed by a line containing a zero.
Output
For each trip, output two lines containing the case number, the trip number, the minimum cost of the trip, and the numbers of the tickets used for the trip, in the order they will be used. Follow the output format shown below. The output will always be unique.
Sample Input:
3
225 3 1 3 4
200 2 1 2
50 2 2 3
1
2 1 3
3
100 2 2 4
100 3 1 4 3
200 3 1 2 3
2
3 1 4 3
3 1 2 4
0
Sample Output:
Case 1, Trip 1: Cost = 225
Tickets used: 1
Case 2, Trip 1: Cost = 100
Tickets used: 2
Case 2, Trip 2: Cost = 300
Tickets used: 3 1
Network
A packet-switching network handles information in small units, breaking long messages into multiple packets
before routing. Although each packet may travel along a different path, and the packets comprising a message
may arrive at different times or out of order, the receiving computer reassembles the original message correctly.
The receiving computer uses a buffer memory to hold packets that arrive out of order. You must write a
program that calculates the minimum buffer size in bytes needed to reassemble the incoming messages when the
number of messages (N), the number of packets (M), the part of the messages in each packet, the size of each
message, and the order of the incoming packets are given.
When each packet arrives, it may be placed into the buffer or moved directly to the output area. All packets that
are held in the buffer are available to be moved to the output area at any time. A packet is said to “pass the
buffer” when it is moved to the output area. A message is said to “pass the buffer” when all of its packets have
passed the buffer.
The packets of any message must be ordered so the data in the sequence of packets that pass the buffer is in
order. For example, the packet containing bytes 3 through 5 of a message must pass the buffer before the packet
containing bytes 6 through 10 of the same message. Messages can pass the buffer in any order, but all packets
from a single message must pass the buffer consecutively and in order (but not necessarily at the same time).
Note that unlike actual buffering systems, the process for this problem can look ahead at all incoming packets to
make its decisions.
The packets consist of data and header. The header contains three numbers: the message number, the starting
byte number of data in the packet, and the ending byte number of data in the packet respectively. The first byte
number in any message is 1.
For example, the figure below shows three messages (with sizes of 10, 20, and 5 bytes) and five packets. The
minimum buffer size for this example is 10 bytes. As they arrive, packet #1 and packet #2 are stored in the
buffer. They occupy 10 bytes. Then packet #3 passes the buffer directly. Packet #4 passes the buffer directly and
then packet #2 exits the buffer. Finally, packet #5 passes the buffer directly and packet #1 exits the buffer.
Input
The input contains several test cases. The first line of each test case contains two integers N (1 <= N <= 5) and
M (1 <= M <= 1000). The second line contains N integers that are the sizes of messages in bytes; the first number
denotes the size of message #1, the second number denotes the size of message #2, and so on. Each of the
following M lines describes a packet with three integers: the message number and the starting and ending byte
numbers of data in the packet. No packet contains more 64 bytes of data.
The last test case is followed by a line containing two zeroes.
Output
For each test case, print a line containing the test case number (beginning with 1) followed by the minimum
buffer size in bytes required to reassemble the original messages. Put a blank line after the output for each test
case. Use the format of the sample output.
Sample Input
3 3
5 5 5
1 1 5
2 1 5
3 1 5
3 5
10 20 5
2 16 20
1 6 10
3 1 5
1 1 5
2 1 15
0 0
Output for the Sample Input
Case 1: 0
Case 2: 10