HDUOJ 2011冬季训练——全程测试

1002 Ropes

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 53Accepted Submission(s): 41

Problem Description

When climbing a section or “pitch”, the lead climber ascends first, taking a rope with them that they anchor to the rock for protection to ascend. Once at the top of a pitch, the lead climber has the second climber attach to the rope, so they can ascend with the safety of the rope. Once the second climber reaches the top of the pitch, the third attaches, and so on until all the climbers have ascended.
For example, for a 10 meter pitch and 50 meter rope, at most 6 climbers could ascend, with the last climber attaching to the end of the rope. To ascend safely, there must be at least 2 climbers and the rope must be at least as long as the pitch.
This process is repeated on each pitch of the climb, until the top is reached. Then to descend, the climbing rope is hung at its midpoint from an anchor (each half must reach the ground).
The climbers then each rappel from this rope. The rope is retrieved from the anchor by pulling one side of the rope, slipping it though the anchor and allowing it to fall to the ground.
To descend safely, the rope must be at least twice as long as the sum of the lengths of the pitches.
For example, a 60 meter rope is required to rappel from a 30 meter climb, no matter how many climbers are involved.
Climbing ropes come in 50, 60 and 70 meter lengths. It is best to take the shortest rope needed for a given climb because this saves weight. You are to determine the maximum number of climbers that can use each type of rope on a given climb.

Input

The input consists of a number of cases. Each case specifies a climb on a line, as a sequence of pitch lengths as in:
N P₁P₂... P_N
Here N is the positive number of pitches, with 1 ≤ N ≤ 100, and P_kis the positive integer length (in meters) of each pitch, with 1 ≤ P_k≤ 100. The last line (indicating the end of input) is a single 0.

Output

Three numbers for each climb separated by a space, indicating the maximum number of climbers that could use the 50, 60, or 70 meter rope lengths, respectively. State 0 if the given rope length is not suitable for that climb.

Sample Input

1 25
2 10 20
0

Sample Output

3 3 3
0 4 4
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iomanip>
using namespace std;
int a[105];
int main() {
	freopen("test.txt", "r", stdin);
	int n;
	while(cin>>n && n){
		memset(a,0,sizeof(a));
		int sum=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];sum+=a[i];
		}
		int m1=10000,m2=10000,m3=10000,ma1=10000,ma2=10000,ma3=10000;
		for(int i=1;i<=n;i++)
		{
			ma1=50/a[i];ma2=60/a[i];ma3=70/a[i];
			if(ma1<m1)m1=ma1;
			if(ma2<m2)m2=ma2;
			if(ma3<m3)m3=ma3;
		}
		m1++;m2++;m3++;
		cout<<((sum*2>50)?0:m1)<<" ";
		cout<<((sum*2>60)?0:m2)<<" ";
		cout<<((sum*2>70)?0:m3)<<endl;
	}
	return 0;
}

1005   Page Count
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 256Accepted Submission(s): 64


Problem Description
When you execute a word processor's print command, you are normally prompted to specify the pages you want printed. You might, for example, enter:

10-15,25-28,8-4,13-20,9,8-8
The expression you enter is a list of print ranges, separated by commas.

Each print range is either a single positive integer, or two positive integers separated by a hyphen. In the latter case we call the first integer low and the second one high. A print range for which low > high is simply ignored. A print range that specifies page numbers exceeding the number of pages is processed so that only the pages available in the document are printed. Pages are numbered starting from 1.

Some of the print ranges may overlap. Pages which are common to two or more print ranges will be printed only once. (In the example given, pages 13, 14 and 15 are common to two print ranges.)


Input
The input will contain data for a number of problem instances. For each problem instance there will be two lines of input. The first line will contain a single positive integer: the number of pages in the document. The second line will contain a list of print ranges, as defined by the rules stated above. End of input will be indicated by 0 for the number of pages. The number of pages in any book is at most 1000. The list of print ranges will be not be longer than 1000 characters.


Output
For each problem instance, the output will be a single number, displayed at the beginning of a new line. It will be the number of pages printed by the print command.


Sample Input

30
10-15,25-28,8-4,13-20,9,8-8
19
10-15,25-28,8-4,13-20,9,8-8
0



