Door Man

Introduction

You are a butler in a large mansion. This mansion has so many rooms that they are merely referred to by number (room 0, 1, 2, 3, etc...). Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house. Over the years, you have mastered the art of traveling in a single path through the sloppy rooms and closing the doors behind you. Your biggest problem is determining whether it is possible to find a path through the sloppy rooms where you:

Always shut open doors behind you immediately after passing through

Never open a closed door

End up in your chambers (room 0) with all doors closed

In this problem, you are given a list of rooms and open doors between them (along with a starting room). It is not needed to determine a route, only if one is possible.
Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

Start line - A single line, "START M N", where M indicates the butler's starting room, and N indicates the number of rooms in the house (1 <= N <= 20).

Room list - A series of N lines. Each line lists, for a single room, every open door that leads to a room of higher number. For example, if room 3 had open doors to rooms 1, 5, and 7, the line for room 3 would read "5 7". The first line in the list represents room 0. The second line represents room 1, and so on until the last line, which represents room (N - 1). It is possible for lines to be empty (in particular, the last line will always be empty since it is the highest numbered room). On each line, the adjacent rooms are always listed in ascending order. It is possible for rooms to be connected by multiple doors!

End line - A single line, "END"

Following the final data set will be a single line, "ENDOFINPUT".

Note that there will be no more than 100 doors in any single data set.
Output

For each data set, there will be exactly one line of output. If it is possible for the butler (by following the rules in the introduction) to walk into his chambers and close the final open door behind him, print a line "YES X", where X is the number of doors he closed. Otherwise, print "NO".
Sample Input

START 1 2
1

END
START 0 5
1 2 2 3 3 4 4

END
START 0 10
1 9
2
3
4
5
6
7
8
9

END
ENDOFINPUT
Sample Output

YES 1
NO
YES 10

题目类型：欧拉回路的判定

算法分析：使用stringstream将读入的数据构建一个度数表，然后按照判断欧拉回路和欧拉路径的方法直接判断即可。注意输入的格式和方法

Domino Effect

Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase domino effect'' comes from).

While this is somewhat pointless with only a few dominoes, some people went to the opposite extreme in the early Eighties. Using millions of dominoes of different colors and materials to fill whole halls with elaborate patterns of falling dominoes, they created (short-lived) pieces of art. In these constructions, usually not only one but several rows of dominoes were falling at the same time. As you can imagine, timing is an essential factor here.

It is now your task to write a program that, given such a system of rows formed by dominoes, computes when and where the last domino falls. The system consists of several key dominoes'' connected by rows of simple dominoes. When a key domino falls, all rows connected to the domino will also start falling (except for the ones that have already fallen). When the falling rows reach other key dominoes that have not fallen yet, these other key dominoes will fall as well and set off the rows connected to them. Domino rows may start collapsing at either end. It is even possible that a row is collapsing on both ends, in which case the last domino falling in that row is somewhere between its key dominoes. You can assume that rows fall at a uniform rate.
Input

The input contains descriptions of several domino systems. The first line of each description contains two integers: the number n of key dominoes (1 <= n < 500) and the number m of rows between them. The key dominoes are numbered from 1 to n. There is at most one row between any pair of key dominoes and the domino graph is connected, i.e. there is at least one way to get from a domino to any other domino by following a series of domino rows.

The following m lines each contain three integers a, b, and l, stating that there is a row between key dominoes a and b that takes l seconds to fall down from end to end.

Each system is started by tipping over key domino number 1.

The input ends with an empty system (with n = m = 0), which should not be processed.
Output

