| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 2118 | AGTC |
|
| 4003 | Your Ways |
|
| 4061 | My T-shirt suits me |
|
| 4068 | Squares |
|
| 4072 | Hotel booking |
|
Description
Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below:
Deletion: a letter in x is missing in y at a corresponding position.
Insertion: a letter in y is missing in x at a corresponding position.
Change: letters at corresponding positions are distinct
Certainly, we would like to minimize the number of all possible operations.
Illustration
A G T A A G T * A G G C
| | | | | | |
A G T * C * T G A C G C
Deletion: * in the bottom line
Insertion: * in the top line
Change: when the letters at the top and bottom are distinct
This tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we could be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like
A G T A A G T A G G C
| | | | | | |
A G T C T G * A C G C
and 4 moves would be required (3 changes and 1 deletion).
In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where n ≤ m.
Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.
Write a program that would minimize the number of possible operations to transform any string x into a string y.
Input
Input contains several datasets. Each dataset consists of the strings x and y prefixed by their respective lengths, one in each line.
Output
For each dataset, an integer representing the minimum number of possible operations to transform any string x into a string y.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You live in a small well-planned rectangular town in Phuket. The size of the central area of the town is H kilometers x W kilometers. The central area is divided into HW unit blocks, each of size 1 x 1 km2. There are H + 1 streets going in the West to East direction, and there are W + 1 avenue going in the North-South direction. The central area can be seen as a rectangle on the plane, as shown below.
We can identify each intersection by its co-ordinate on the plane. For example, on the Figure above the bottom-left corner is intersection (0,0), and the top-right corner is intersection (6,3).
Your house is at the bottom-left corner (i.e., intersection (0,0)) and you want to go to the university at the top-right corner (i.e., intersection (W,H)). More over, you only want to go to the university with wasting any efforts; therefore, you only want to walk from West-to-East and South-to-North directions. Walking this way, in the example above there are 84 ways to reach the university.
You want to go to the university for K days. Things get more complicated when each morning, the city blocks parts of streets and avenues to do some cleaning. The blocking is done in such a way that it is not possible to reach parts of the streets or avenues which is blocked from some other part which is blocked as well through any paths containing only West-to-East and South-to-North walks.
You still want to go to the university using the same West-to-East and South-to-North strategy. You want to find out for each day, how many ways you can reach the university by only walking West-to-East and South-to-North. Since the number can be very big, we only want the result modulo 2552.
Input
The first line contains an integer T, the number of test cases (1 < T < 5). Each test case is in the following format.
The first line of each test case contains 3 integers: W, H, and K (1 < W < 1,000; 1 < H < 1,000; 1 < K < 10,000). W and H specify the size of the central area. K denotes the number of days you want to go to the university.
The next K lines describe the information on broken parts of streets and avenues. More specifically, line 1 + i, for 1 < i < K, starts with an integer Qi (1 < Qi < 100) denoting the number of parts which are blocked. Then Qi sets of 4 integers describing the blocked parts follow. Each part is described with 4 integers, A, B, C, and D (0 < A < C < W; 0 < B < D < H) meaning that the parts connecting intersection (A,B) and (C,D) is blocked. It is guaranteed that that part is a valid part of the streets or avenues, also C - A < 1, and D - B < 1, i.e., the part is 1 km long.
Output
For each test case, for each day, your program must output the number of ways to go to the university modulo 2552 on a separate line. i.e., the output for each test case must contains K lines.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Our friend Victor participates as an instructor in an environmental volunteer program. His boss asked Victor to distribute N T-shirts to M volunteers, one T-shirt each volunteer, where N is multiple of six, and N>=M. There are the same number of T-shirts of each one of the six available sizes: XXL, XL, L, M , S, and XS. Victor has a little problem because only two sizes of the T-shirts suit each volunteer.
You must write a program to decide if Victor can distribute T-shirts in such a way that all volunteers get a T-shirt that suit them. If N != M, there can be some remaining T-shirts.
Input
The first line of the input contains the number of test cases. For each test case, there is a line with two numbers N and M. N is multiple of 6, 1<=N<=36, and indicates the number of T-shirts. Number M, 1<=M<=30, indicates the number of volunteers, with N>=M. Subsequently, M lines are listed where each line contains, separated by one space, the two sizes that suit each volunteer (XXL, XL, L, M , S, or XS).
Output
For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
For any positive integer N , N = a1
2 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.
Your task is to print the smallest `n ' such that N = a12 + a22 +...+ an2 .
Input
The first line of the input will contain an integer `t ' which indicates the number of test cases to follow.
Each test case will contain a single integer `N ' (1
N10000) on a line by itself.
Output
Print an integer which represents the smallest `n ' such that
N = a12 + a22 +...+ an2 .
Explanation for sample test cases:
5 - > number of test cases
1 = 12 (1 term)
2 = 12 + 12 (2 terms)
3 = 12 + 12 + 12 (3 terms)
1 = 22 (1 term)
2 = 52 + 52 (2 terms)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A transport company often needs to deliver goods from one city to another city. The transport company has made a special deal with a hotel chain which allows its drivers to stay in the hotels of this chain for free. Drivers are only allowed to drive up to 10 hours a day. The transport company wants to find a route from the starting city to the destination city such that a driver can always spend the night in one of the hotels of the hotel chain, and that he needs to drive at most 10 hours from one hotel to the next hotel (or the destination). Of course, the number of days needed to deliver the goods should also be minimized.
Input
The input file contains several test cases. Each test case starts with a line containing an integer n, (2 ≤ n ≤ 10000), the number of cities to be considered when planning the route. For simplicity, cities are numbered from 1 to n, where 1 is the starting city, and n is the destination city. The next line contains an integer h followed by the numbers c1, c2, ..., ch indicating the numbers of the cities where hotels of the hotel chain are located. You may assume that 0 ≤ h ≤ min(n, 100). The third line of each test case contains an integer m (1 ≤ m ≤ 105), the number of roads to be considered for planning the route. The following m lines describe the roads. Each road is described by a line containing 3 integers a, b, t (1 ≤ a, b ≤ n and 1 ≤ t ≤ 600), where a, b are the two cities connected by the road, and t is the time in minutes needed by the driver to drive from one end of the road to the other. Input is terminated by n = 0.
Output
For each test case, print one line containing the minimum number of hotels the transport company has to book for a delivery from city 1 to city n. If it is impossible to find a route such that the driver has to drive at most 10 hours per day, print -1 instead.