| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1303 | Time is Money! |
|
| 1304 | More Profit! |
|
| 1305 | Treasures of the Sea |
|
| 1306 | Energy Saver |
|
| 1307 | Gift Wrapping Algorithm for Convex Hull |
|
Description
Peter is an employee of certain company. Since the policy of company, his salary is related to the type of works and the corresponding time. For example, if Peter spent 2 hours in updating server, and company paid him $600 per hour, then he earned $1200.
Now you have the list of Peter's works, please compute Peter's salary.
Input
The first line is an integer T(<=100) meaning the number of test cases in the input file. In each test case, it begins with N, the number of works(N<=103), come up with N works' details, P TS TF. P(0
For simplicity, we assume that all works are done in one day, no durations cross two or more days. Moreover, the durations of any two works doesn't overlap each other and the time in one day is from 00:00 to 23:59. Besides, if the duration is less than one hour, we take this duration as if he works for an hour. For instance, a duration 1 hour and 23 minutes is counted as 2 hours.
Output
For each test case, output test case number and the salary in a line. There should be an empty line between two adjacent test cases.
See sample output for more details.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In some online games, property of character is important. One of the famous way to increase your money is commerce. More precisely, we can buy something in lower price and then sell it by higher price. Because of the difference between two prices, player can make money easily.
In Amusement Commerce Game, player can buy some items from a commerce port and sell it in a big city. There are many items that is sold by supplier and the amount of each item is limited. Moreover, player can put at most M items on character. Give the profit of each item, what is the maximum profit can achieve in a single journey from port to city?
Input
There is an integer T representing the number of test cases, which is followed by T test cases. Each test case begins with two integers N, M, and then the next N lines are N items' information. Each line has two numbers, n_i and p_i, representing the amount and the price per quantity for i_th item. You can assume that there are at most 1,000 cases and at most 10,000 items for each case. Also n_i and p_i are both non-negative integers.
Output
For each test case, output the maximum profit can be made. The maximum profit would not exceed 2,147,483,647.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Your friend, John, is a pirate. One day, he found a map marking the treasures of the sea, which described as following:
1. Like most maps in the world, the east is on the right-hand side of map.
2. The map splits the sea into grids, separated by vertical and horizontal lines.
3. For each grid, there is a non-negative number presenting how many treasures are there on the islands in the grid.
4. Any regions out of the map contain no treasure.
In this season, the wind blows from the north to the south. With the help of wind, John will drive his boat from the north of sea to the south. The boat can sail to east or west, but there are some limitations.
John will start his journey from any grids in the north side of the sea in map (any grid on the top of map). After gathering the treasures in the grid, there are 3 directions he can choose:
1. South. He will go down on the map.
2. Southeast. He will reach the grid on the right of choice 1.
3. Southwest. He will reach the grid on the left of choice 1.
As described above, there is no way to sail east, west, or north. After John sail out of the south grids on the grid, his journey will end.
Since John promised you to share half of the treasures he gets in the journey, you are to find out how may treasures you and John can get most if he chooses the path carefully.
Input
There will be multiple cases in the input.
The first line contains a positive integer T, T≦10, which denotes the number of cases.
The next line contains 2 positive integers, R and C (≦100), denoting the size of map for rows and columns. There are R lines following, denoting the rows from north to south, and each row contains C integers, which are the value of treasures in that grid(≦10000).
Values will be separated with spaces.
Output
For each case, output a line containing one integer denoting the maximum value of treasures John and you may get.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Welcome to NTHU Online Judge! You must notice the avenue planted with many streetlamps. Since energy issue is serious, NTHU decided to turn off some streetlamps. However, there are so many activities held in NTHU, sometimes we need more lights for safety, so a fixed setting is not flexible.
As a computer science student, Scott designed a system to control the setting of streetlamps. At first, he gave every streeplamps a number from 1, 2, 3, ..., and so on. There is a control panel with two lines of buttons, and the buttons each line are indexed from 1 to n provided that the total number of streeplamps is n. When Scott pushed a button on first line, e.g: i_th one, the status of i_th streetlamp changes. Changing status means that if a streetlamp is turn off, then it would be turned on, and vice versa. This kind of action is called "normal" push.
Another line of buttons is more powerful, called "toggle" push. If we toggle pushed the i_th button, then the status of streetlamps from the i_th streetlamp to the last(n_th) one would be changed. For example, if we toggle pushed 5th button, then the status of streetlamps with index 5, 6, ..., n will be changed.
Now we want to know how to minimize the total number of normal push and toggle push on buttons. Please write a program to help Scott. We assume that originally all streetlamps are turned off.
Input
The first line is the number of test cases. Each test case starts with an integer n and the next line are n integers v_1, v_2, ..., v_n. n(<=10^6) is the number of streeplamps, and v_i is i_th streeplamp status for final setting. v_i is either 0 or 1, 0 is turned off and 1 is turned on.
Output
For each test case, output the test case number and the minimum number of push. See sample for more details.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
On a 2D plane, there are N non-overlapping points. Consider a string which forms a large cycle and surrounds all of the N points. As we shorten the string, the cycle will become smaller and smaller. Since we have to surround all points, when the string can not be any shorter, the string will form a polygon, which is called the convex hull.
There is a simple way to find a convex hull of N points, which is the so call “gift wrapping algorithm.” We will show the steps as follows.
1. Consider the coordinates, and select the point with the smallest X. If there are multiple choices, select the one with the smallest Y. Let a point P denotes this point.
2. Set a vector D=(0,1), denote the “direction”.
3. For all the other points, find the point, Q, which forms the smallest angle, Θ, between direction D and direction PQ. Use a dot product D*PQ = |D||PQ|cosΘ, we can use the value of cosΘ to compare the angles of Θ for different Q. If there are more than one Qs form the same Θ, choose the one with the largest |PQ|.
4. Do step 3 continuously until the convex hull is closed (we reach the first point).
Hint: to get the square root, use the function:
double sqrt(double x)
in math.h
Input
There will be multiple cases in the input.
The first line contains a positive integer T, T≦100, which denotes the number of cases.
For each case, the first line contains an integers N ,2≦N≦1000, which is the number of points on the plane. There are N lines following, and each line contains 2 integers X and Y, which are the coordinates of that point. All coordinates are between -10000 and 10000.
Values will be separated with spaces.
Output
For each case, output a line containing one integer denoting the minimum number of points needed to form a convex hull to cover all points.