51isoft's ACM Journey

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  5 随笔 :: 0 文章 :: 0 评论 :: 0 Trackbacks

2009年7月28日 #

     摘要: Sudoku Time Limit: 10000MS Memory Limit: 65536K Total Submissions: 638 ...  阅读全文
posted @ 2009-07-28 02:37 51isoft 阅读(1453) | 评论 (0)编辑 收藏

2008年11月13日 #


Problem Statement


In a typical filesystem, there are files, representing complete units of data. These files are contained in directories, and these directories, in turn, may be contained in other directories, and so on. A path is a pointer to a specific file or directory in this stucture. Most Unix-like OSes have a single root directory, that has all other directories and files directly or indirectly (via other directories) inside it. Such OSes use the following structure for file paths:


and, correspondingly, the following structure for directory paths:


For example, "/etc/passwd" (all quotes here and below are for clarity only) points to a file named "passwd" inside a directory named "etc" inside the root directory. Other valid file names might be "/home/user/pictures/me" or just "/file". In this problem, we allow only nonempty sequences of lowercase letters ('a'-'z') as file and directory names.

A special case is the root directory itself, which is referred to as just "/".

When a user works with such an OS, one of the directories is chosen as 'current'. Such a designation allows her to refer to the files in that directory without specifying the full path to the current directory. For example, if the current directory is "/home/user/pictures", then one might refer to the file "/home/user/pictures/me" as just "me" (note that such a short form can be easily spotted by the absence of the starting '/' character). Moreover, the files in subdirectories of the current directory can also be referred to in a short manner: "/home/user/pictures/others/she" can be referred to as "others/she".

And even more exciting is the ability to have short references for files outside the current folder. More specifically, ".." means "the directory one level above the current directory", "../.." means "the directory two levels above the current directory", and so on. For example, if the current directory is "/home/user/pictures", and you want to refer to "/home/top/data/file", you can express that as "../../top/data/file".

Given a String path, indicating the complete path to the file that needs to be referred to, and a String currentDir, indicating the current directory, return a String that contains the relative path to that file according to the above rules. You should choose the shortest of all possible relative paths (for example, if the current directory is "/home/user/pictures", you should use "../movies/title" and not "../../user/movies/title" as a pointer to "/home/user/movies/title").

Some files and/or directories may have coinciding names, but it is impossible to have two files or two directories or a file and a directory with the same name inside the same directory, so file and directory paths are not ambiguous. It is guaranteed that the given data describes a valid file and directory according to the above rules. In particular, they will not contradict - for example, path="/home/user/some" and currentDir="/home/user/some/other" are a contradiction, since it implies that a file and a directory both named "some" exist inside the directory "/home/user".



Class: RelativePath
Method: makeRelative
Parameters: String, String
Returns: String
Method signature: String makeRelative(String path, String currentDir)
(be sure your method is public)



- A file name never ends with the '/' character. A directory name never ends with the '/' character, with the exception of the root directory, which is specified as just "/".


- path and currentDir will each contain between 1 and 50 characters, inclusive.
- Each character of path and currentDir will be '/', or a lowercase letter ('a'-'z').
- path will contain a valid file path according to the above rules.
- currentDir will contain a valid directory path according to the above rules.
- path and currentDir will not contradict (see the last paragraph of the statement).


Returns: "../../top/data/file"
The example from the problem statement.
Returns: "../movies/title"
And another one from the statement.
Returns: "file"
Remember about the root directory.
Returns: "../../../../b/a/b"
Some file and directory names may be the same.
Returns: "root/root"
Some files and/or directories can be named "root" - but that doesn't make them root directories.

#include <vector>

using namespace std;