For each case output a line stating the number of the case (System #1', System #2', etc.). Then output a line containing the time when the last domino falls, exact to one digit to the right of the decimal point, and the location of the last domino falling, which is either at a key domino or between two key dominoes. Adhere to the format shown in the output sample. If you find several solutions, output only one of them. Output a blank line after each system.
Sample Input

2 1
1 2 27
3 3
1 2 5
1 3 5
2 3 5
0 0

Sample Output

System #1
The last domino falls after 27.0 seconds, at key domino 2.

System #2
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.

题目类型：单源最短路

算法分析：题目所求的最后倒下的牌分两种情况：1最后倒下的牌是关键牌，所用时间是从源点1开始求得的最短路径中最大值。2最后倒下的牌是普通牌，所用时间是某一边邻接的两个节点的最短路径值和该边权之和的一半。推导过程：假设有dis[i]、dis[j]和edge[i][j] < INF。其中存在dis[i] < dis[j]，则该边倒下的时间是dis[j] + [edge[i][j] – (dis[j] – dis[i])] / 2。化简为(dis[i] + dis[j] + edge[i][j]) / 2。最后求得上述的两个时间，比较大小并输出相应情况的解

Risk

Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world map broken up into hypothetical countries. During a player's turn, armies stationed in one country are only allowed to attack only countries with which they share a common border. Upon conquest of that country, the armies may move into the newly conquered country.

During the course of play, a player often engages in a sequence of conquests with the goal of transferring a large mass of armies from some starting country to a destination country. Typically, one chooses the intervening countries so as to minimize the total number of countries that need to be conquered. Given a description of the gameboard with 20 countries each with between 1 and 19 connections to other countries, your task is to write a function that takes a starting country and a destination country and computes the minimum number of countries that must be conquered to reach the destination. You do not need to output the sequence of countries, just the number of countries to be conquered including the destination. For example, if starting and destination countries are neighbors, then your program should return one.

The following connection diagram illustrates the sample input.
Input

Input to your program will consist of a series of country configuration test sets. Each test set will consist of a board description on lines 1 through 19. The representation avoids listing every national boundary twice by only listing the fact that country I borders country J when I < J. Thus, the Ith line, where I is less than 20, contains an integer X indicating how many "higher-numbered" countries share borders with country I, then X distinct integers J greater than I and not exceeding 20, each describing a boundary between countries I and J. Line 20 of the test set contains a single integer (1 <= N <= 100) indicating the number of country pairs that follow. The next N lines each contain exactly two integers (1 <= A,B <= 20; A!=B) indicating the starting and ending countries for a possible conquest.

There can be multiple test sets in the input; your program should continue reading and processing until reaching the end of file. There will be at least one path between any two given countries in every country configuration.
Output

For each input set, your program should print the following message "Test Set #T" where T is the number of the test set starting with 1. The next NT lines each will contain the result for the corresponding test in the test set - that is, the minimum number of countries to conquer. The test result line should contain the start country code A the string " to " the destination country code B ; the string ": " and a single integer indicating the minimum number of moves required to traverse from country A to country B in the test set. Following all result lines of each input set, your program should print a single blank line.
Sample Input

1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
Sample Output

Test Set #1
1 to 20: 7
2 to 9: 5
19 to 5: 6
18 to 19: 2
16 to 20: 2

题目类型：全源最短路(Floyd)

算法分析：直接将读入的数据建成一个无向图，每个边的权值为1，然后调用一次Floyd算法计算全源最短路，然后对于每一个查询，直接输出edge数组中相应的值即可。本题中要求的征服城市的数量(包括目标城市)其实等于求路径中边的数量，也就是求边权为1的最短路，当然本题也可以使用BFS求解，只不过对于每一个查询都要调用一次BFS

Swordfish

There exists a world within our world
A world beneath what we call cyberspace.
A world protected by firewalls,

passwords and the most advanced
security systems. 阅读全文 »

Arbitrage

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

Input Specification

The input file will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name c_i of a source currency, a real number r_ij which represents the exchange rate from c_ito c_j and a name c_j of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

Output Specification

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

Sample Input

3USDollarBritishPoundFrenchFranc3USDollar 0.5 BritishPoundBritishPound 10.0 FrenchFrancFrenchFranc 0.21 USDollar 3USDollarBritishPoundFrenchFranc6USDollar 0.5 BritishPoundUSDollar 4.9 FrenchFrancBritishPound 10.0 FrenchFrancBritishPound 1.99 USDollarFrenchFranc 0.09 BritishPoundFrenchFranc 0.19 USDollar 0

Sample Output

Case 1: YesCase 2: No

题目类型：最长回路

算法分析：调用n次bellman-ford算法计算每一点为源点的最长回路(乘积)，对于长度大于1.0的情况直接可以判断出出现套汇

Stockbroker Grapevine

Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way.

Unfortunately for you, stockbrokers only trust information coming from their ��trusted sources��. This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information.

Your program will input data for different sets of stockbrokers. Each set starts with a line with the number of stockbrokers. Following this is a line for each stockbroker which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the message to each person. The format of each stockbroker line is as follows: The line starts with the number of contacts (n), followed by n pairs of integers, one pair for each contact. Each pair lists first a number referring to the contact (e.g. a ��1�� means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules. For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes.

Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input file is terminated by a set of stockbrokers containing 0 (zero) people.

It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message ��disjoint��'. Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all.
SAMPLE INPUT

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0

SAMPLE OUTPUT

3 2
3 10

题目类型：全源最短路(Floyd)

算法分析：使用Floyd算法计算一次全源最短路，然后对于每一个节点求得该节点到其他所有节点(可达)的最大距离，然后直接输出所有最大距离中的最小值和该节点的编号。判断有向图中存在不可达节点的方法是判断edge[i][j]和edge[j][i]是否同时为INF，如果是则说明图中存在不可达的节点。注意不要使用程序定义的INF常变量进行加法运算，因为容易溢出而导致WA！！！

Gene Assembly

Statement of the Problem

With the large amount of genomic DNA sequence data being made available, it is becoming more important to find genes (parts of the genomic DNA which are responsible for the synthesis of proteins) in these sequences. It is known that for eukaryotes (in contrast to prokaryotes) the process is more complicated, because of the presence of junk DNA that interrupts the coding region of genes in the genomic sequence. That is, a gene is composed by several pieces (called exons) of coding regions. It is known that the order of the exons is maintained in the protein synthesis process, but the number of exons and their lengths can be arbitrary.

Most gene finding algorithms have two steps: in the first they search for possible exons; in the second they try to assemble a largest possible gene, by finding a chain with the largest possible number of exons. This chain must obey the order in which the exons appear in the genomic sequence. We say that exon i appears before exon j if the end of i precedes the beginning of j.

The objective of this problem is, given a set of possible exons, to find the chain with the largest possible number of exons that cound be assembled to generate a gene.

Input Format

Several input instances are given. Each instance begins with the number 0 < n < 1000 of possible exons in the sequence. Then, each of the next n lines contains a pair of integer numbers that represent the position in which the exon starts and ends in the genomic sequence. You can suppose that the genomic sequence has at most 50000 basis. The input ends with a line with a single 0.

Output Format

For each input instance your program should print in one line the chain with the largest possible number of exons, by enumerating the exons in the chain. If there is more than one chain with the same number of exons, your program can print anyone of them.

Sample Input

6
340 500
220 470
100 300
880 943
525 556
612 776
3
705 773
124 337
453 665
0

Sample Output

3 1 5 6 4
2 3 1

题目类型：贪心

算法分析：这是一道经典的任务调度问题，先按任务的结束时间递减排序，再逐个选择，选择活动的起始时间大于已选择活动的结束时间，最后输出选择的活动的id即可

Web Navigation

Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. In this problem, you are asked to implement this.

The following commands need to be supported:

BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page. If the backward stack is empty, the command is ignored.

FORWARD: Push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page. If the forward stack is empty, the command is ignored.

VISIT <url>: Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied.

QUIT: Quit the browser.

Assume that the browser initially loads the web page at the URL http://www.acm.org/
This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.
Input

Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 70 characters. You may assume that no problem instance requires more than 100 elements in each stack at any time. The end of input is indicated by the QUIT command.

Output

For each command other than QUIT, print the URL of the current page after the command is executed if the command is not ignored. Otherwise, print "Ignored". The output for each command should be printed on its own line. No output is produced for the QUIT command.

Sample Input

1

VISIT http://acm.ashland.edu/
VISIT http://acm.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT http://www.ibm.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

Sample Output

http://acm.ashland.edu/
http://acm.baylor.edu/acmicpc/
http://acm.ashland.edu/
http://www.acm.org/
Ignored
http://acm.ashland.edu/
http://www.ibm.com/
http://acm.ashland.edu/
http://www.acm.org/
http://acm.ashland.edu/
http://www.ibm.com/
Ignored

题目类型：简单栈模拟

算法分析：直接按照题目所说的方式进行栈模拟即可

1076: 小W喜欢的数字

题目描述

大家都知道，小W是一名大帅哥，当然比起Light还是有点儿差距的！帅气的小W认为0-9这些数字，只有1,3,5是完美的。

欲问小W为什么，小W总是说“帅哥，是不需要解释的”.所以在帅哥小W的世界里， 阅读全文 »