Sample Output

17
12


#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iomanip>
using namespace std;
struct node{
	int a,b;
};
string* ss = new string[1002];
set<int> si;
node check(string str){
	int len = str.length();
	int num = 0;node n;n.a = n.b = -1;
	for (int i = 0; i < len; i++) {
		if(str[i] != '-'){
			num = num *10 + str[i] - '0';
		}
		else{
			n.a = num;
			num = 0;
		}		
	}
	n.b = num;
	if(n.a > n.b) {
		n.a = 0,n.b = 0;
	}
	if(n.a < 0){
		n.a = n.b;
	}
	return n;
}
int doing(string str,int m) {
	int len = str.length();
	string sub = "";int j=0;
	for (int i = 0; i < len; i++) {
		if(str[i] == ','){
			ss[j] = sub;j++;sub = "";
		}
		else{
			sub += str[i];
		}
	}
	ss[j] = sub;
	for(int i=0;i<=j;i++){
		node n = check(ss[i]);
		if(n.a|n.b){
			for (int j =n.a;j<=n.b && j <= m;j++){
				si.insert(j);
			}
		}		
	}
	return si.size();
}
int main() {
	freopen("test.txt", "r", stdin);
	int n;char sss[1002];
	string sin;
	while (scanf("%d\n",&n) && n) {
		scanf("%s",sss);sin = sss;
		si.clear();
		printf("%d\n",doing(sin,n));
	}
	return 0;
}


1007   Railroad
Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 115Accepted Submission(s): 26


Problem Description
A train yard is a complex series of railroad tracks for storing, sorting, or loading/unloading railroad cars. In this problem, the railroad tracks are much simpler, and we are only interested in combining two trains into one.



Figure 1: Merging railroad tracks.

The two trains each contain some railroad cars. Each railroad car contains a single type of products identified by a positive integer up to 1,000,000. The two trains come in from the right on separate tracks, as in the diagram above. To combine the two trains, we may choose to take the railroad car at the front of either train and attach it to the back of the train being formed on the left. Of course, if we have already moved all the railroad cars from one train, then all remaining cars from the other train will be moved to the left one at a time. All railroad cars must be moved to the left eventually. Depending on which train on the right is selected at each step, we will obtain different arrangements for the departing train on the left. For example, we may obtain the order 1,1,1,2,2,2 by always choosing the top train until all of its cars have been moved. We may also obtain the order 2,1,2,1,2,1 by alternately choosing railroad cars from the two trains.

To facilitate further processing at the other train yards later on in the trip (and also at the destination), the supervisor at the train yard has been given an ordering of the products desired for the departing train. In this problem, you must decide whether it is possible to obtain the desired ordering, given the orders of the products for the two trains arriving at the train yard.


Input
The input consists of a number of cases. The first line contains two positive integers N1N2which are the number of railroad cars in each train. There are at least 1 and at most 1000 railroad cars in each train. The second line contains N1positive integers (up to 1,000,000) identifying the products on the first train from front of the train to the back of the train. The third line contains N2positive integers identifying the products on the second train (same format as above). Finally, the fourth line contains N1+N2positive integers giving the desired order for the departing train (same format as above).

The end of input is indicated by N1= N2= 0.


Output
For each case, print on a line possible if it ispossibleto produce the desired order, ornot possibleif not.


Sample Input

3 3
1 2 1
2 1 1
1 2 1 1 2 1
3 3
1 2 1
2 1 2
1 1 1 2 2 2
0 0



Sample Output

possible
not possible
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int s1[1005],s2[1005],ss[2005];

int n,m;
int ok;
int tmm;

void dfs(int t1,int t2,int tt){
     tmm++;
     if(tmm>5000000) return; //有限次数内完成不了，肯定impossible 
    //printf("%d %d %d\n",t1,t2,tt);
    if(ok) return;
    if(tt==n+m) {
        ok=1; return;
    }
    if(t1<n && s1[t1]==ss[tt]){
        dfs(t1+1, t2, tt+1);
    }
    if(t2<m && s2[t2]==ss[tt]){
        dfs(t1,t2+1,tt+1);
    }
}