class RelativePath {
string makeRelative(stringstring);

string RelativePath::makeRelative(string path, string cD) {
int sz1=path.size();
int sz2=cD.size();
int td1=0;
int td2=0;
int i;
int cloc,cdepth=0,tmp;
string ret="";
for (i=0;i<sz1;i++if (path[i]=='/') td1++;
if (sz1==1) td1=0;
for (i=0;i<sz2;i++if (cD[i]=='/') td2++;
if (sz2==1) td2=0;
for (i=0;i<sz2;i++)
if (path[i]!=cD[i]) break;
if (path[i]=='/') cdepth++;
if (i==sz2&&sz2<sz1&&path[sz2]!='/') cdepth--;
if (i!=sz2) cdepth--;
if (i==0||sz2==1) cdepth=0;
for (i=0;i<td2-cdepth;i++) ret+="../";
for (i=0;i<sz1&&tmp<cdepth;i++)
if (path[i]=='/') tmp++;
return ret;

//Powered by [KawigiEdit] 2.0!

posted @ 2008-11-13 20:37 51isoft 阅读(262) | 评论 (0)编辑 收藏

2008年9月18日 #


Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.

John's parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.


The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.


The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

Sample Input

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10

Sample Output

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1
0: 2
1: 2
2: 2
3: 2
4: 2


As the example illustrates, toys that fall on the boundary of the box are "in" the box.




#include <stdio.h>

int n,m,x1,y1,x2,y2,x,y;
int loc[5000][2];
double a[5000],b[5000];
int num[5001];

int i,j;
double v1,v2;
bool pd;

int main()
while (scanf("%d",&n)&&n)
if (m!=0) printf("\n");
        scanf (
"%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);
for (i=0;i<n;i++)
"%d %d",&loc[i][0],&loc[i][1]);

for (i=0;i<m;i++)
"%d %d",&x,&y);
for (j=0;j<n;j++)
if (x>loc[j][0]&&x>loc[j][1]) continue;
if (v1*v2>0{


if (!pd) num[n]++;

for (i=0;i<=n;i++)
"%d: %d\n",i,num[i]);

return 0;

posted @ 2008-09-18 17:45 51isoft 阅读(1079) | 评论 (0)编辑 收藏

     摘要: Description The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, a...  阅读全文
posted @ 2008-09-18 17:31 51isoft 阅读(1472) | 评论 (0)编辑 收藏

Problem Description
The Association of Chess Monsters (ACM) is planning their annual team match up against the rest of the world. The match will be on 30 boards, with 15 players playing white and 15 players playing black. ACM has many players to choose from, and they try to pick the best team they can. The ability of each player for playing white is measured on a scale from 1 to 100 and the same for playing black. During the match a player can play white or black but not both. The value of a team is the total of players' abilities to play white for players designated to play white and players' abilities to play black for players designated to play black. ACM wants to pick up a team with the highest total value.

Input consists of a sequence of lines giving players' abilities. Each line gives the abilities of a single player by two integer numbers separated by a single space. The first number is the player's ability to play white and the second is the player's ability to play black. There will be no less than 30 and no more than 1000 lines on input.

Output a single line containing an integer number giving the value of the best chess team that ACM can assemble.

Sample Input
87 84
66 78
86 94
93 87
72 100
78 63
60 91
77 64
77 91
87 73
69 62
80 68
81 83
74 63
86 68
53 80
59 73
68 70
57 94
93 62
74 80
70 72
88 85
75 99
71 66
77 64
81 92
74 57
71 63
82 97
76 56

Sample Output



#include <stdio.h>

int f[2000][16][16];
int a[2000][2];
int n;

int i,j,k;

int main()

while (scanf("%d %d",&a[n][0],&a[n][1])!=EOF) n++;
for (i=1;i<16;i++) f[0][0][i]=a[0][1];
for (i=1;i<16;i++) f[0][i][0]=a[0][0];
for (i=1;i<n;i++)
for (j=0;j<16;j++)
for (k=0;k<16;k++)
if (j==0) f[i][1][k]=f[i-1][0][k]+a[i][0];
if (k==0) f[i][j][1]=f[i-1][j][0]+a[i][1];
if (j!=0
if (f[i-1][j-1][k]+a[i][0]>f[i-1][j][k]) 
if (f[i][j][k]<f[i-1][j-1][k]+a[i][0]) f[i][j][k]=f[i-1][j-1][k]+a[i][0]; 

else if (f[i][j][k]<f[i-1][j][k]) f[i][j][k]=f[i-1][j][k];
if (k!=0
if (f[i-1][j][k-1]+a[i][1]>f[i-1][j][k]) 
if (f[i][j][k]<f[i-1][j][k-1]+a[i][1]) f[i][j][k]=f[i-1][j][k-1]+a[i][1]; 

else if (f[i][j][k]<f[i-1][j][k]) f[i][j][k]=f[i-1][j][k];



return 0;

posted @ 2008-09-18 17:20 51isoft 阅读(815) | 评论 (0)编辑 收藏