uestc-dp专题

M is a const number. Now Zero wants to know the minimum cost in order to arrange the article perfectly. Input

There are many test cases. For each test case, There are two numbers N and M in the first line (0<=n<=500000, 0<=m<=1000). Then, there are N numbers in the next lines. Input are terminated by EOF. Output

A single number, meaning the minimum cost to print the article. Sample Input 5 5 5 9 5 7 5 Sample Output 230 Source

2010 ACM-ICPC MU Training - Host by HIT

Robotruck

Time Limit: 3000 ms Memory Limit: 65536 kB

Solved: 43 Tried: 227

Description

This problem is about a robotic truck that distributes mail packages to several locations in a factory. The robot sits at the end of a conveyer at the mail office and waits for packages to be loaded into its cargo area. The robot has a maximum load capacity, which means that it may have to perform several round trips to complete its task. Provided that the maximum capacity is not exceeded, the robot can stop the conveyer at any time and start a round trip distributing the already collected packages. The packages must be delivered in the incoming order. The distance of a round trip is computed in a grid by measuring the number of robot moves from the mail office, at location (0,0), to the location of delivery of the first package, the number of moves between package delivery locations, until the last package, and then the number of moves

from the last location back to the mail office. The robot moves a cell at a time either horizontally or vertically in the factory plant grid. For example, consider four packages, to be delivered at the locations (1,2),(1,0), (3,1), and (3,1). By dividing these packages into two round trips of two packages each, the number of moves in the first trip is 3+2+1=6, and 4+0+4=8 in the second trip. Notice that the two last packages are delivered at the same location and thus the number of moves between them is 0.

Given a sequence of packages, compute the minimum distance the robot must travel to deliver all packages. Input

A positive integer P in a single line followed by a sequence of P test cases. Each test case consists of a line containing one positive integer C, not greater than 100, indicating the maximum capacity of the robot, a line containing one positive integer N, not greater than 100,000, which is the number of packages to be loaded from the conveyer. Next, there are N lines containing, for each package, two non-negative integers x,y(x<=1000,y<=1000) to indicate its delivery location in the grid, and a non-negative integer to indicate its weight. The weight of the packages is always smaller than the robot's maximum load capacity. The order of the input is the order of appearance in the conveyer. Output

One line containing the case number and one integer representing the minimum number of moves the robot must travel to deliver all the packages. Sample Input 1 10 4 1 2 3 1 0 3 3 1 4 3 1 4

Sample Output Case 1: 14 Source

Southwestern Europe 2007

Sum of Digits

Time Limit: 3000 ms Memory Limit: 65536 kB

Solved: 54 Tried: 349

Description

Petka thought of a positive integer n and reported to Chapaev the sum of its digits and the sum of its squared digits. Chapaev scratched his head and said: “Well, Petka, I won't find just your number, but I can find the smallest fitting number.” Can you do the same? Input

The first line contains the number of test cases t (no more than 10000). In each of the following tlines there are numbers s1 and s2 (1 ≤ s1, s2 ≤ 10000) separated by a space. They are the sum of digits and the sum of squared digits of the number n. Output

For each test case, output in a separate line the smallest fitting number n, or “No solution” if there is no such number or if it contains more than 100 digits.

Sample Input 4 9 81 12 9 6 10 7 9

Sample Output 9

No solution 1122 111112 Source

NEERC 2008, Eastern subregion quarterfin

Weights and Measures

Time Limit: 1000 ms Memory Limit: 65536 kB

Solved: 73 Tried: 889

Description

I know, up on top you are seeing great sights, But down at the bottom, we, too, should have rights. We turtles can't stand it. Our shells will all crack! Besides, we need food. We are starving!\

Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles

should be dispatched to form Yertle's throne. Each of the five thousand, six hundred and seven turtles ordered by Yertle has a different weight and strength. Your task is to build the largest stack of turtles possible.

The weight of the turtle is in grams. The strength, also in grams, is the turtle's overall carrying capacity, including its own weight. That is, a turtle weighing 300g with a strength of 1000g could carry 700g of turtles on its back. Input

There is only one test case in the input.

Standard input consists of several lines, each containing a pair of integers separated by one or more space characters, specifying the weight and strength of a turtle (w<=s).There are at most 5,607 turtles. Output

Your output is a single integer indicating the maximum number of turtles that can be stacked without exceeding the strength of any one.

Sample Input 300 1000 1000 1200 200 600 100 101 Sample Output 3 Source Liu Rujia