int main(){
    while(scanf("%d%d",&n,&m)){
        if(n==0 && m==0) break;
        for(int i=0; i<n; i++) scanf("%d",&s1[i]);
        for(int i=0; i<m; i++) scanf("%d",&s2[i]);
        for(int i=0; i<n+m; i++) scanf("%d",&ss[i]);
        ok=0;
        tmm=0;
        dfs(0,0,0);      
        if(ok) printf("possible\n");
        else printf("not possible\n");                     
    }
}


#include <stdio.h>
#include <string.h>

#define MAXN 1010

int d[MAXN * 2], a[MAXN], b[MAXN];
bool dp[MAXN][MAXN];

int main() {
	int n, m;
	while(scanf("%d%d", &n, &m), n || m) {
		for(int i = 1; i <= n; ++i) scanf("%d", a + i);
		for(int j = 1; j <= m; ++j) scanf("%d", b + j);
		for(int i = 1; i <= n + m; ++i) scanf("%d", d + i);
		memset(dp, false, sizeof(dp));
		dp[0][0] = true;
		for(int i = 0; i <= n; ++i)
			for(int j = 0; j <= m; ++j)
				if(dp[i][j]) {
					if(i + 1 <= n && a[i + 1] == d[i + j + 1]) dp[i + 1][j] = true;
					if(j + 1 <= m && b[j + 1] == d[i + j + 1]) dp[i][j + 1] = true;
				}
		if(dp[n][m]) puts("possible");
		else puts("not possible");
	}
	return 0;
}

1008   Post Office
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 102Accepted Submission(s): 28


Problem Description
Other than postcards, the post office department of some country recognizes three classes of mailable items: letters, packets, and parcels. The three dimensions of a mailable item are called length, height and thickness, with length being the largest and thickness the smallest of the three dimensions.

A letter's length must be at least 125mm but not more than 290mm, its height at least 90mm but not more than 155mm, and its thickness at least 0.25mm but not more than 7mm. (The unit millimeter is abbreviated by mm.)

All three of a packet's dimensions must be greater than or equal to the corresponding minimum dimension for a letter, and at least one of its dimensions must exceed the corresponding maximum for a letter. Furthermore, a packet's length must be no more than 380mm, its height no more than 300mm, and its thickness no more than 50mm.

All three of a parcel's dimensions must be greater than or equal to the corresponding minimum dimension for a letter, and at least one of its dimensions must exceed the corresponding maximum for a packet. Furthermore, the parcel's combined length and girth may not exceed 2100mm. (The girth is the full perimeter measured around the parcel, perpendicular to the length.)


Input
The input will contain data for a number of problem instances. For each problem instance, the input will consist of the three dimensions (measured in mm) of an item, in any order. The length and width will be positive integers. The thickness will be either a positive integer or a positive floating point number. The input will be terminated by a line containing three zeros.


Output
For each problem instance, your program will classify the item asletter,packet,parcelornot mailable. This verdict will be displayed at the beginning of a new line, in lower case letters.


Sample Input

100 120 100
0.5 100 200
100 10 200
200 75 100
0 0 0



Sample Output

not mailable
letter
packet
parcel

#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iomanip>
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const double pi = acos(-1.0);
double d[3];
string rst[4] = {"letter", "packet", "parcel", "not mailable"};
int solve() {
	if (d[0] >= 0.25 && d[1] >= 90 && d[2] >= 125) {
		if (d[0] <= 7 && d[1] <= 155 && d[2] <= 290)
			return 0;
		else {
			if (d[0] <= 50 && d[1] <= 300 && d[2] <= 380)
				return 1;
			else if (d[2] + 2 * d[1] + 2 * d[0] <= 2100)
				return 2;
			else 
				return 3;
		}
	} 
	else {
		return 3;
	}
}
int main(){
	freopen("test.txt","r",stdin);
	
	while (cin>>d[0]>>d[1]>>d[2]) {
		cout<<"!@#@!#@#@!#\n\n\n";
		if (d[0] == 0 && d[1] == 0 && d[2] == 0)break;
		sort(d, d + 3);
		cout << rst[solve()] << endl;
	}
	return 0; 
}