uva122

maksyuki 发表于 oj 分类,标签:
0

Trees are fundamental in many branches of computer science (Pun definitely intended). Current stateof-the art parallel computers such as Thinking Machines’ CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics.

This problem involves building and traversing binary trees.

Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes.

In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k + 1.

For example, a level order traversal of the tree on the right is: 5, 4, 8, 11, 13, 4, 7, 2, 1.

In this problem a binary tree is specified by a sequence of pairs ‘(n,s)’ where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of ‘L’s and ‘R’s where ‘L’ indicates a left branch and ‘R’ indicates a right branch. In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once.

Input

The input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs ‘(n,s)’ as described above separated by whitespace. The last entry in each tree is ‘()’. No whitespace appears between left and right parentheses.

All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes. Input is terminated by end-of-file.

Output

For each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ‘not complete’ should be printed.

Sample Input

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

Sample Output

5 4 8 11 13 4 7 2 1

not complete

 

题目类型:二叉树遍历

算法分析:首先应该先建树,然后按照题目的要求边读入数据,边向二叉树添加节点。对于没有的子节点则创建一个节点,有子节点的则直接移动到其子节点中,直到输入命令结束。判断所在的节点是否已经赋过值了,如果已经赋过值了就置合法标志valid为false。接着使用BFS遍历建好的二叉树并将节点的值赋值到输出数组中,对于没有赋过值的节点,则将valid标志置为false并break

 

uva679

maksyuki 发表于 oj 分类,标签:
0

A number of K balls are dropped one by one from the root of a fully binary tree structure FBT. Each time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows the path of the left subtree, or follows the path of the right subtree, until it stops at one of the leaf nodes of FBT. To determine a ball’s moving direction a flag is set up in every non-terminal node with two values, either false or true. Initially, all of the flags are false. When visiting a non-terminal node if the flag’s current value at this node is false, then the ball will first switch this flag’s value, i.e., from the false to the true, and then follow the left subtree of this node to keep moving down. Otherwise, it will also switch this flag’s value, i.e., from the true to the false, but will follow the right subtree of this node to keep moving down. Furthermore, all nodes of FBT are sequentially numbered, starting at 1 with nodes on depth 1, and then those on depth 2, and so on. Nodes on any depth are numbered from left to right.

For example, Fig. 1 represents a fully binary tree of maximum depth 4 with the node numbers 1, 2, 3, ..., 15. Since all of the flags are initially set to be false, the first ball being dropped will switch flag’s values at node 1, node 2, and node 4 before it finally stops at position 8. The second ball being dropped will switch flag’s values at node 1, node 3, and node 6, and stop at position 12. Obviously, the third ball being dropped will switch flag’s values at node 1, node 2, and node 5 before it stops at position 10.

Now consider a number of test cases where two values will be given for each test. The first value is D, the maximum depth of FBT, and the second one is I, the I-th ball being dropped. You may assume the value of I will not exceed the total number of leaf nodes for the given FBT.

Please write a program to determine the stop position P for each test case.

For each test cases the range of two parameters D and I is as below:

2 ≤ D ≤ 20, and 1 ≤ I ≤ 524288.

Input

Contains l + 2 lines.

Line 1 l the number of test cases

Line 2 D1 I1 test case #1, two decimal numbers that are separated by one blank

...

Line k + 1 Dk Ik test case #k

Line l + 1 Dl Il test case #l

Line l + 2 -1 a constant ‘-1’ representing the end of the input file

Output

Contains l lines.

Line 1 the stop position P for the test case #1

...

Line k the stop position P for the test case #k

...

Line l the stop position P for the test case #l

Sample Input

5
4 2
3 4
10 1
2 2
8 128
-1
Sample Output

12

7

512

3

255

 

题目类型:二叉树查找

算法分析:由于每个节点具有开关属性,则当标号k为奇数时其为走左子树的第(k+1)/2个节点(也即其在左子树中的顺序标号),否则为走右子树的第k/2个节点,一共走D-1次

 

uva12657

maksyuki 发表于 oj 分类,标签:
0

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands:

• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )

• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )

• 3 X Y : swap box X and Y

• 4: reverse the whole line.

Commands are guaranteed to be valid, i.e. X will be not equal to Y .

For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1. Then after executing 4, then line becomes 1 3 5 4 6 2

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m (1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.

Sample Input

6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4

Sample Output

Case 1: 12

Case 2: 9

Case 3: 2500050000

 

题目类型:双重链表

算法分析:使用left[x]表示x的左边节点标号,right[x]表示x的右边节点标号,之后按照题目模拟即可。注意答案可能超出int的范围

 

uva442

maksyuki 发表于 oj 分类,标签:
0

Suppose you have to evaluate an expression like A*B*C*D*E where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose.

For example, let A be a 50*10 matrix, B a 10*20 matrix and C a 20*5 matrix. There are two different strategies to compute A*B*C, namely (A*B)*C and A*(B*C).

The first one takes 15000 elementary multiplications, but the second one only 3500.

Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.

Input

Input consists of two parts: a list of matrices and a list of expressions.

The first line of the input file contains one integer n (1 ≤ n ≤ 26), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.

The second part of the input file strictly adheres to the following syntax (given in EBNF):

SecondPart = Line { Line }

Line = Expression

Expression = Matrix | "(" Expression Expression ")"

Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

Output

For each expression found in the second part of the input file, print one line containing the word ‘error’ if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.

Sample Input

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

Sample Output

0

0

0

error

10000

error

3500

15000

40500

47500

15125

 

题目类型:表达式计算(栈模拟)

算法分析:使用栈来模拟计算矩阵表达式

 

 

uva514

maksyuki 发表于 oj 分类,标签:
0

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N ≤ 1000 coaches numbered in increasing order 1, 2, . . . , N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1.a2, . . . , aN . Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

Input

The input file consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, . . . , N. The last line of the block contains just ‘0’. The last block consists of just one line containing ‘0’.

Output

The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains ‘Yes’ if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains ‘No’. In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last “null” block of the input file.

Sample Input

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

Sample Output

Yes

No

 

Yes

 

题目类型:栈模拟

算法分析:使用一个Stack数组表示序列中数的情况,Stack[i] == 0表示i元素还没有入栈;Stack[i] == 1表示i元素在栈内;Stack[i] == 2表示i元素已经出栈。边输入边处理:维护一个合法标志valid,初始时valid置为true。读入一个元素a,判断比a大的元素是否还有在栈中的,如果还有则valid置为false;如果判断完之后valid仍为true,则更新在栈中的最大值元素maxval,a出栈并将小于a的所有还没有入栈的元素都压入栈中。另一个解法是考虑每个元素进入栈中只有两种操作:(1)进栈然后出栈(2)进栈然后暂不出栈。也即存在进栈,立即出栈和暂缓出栈三种方式。依次考察出栈序列的每个元素并判断。下面第一份代码是更好的实现

 

uva12504

maksyuki 发表于 oj 分类,标签: ,
0

In this problem, a dictionary is collection of key-value pairs, where keys are lower-case letters, and values are non-negative integers. Given an old dictionary and a new dictionary, find out what were changed.

Each dictionary is formatting as follows:

{key:value,key:value,...,key:value}

Each key is a string of lower-case letters, and each value is a non-negative integer without leading zeros or prefix ‘+’. (i.e. -4, 03 and +77 are illegal). Each key will appear at most once, but keys can appear in any order.

Input

The first line contains the number of test cases T (T ≤ 1000). Each test case contains two lines. The first line contains the old dictionary, and the second line contains the new dictionary. Each line will contain at most 100 characters and will not contain any whitespace characters. Both dictionaries could be empty.

WARNING: there are no restrictions on the lengths of each key and value in the dictionary. That means keys could be really long and values could be really large.

Output

For each test case, print the changes, formatted as follows:

• First, if there are any new keys, print ‘+’ and then the new keys in increasing order (lexicographically), separated by commas.

• Second, if there are any removed keys, print ‘-’ and then the removed keys in increasing order (lexicographically), separated by commas.

• Last, if there are any keys with changed value, print ‘*’ and then these keys in increasing order (lexicographically), separated by commas.

If the two dictionaries are identical, print ‘No changes’ (without quotes) instead. Print a blank line after each test case.

Sample Input

3
{a:3,b:4,c:10,f:6}
{a:3,c:5,d:10,ee:4}
{x:1,xyz:123456789123456789123456789}
{xyz:123456789123456789123456789,x:1}
{first:1,second:2,third:3}
{third:3,second:2}

Sample Output

+d,ee

-b,f

*c

 

No changes

 

-first

 

题目类型:简单字符处理+二分搜索

算法分析:使用map<string, string>ma[2]分别表示旧和新字典,然后直接循环判断。注意解析字符串的方法和字典可能是空的

 

uva1597

maksyuki 发表于 oj 分类,标签: ,
0

The word “search engine” may not be strange to you. Generally speaking, a search engine searches the web pages available in the Internet, extracts and organizes the information and responds to users’ queries with the most relevant pages. World famous search engines, like GOOGLE, have become very important tools for us to use when we visit the web. Such conversations are now common in our daily life:

“What does the word like ∗ ∗ ∗ ∗ ∗∗ mean?”

“Um. . . I am not sure, just google it.”

In this problem, you are required to construct a small search engine. Sounds impossible, does it? Don’t worry, here is a tutorial teaching you how to organize large collection of texts efficiently and respond to queries quickly step by step. You don’t need to worry about the fetching process of web pages, all the web pages are provided to you in text format as the input data. Besides, a lot of queries are also provided to validate your system.

Modern search engines use a technique called inversion for dealing with very large sets of documents. The method relies on the construction of a data structure, called an inverted index, which associates terms (words) to their occurrences in the collection of documents. The set of terms of interest is called the vocabulary, denoted as V . In its simplest form, an inverted index is a dictionary where each search key is a term ω ∈ V . The associated value b(ω) is a pointer to an additional intermediate data structure, called a bucket. The bucket associated with a certain term ω is essentially a list of pointers marking all the occurrences of ω in the text collection. Each entry in each bucket simply consists of the document identifier (DID), the ordinal number of the document within the collection and the ordinal line number of the term’s occurrence within the document.

Let’s take Figure-1 for an example, which describes the general structure. Assuming that we only have three documents to handle, shown at the right part in Figure-1; first we need to tokenize the text for words (blank, punctuations and other non-alphabetic characters are used to separate words) and construct our vocabulary from terms occurring in the documents. For simplicity, we don’t need to consider any phrases, only a single word as a term. Furthermore, the terms are case-insensitive (e.g. we consider “book” and “Book” to be the same term) and we don’t consider any morphological variants (e.g. we consider “books” and “book”, “protected” and “protect” to be different terms) and hyphenated words (e.g. “middle-class” is not a single term, but separated into 2 terms “middle” and “class” by the hyphen). The vocabulary is shown at the left part in Figure-1. Each term of the vocabulary has a pointer to its bucket. The collection of the buckets is shown at the middle part in Figure-1. Each item in a bucket records the DID of the term’s occurrence.

After constructing the whole inverted index structure, we may apply it to the queries. The query is in any of the following formats:

term

term AND term

term OR term

NOT term

A single term can be combined by Boolean operators: ‘AND’, ‘OR’ and ‘NOT’ (‘term1 AND term2’ means to query the documents including term1 and term2; ‘term1 OR term2’ means to query the documents including term1 or term2; ‘NOT term1’ means to query the documents not including term1). Terms are single words as defined above. You are guaranteed that no non-alphabetic characters appear in a term, and all the terms are in lowercase. Furthermore, some meaningless stop words (common words such as articles, prepositions, and adverbs, specified to be “the, a, to, and, or, not” in our problem) will not appear in the query, either.

For each query, the engine based on the constructed inverted index searches the term in the vocabulary, compares the terms’ bucket information, and then gives the result to user. Now can you construct the engine?

Input

The input starts with integer N (0 < N < 100) representing N documents provided. Then the next N sections are N documents. Each section contains the document content and ends with a single line of ten asterisks.

**********

You may assume that each line contains no more than 80 characters and the total number of lines in the N documents will not exceed 1500.

Next, integer M (0 < M ≤ 50000) is given representing the number of queries, followed by M lines, each query in one line. All the queries correspond to the format described above.

Output

For each query, you need to find the document satisfying the query, and output just the lines within the documents that include the search term (For a ‘NOT’ query, you need to output the whole document). You should print the lines in the same order as they appear in the input. Separate different documents with a single line of 10 dashes.

----------

If no documents matching the query are found, just output a single line: ‘Sorry, I found nothing.’. The output of each query ends with a single line of 10 equal signs.

==========

Sample Input

4
A manufacturer, importer, or seller of
digital media devices may not (1) sell,
or offer for sale, in interstate commerce,
or (2) cause to be transported in, or in a
manner affecting, interstate commerce,
a digital media device unless the device
includes and utilizes standard security
technologies that adhere to the security
system standards.
**********
Of course, Lisa did not necessarily
intend to read his books. She might
want the computer only to write her
midterm. But Dan knew she came from
a middle-class family and could hardly
afford the tuition, let alone her reading
fees. Books might be the only way she
could graduate
**********
Research in analysis (i.e., the evaluation
of the strengths and weaknesses of
computer system) is essential to the
development of effective security, both
for works protected by copyright law
and for information in general. Such
research can progress only through the
open publication and exchange of
complete scientific results
**********
I am very very very happy!
What about you?
**********
6
computer
books AND computer
books OR protected
NOT security
very
slick
Sample Output

want the computer only to write her
----------
computer system) is essential to the
==========
intend to read his books. She might
want the computer only to write her
fees. Books might be the only way she
==========
intend to read his books. She might
fees. Books might be the only way she
----------
for works protected by copyright law
==========
Of course, Lisa did not necessarily
intend to read his books. She might
want the computer only to write her
midterm. But Dan knew she came from
a middle-class family and could hardly
afford the tuition, let alone her reading
fees. Books might be the only way she
could graduate
----------
I am very very very happy!
What about you?
==========
I am very very very happy!
==========
Sorry, I found nothing.
==========

 

题目类型:简单字符处理+二分搜索

算法分析:根据题目的提示使用map<string, vector<node>>dict[maxn]来模拟倒插表,注意数据集中的单词为忽略大小写的

 

uva1596

maksyuki 发表于 oj 分类,标签: ,
0

In this problem, we consider a simple programming language that has only declarations of onedimensional integer arrays and assignment statements. The problem is to find a bug in the given program.

The syntax of this language is given in BNF as follows:

⟨program⟩ ::= ⟨declaration⟩|⟨program⟩⟨declaration⟩|⟨program⟩⟨assignment⟩

⟨declaration⟩ ::= ⟨array name⟩ [⟨number⟩]⟨new line⟩

⟨assignment⟩ ::= ⟨array name⟩ [⟨expression⟩]= ⟨expression⟩⟨newline⟩

⟨expression⟩ ::= ⟨number⟩|⟨array name⟩ [⟨expression⟩]

⟨number⟩ ::= ⟨digit⟩|⟨digit positive⟩⟨digit string⟩

⟨digit string⟩ ::= ⟨digit⟩|⟨digit⟩⟨digit string⟩

⟨digit positive⟩ ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

⟨digit⟩ ::= 0 | ⟨digit positive⟩

⟨array name⟩ ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

where ⟨new line⟩ denotes a new line character (LF).

Characters used in a program are alphabetical letters, decimal digits, =, [, ] and new line characters. No other characters appear in a program.

A declaration declares an array and specifies its length. Valid indices of an array of length n are integers between 0 and n − 1, inclusive. Note that the array names are case sensitive, i.e. array a and array A are different arrays. The initial value of each element in the declared array is undefined.

For example, array a of length 10 and array b of length 5 are declared respectively as follows.

a[10]

b[5]

An expression evaluates to a non-negative integer. A ⟨number⟩ is interpreted as a decimal integer. An ⟨array name⟩ [⟨expression⟩] evaluates to the value of the ⟨expression⟩-th element of the array. An assignment assigns the value denoted by the right hand side to the array element specified by the left hand side.

Examples of assignments are as follows.

a[0]=3

a[1]=0

a[2]=a[a[1]]

a[a[0]]=a[1]

A program is executed from the first line, line by line. You can assume that an array is declared once and only once before any of its element is assigned or referred to.

Given a program, you are requested to find the following bugs.

• An index of an array is invalid.

• An array element that has not been assigned before is referred to in an assignment as an index of array or as the value to be assigned.

You can assume that other bugs, such as syntax errors, do not appear. You can also assume that integers represented by ⟨number⟩s are between 0 and 231 − 1 (= 2147483647), inclusive.

Input

The input consists of multiple datasets followed by a line which contains only a single ‘.’ (period). Each dataset consists of a program also followed by a line which contains only a single ‘.’ (period). A program does not exceed 1000 lines. Any line does not exceed 80 characters excluding a new line character.

Output

For each program in the input, you should answer the line number of the assignment in which the first bug appears. The line numbers start with 1 for each program. If the program does not have a bug, you should answer zero. The output should not contain extra characters such as spaces.

Sample Input

a[3]
a[0]=a[1]
.
x[1]
x[0]=x[0]
.
a[0]
a[0]=1
.
b[2]
b[0]=2
b[1]=b[b[0]]
b[0]=b[1]
.
g[2]
G[10]
g[0]=0
g[1]=G[0]
.
a[2147483647]
a[0]=1
B[2]
B[a[0]]=2
a[B[a[0]]]=3
a[2147483646]=a[2]
.
.
Sample Output

2

2

2

3

4

0

 

题目类型:简单字符处理+栈模拟

算法分析:由于表达式可能存在嵌套的情况,所以需要使用栈来模拟计算。对于每个赋值语句'='左右两边的表达式都要分别计算并需要考虑不同的情况

 

uva230

maksyuki 发表于 oj 分类,标签:
0

I mean your borrowers of books — those mutilators of collections, spoilers of the symmetry of shelves, and creators of odd volumes. – (Charles Lamb, Essays of Elia (1823) ‘The Two Races of Men’)

Like Mr. Lamb, librarians have their problems with borrowers too. People don’t put books back where they should. Instead, returned books are kept at the main desk until a librarian is free to replace them in the right places on the shelves. Even for librarians, putting the right book in the right place can be very time-consuming. But since many libraries are now computerized, you can write a program to help.

When a borrower takes out or returns a book, the computer keeps a record of the title. Periodically, the librarians will ask your program for a list of books that have been returned so the books can be returned to their correct places on the shelves. Before they are returned to the shelves, the returned books are sorted by author and then title using the ASCII collating sequence. Your program should output the list of returned books in the same order as they should appear on the shelves. For each book, your program should tell the librarian which book (including those previously shelved) is already on the shelf before which the returned book should go.

Input

First, the stock of the library will be listed, one book per line, in no particular order. Initially, they are all on the shelves. No two books have the same title. The format of each line will be:

title" by author

The end of the stock listing will be marked by a line containing only the word:

END

Following the stock list will be a series of records of books borrowed and returned, and requests from librarians for assistance in restocking the shelves. Each record will appear on a single line, in one of the following formats:

BORROW title

RETURN title

SHELVE

The list will be terminated by a line containing only the word:

END

Output

Each time the SHELVE command appears, your program should output a series of instructions for the librarian, one per line, in the format:

Put title1 after title2

or, for the special case of the book being the first in the collection:

Put title first

After the set of instructions for each SHELVE, output a line containing only the word:

END

Assumptions & Limitations:

1. A title is at most 80 characters long.

2. An author is at most 80 characters long.

3. A title will not contain the double quote (") character.

Sample Input

"The Canterbury Tales" by Chaucer, G.
"Algorithms" by Sedgewick, R.
"The C Programming Language" by Kernighan, B. and Ritchie, D.
END
BORROW "Algorithms"
BORROW "The C Programming Language"
RETURN "Algorithms"
RETURN "The C Programming Language"
SHELVE
END

Sample Output

Put "The C Programming Language" after "The Canterbury Tales"

Put "Algorithms" after "The C Programming Language"

END

 

题目类型:简单字符处理

算法分析:首先将图书的标题和作者读入并分别使用结构体数组存储相应的值并排序,然后分类处理。当输入的命令是”BORROW”时,将相应数据的访问标志is_return置为-1,当命令是”RETURN”时,将相应数据的访问标志is_return置为1,当命令是”SHELVE”时,遍历所有is_return为1的数据,然后按照位置的不同输出相应的信息并把is_return置为0,注意含first语句的输出。下面第一份代码是更好的实现

 

uva1595

maksyuki 发表于 oj 分类,标签:
0

The figure shown on the left is left-right symmetric as it is possible to fold the sheet of paper along a vertical line, drawn as a dashed line, and to cut the figure into two identical halves. The figure on the right is not left-right symmetric as it is impossible to find such a vertical line.

Write a program that determines whether a figure, drawn with dots, is left-right symmetric or not. The dots are all distinct.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input file. The first line of each test case contains an integer N, where N (1 ≤ N ≤ 1, 000) is the number of dots in a figure. Each of the following N lines contains the x-coordinate and y-coordinate of a dot. Both x-coordinates and y-coordinates are integers between −10, 000 and 10, 000, both inclusive.

Output

Print exactly one line for each test case. The line should contain ‘YES’ if the figure is left-right symmetric, and ‘NO’, otherwise.

Sample Input

3
5
-2 5
0 0
6 5
4 0
2 3
4
2 3
0 4
4 0
0 0
4
5 14
6 10
5 10
6 14

Sample Output

YES

NO

YES

 

题目类型:暴力枚举

算法分析:由于判断的是是否存在左右对称,所以依次检查输入数据的每个y坐标,然后对于同一个y坐标,递增排序x坐标并从两头同时检查xa和xb中点的x坐标是否完全相同(对于所有的y坐标而言)

 

uva10391

maksyuki 发表于 oj 分类,标签:
0

You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.

Input

Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words.

Output

Your output should contain all the compound words, one per line, in alphabetical order.

Sample Input

a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra

Sample Output

alien

newborn

 

题目类型:二分查找

算法分析:由于数据规模有12e4,所以考虑按照字典序对于每个单词构造出其相接的子串sa和sb,然后二分查找sa和sb是否在给定的数据集中,复杂度为O(nmlogn),n为单词个数,m为单词长度

 

uva10763

maksyuki 发表于 oj 分类,标签:
0

Your non-profit organization (iCORE - international Confederation of Revolver Enthusiasts) coordinates a very successful foreign student exchange program. Over the last few years, demand has sky-rocketed and now you need assistance with your task.

The program your organization runs works as follows: All candidates are asked for their original location and the location they would like to go to. The program works out only if every student has a suitable exchange partner. In other words, if a student wants to go from A to B, there must be another student who wants to go from B to A. This was an easy task when there were only about 50 candidates, however now there are up to 500000 candidates!

Input

The input file contains multiple cases. Each test case will consist of a line containing n – the number of candidates (1 ≤ n ≤ 500000), followed by n lines representing the exchange information for each candidate. Each of these lines will contain 2 integers, separated by a single space, representing the candidate’s original location and the candidate’s target location respectively. Locations will be represented by nonnegative integer numbers. You may assume that no candidate will have his or her original location being the same as his or her target location as this would fall into the domestic exchange program. The input is terminated by a case where n = 0; this case should not be processed.

Output

For each test case, print ‘YES’ on a single line if there is a way for the exchange program to work out, otherwise print ‘NO’.

Sample Input

10
1 2
2 1
3 4
4 3
100 200
200 100
57 2
2 57
1 2
2 1
10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
0

Sample Output

YES

NO

 

题目类型:二分枚举

算法分析:由于数据组数达到5e5,所以考虑使用二分枚举的方法。使用map<pair<int, int>, int>存储每个对应关系的组数,最后枚举一遍若关系(a,b)的组数和(b,a)的组数不同,则不可能交换

 

uva1594

maksyuki 发表于 oj 分类,标签:
0

A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers (a1, a2, · · · , an), the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers:

(a1, a2, · · · , an) → (|a1 − a2|, |a2 − a3|, · · · , |an − a1|)

Ducci sequences either reach a tuple of zeros or fall into a periodic loop. For example, the 4-tuple sequence starting with 8,11,2,7 takes 5 steps to reach the zeros tuple:

(8, 11, 2, 7) → (3, 9, 5, 1) → (6, 4, 4, 2) → (2, 0, 2, 4) → (2, 2, 2, 2) → (0, 0, 0, 0).

The 5-tuple sequence starting with 4,2,0,2,0 enters a loop after 2 steps:

(4, 2, 0, 2, 0) → (2, 2, 2, 2, 4) → (0,0,0,2,2) → (0, 0, 2, 0, 2) → (0, 2, 2, 2, 2) → (2, 0, 0, 0, 2) → (2, 0, 0, 2, 0) → (2, 0, 2, 2, 2) → (2, 2, 0, 0, 0) → (0, 2, 0, 0, 2) → (2, 2, 0, 2, 2) → (0, 2, 2, 0, 0) → (2, 0, 2, 0, 0) → (2, 2, 2, 0, 2) → (0, 0, 2, 2, 0) → (0, 2, 0, 2, 0) → (2, 2, 2, 2, 0) → (0,0,0,2,2) → · · ·

Given an n-tuple of integers, write a program to decide if the sequence is reaching to a zeros tuple or a periodic loop.

Input

Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n (3 ≤ n ≤ 15), which represents the size of a tuple in the Ducci sequences. In the following line, n integers are given which represents the n-tuple of integers. The range of integers are from 0 to 1,000. You may assume that the maximum number of steps of a Ducci sequence reaching zeros tuple or making a loop does not exceed 1,000.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print ‘LOOP’ if the Ducci sequence falls into a periodic loop, print ‘ZERO’ if the Ducci sequence reaches to a zeros tuple.

Sample Input

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

Sample Output

ZERO

LOOP

ZERO

LOOP

 

题目类型:暴力枚举

算法分析:由于最多循环1000次就会出现循环节,所以可以枚举1000次并进行判断

 

uva221

maksyuki 发表于 oj 分类,标签: ,
0

An elevation of a collection of buildings is an orthogonal projection of the buildings onto a vertical plane. An external elevation of a city would show the skyline and the faces of the “visible” buildings of the city as viewed from outside the city from a certain direction. A southern elevation shows no sides; it shows the perfectly rectangular faces of buildings or parts of faces of buildings not obstructed on the south by taller buildings. For this problem, you must write a program that determines which buildings of a city are visible in a southern elevation.

For simplicity, assume all the buildings for the elevation are perfect rectangular solids, each with two sides that run directly east-west and two running directly north-south. Your program will find the buildings that appear in a southern elevation based on knowing the positions and heights of each city building. That data can be illustrated by a map of the city as in the diagram on the left below. The southern elevation for that city is illustrated in the diagram on the right.

City map. Boldface numbers (in the upper left of each building) identify the buildings. Plain numbers (lower right) are the buildings heights. Southern Elevation (Only the shaded buildings are visible in a southern elevation)

Input

Input for your program consists of the numeric description of maps of several cities. The first line of each map contains the number of buildings in the city (a non-negative integer less than 101). Each subsequent line of a map contains data for a single building — 5 real numbers separated by spaces in the following order:

x-coordinate of the southwest corner

y-coordinate of the southwest corner

width of the building (length of the south side)

depth of the building (length of the west side)

height of the building

Each map is oriented on a rectangular coordinate system so that the positive x-axis points east and the positive y-axis points north. Assume that all input for each map corresponds to a legitimate map (the number of buildings is the same as the number of subsequent lines of input for the map; no two buildings in a single map overlap). Input is terminated by the number 0 representing a map with no buildings.

Output

Buildings are numbered according to where their data lines appear in the map’s input data — building #1 corresponding to the first line of building data, building #2 data to the next line, and building #n to the nth line of building data for that map. (Buildings on subsequent maps also begin their numbering with 1.)

For each map, output begins with line identifying the map (map #1, map #2, etc.) On the next line the numbers of the visible buildings as they appear in the southern elevation, ordered south-to-north, west-to-east. This means that if building n and building m are visible buildings and if the southwest corner of building n is west of the southwest corner of building m, then number n is printed before number m. If building n and building m have the same x-coordinate for their southwest corners and if building n is south of building m, then the number n is printed before the number m.

For this program, a building is considered visible whenever the part of its southern face that appears in the elevation has strictly positive area. One blank line must separate output from consecutive input records.

Sample Input

14
160 0 30 60 30
125 0 32 28 60
95 0 27 28 40
70 35 19 55 90
0 0 60 35 80
0 40 29 20 60
35 40 25 45 80
0 67 25 20 50
0 92 90 20 80
95 38 55 12 50
95 60 60 13 30
95 80 45 25 50
165 65 15 15 25
165 85 10 15 35
0

Sample Output

For map #1, the visible buildings are numbered as follows:

5 9 4 3 10 2 1 14

 

题目类型:排序+离散化

算法分析:矩形的可见性等价于南墙的可见性,首先将矩形按照左下角坐标排序(x坐标优先,然后再比较y),然后将矩形的所有x坐标排序并去重,构造出每个小区间,易知每个矩形在这个小区间内要么可见,要么不可见,所以可以按照前面排好的顺序依次检查每个矩形,对于每个矩形依次检查每个小区间,在每个小区间内依次检查是存在其他矩形也在这个小区间内,且在其前面并且高度不比其低

 

uva814

maksyuki 发表于 oj 分类,标签: ,
0

For an electronic mail application you are to describe the SMTP-based communication that takes place between pairs of MTAs. The sender’s User Agent gives a formatted message to the sending Message Transfer Agent (MTA). The sending MTA communicates with the receiving MTA using the Simple Mail Transfer Protocol (SMTP). The receiving MTA delivers mail to the receiver’s User Agent. After a communication link is initialized, the sending MTA transmits command lines, one at a time, to the receiving MTA, which returns a three-digit coded response after each command is processed. The sender commands are shown below in the order sent for each message. There is more than one RCPT TO line when the same message is sent to several users at the same MTA. A message to users at different MTAs requires separate SMTP sessions.

HELO myname Identifies the sender to the receiver (yes, there is only one L)

MAIL FROM:< sender > Identifies the message sender

RCPT TO:< user > Identifies one recipient of the message

DATA Followed by an arbitrary number of lines of text comprising the message body, ending with a line containing a period in column one.

QUIT Terminates the communication.

The following response codes are sent by the receiving MTA:

221 Closing connection (after QUIT)

250 Action was okay (after MAIL FROM and RCPT TO specifying an acceptable user, or completion of a message)

354 Start sending mail (after DATA)

550 Action not taken; no such user here (after RCPT TO with unknown user)

Input

The input contains descriptions of MTAs followed by an arbitrary number of messages. Each MTA description begins with the MTA designation and its name (1 to 15 alphanumeric characters). Following the MTA name is the number of users that receive mail at that MTA and a list of the users (1 to 15 alphanumeric characters each). The MTA description is terminated by an asterisk in column 1. Each message begins with the sending user’s name and is followed by a list of recipient identifiers. Each identifier has the form user@mtaname. The message (each line containing no more than 72 characters) begins and terminates with an asterisk in column 1. A line with an asterisk in column 1 instead of a sender and recipient list indicates the end of the entire input.

Output

For each message, show the communication between the sending and receiving MTAs. Every MTA mentioned in a message is a valid MTA; however, message recipients may not exist at the destination MTA. The receiving MTA rejects mail for those users by responding to the RCPT TO command with the 550 code. A rejection will not affect delivery to authorized users at the same MTA. If there is not at least one authorized recipient at a particular MTA, the DATA is not sent. Only one SMTP session is used to send a message to users at a particular MTA. For example, a message to 5 users at the same MTA will have only one SMTP session. Also a message is addressed to the same user only once. The order in which receiving MTAs are contacted by the sender is the same as in the input file. As shown in the sample output, prefix the communication with the communicating MTA names, and indent each non-empty communication line. No innecessary spaces should be printed.

Sample Input

MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report! --Fiona
*
*
Sample Output

Connection between Cairo and MexicoCity
HELO Cairo
250
MAIL FROM:<Hamdy@Cairo>
250
RCPT TO:<Conrado@MexicoCity>
250
RCPT TO:<Lisa@MexicoCity>
550
DATA
354
Congratulations on your efforts !!
--Hamdy
.
250
QUIT
221
Connection between Cairo and SanFrancisco
HELO Cairo
250
MAIL FROM:<Hamdy@Cairo>
250
RCPT TO:<Shariff@SanFrancisco>
250
DATA
354
Congratulations on your efforts !!
--Hamdy
.
250
QUIT
221
Connection between London and HongKong
HELO London
250
MAIL FROM:<Fiona@London>
250
RCPT TO:<Chen@HongKong>
250
DATA
354
Thanks for the report! --Fiona
.
250
QUIT
221
Connection between London and Paris
HELO London
250
MAIL FROM:<Fiona@London>
250
RCPT TO:<Natasha@Paris>
550
QUIT
221

 

题目类型:简单字符处理+模拟

算法分析:按照题目给定的过程模拟MTA交互即可,注意若接受者中有重复的地址是需要去除掉的

 

uva207

maksyuki 发表于 oj 分类,标签:
0

A PGA (Professional Golf Association) Tour event is a golf tournament in which prize money is awarded to the best players. The tournament is broken into four rounds of 18 holes apiece. All players are eligible to play the first two rounds. Only those with the best scores from those 36 holes “make the first cut” to play the final two rounds and qualify for prize money. Players with the best 72-hole aggregate scores (the lowest scores) earn prize money.

You must write a program to determine how the total prize money (called the tournament “purse”) is to be allocated for a tournament.

Specifications are as follows.

1) All players will play at least two 18-hole rounds (36 holes in all) unless they are disqualified for some reason.

2) Any player who is disqualified stops playing at the time of the disqualification. Players who are disqualified during the first two rounds are ineligible to make the cut. Players who are disqualified during either of the last two rounds are ineligible to win prize money.

3) At the end of the first two rounds, the field of players is cut to the 70 players with the lowest 36-hole scores plus ties. So if 10 players are tied for 70th place, then 79 players make the 36-hole cut. Players who do not make the 36-hole cut are eliminated from the playing field and do not win any prize money.

4) The players who do make the 36-hole cut play an additional 36 holes (two 18-hole rounds) and are paid a percentage of the total prize money depending on their 72-hole aggregate score. The lower the score, the more prize money a player wins.

5) Players are paid percentages of the the tournament purse according to their final standings. For example, if the tournament purse were $1,000,000 and the winner’s share were 18%, the winner would earn $180,000.

6) There will be only one winner of this tournament. (In an actual golf tournament, when there is a tie for the low 72-hole score, there is be a play-off among the tied players. We will ignore that situation.) 7) There may be a tie for any or all of the positions between 2 and 70. If there is a tie among n players for position k, the money designated for positions k through n + k − 1 is pooled and allocated equally among the tied players. For example, using the sample data given later, if there were a tie for second place between two golfers, they would each win $88,000 [(10.8% + 6.8%)/2 = 8.8% * $1,000,000]. If there were a three-way tie, all three golfers would get $74,666.67 [(10.8% + 6.8% + 4.8%)/3 = 7.466667% * $1,000,000]. The extra penny is ignored.

8) If disqualification reduces the field to less than 70 players, the money for the last and any other places not covered is not allocated. For example, if exactly 70 players make the cut but three of them are disqualified, then the tournament simply pays 67 places.

9) Amateur golfers may play in professional tournaments but can win no money. Any prize money “won” by an amateur is allocated to the next lower position. For example, if an amateur has placed third in a tournament, then third place money goes to the fourth place finisher, and fourth place money goes to the fifth place finisher, etc.

10) Only the low 70 non-amateur places and ties earn prize money. For example, if 75 players make the 36-hole cut, it is possible for 5 of them not to earn prize money, assuming none of the players making the cut are amateurs.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input for each case is broken into two segments. The amount of the tournament purse and the percentages for all the 70 places are stored in the first segment of the input. This segment contains exactly 71 lines, which are formatted as follows.

Line 1: Total value of the purse

Line 2: Percentage of the purse designated for first place

Line 3: Percentage of the purse designated for second place

...

Line71: Percentage of the purse designated for 70-th place All entries in the first 71 file lines can be read as real numbers.

All percentages are given to four decimal places. Assume the percentages are correct and sum to 100%.

A partial example of the first segment of the input file is shown in the sample input section below.

The second segment of the input contains the players’ names and their respective scores for the four rounds. There is a maximum of 144 players.A first line contains the number of players and then one more line for each one of them, with the format as follows (see a partial example in the sample input section).

Characters 1–20: Player name

Characters 21–23: Round 1 score (first 18 holes)

Characters 24–26: Round 2 score (second 18 holes)

Characters 27–29: Round 3 score (third 18 holes)

Characters 30–32: Round 4 score (fourth 18 holes)

Any player who has an asterisk ‘*’ at the end of his last name is an amateur. All players who are not disqualified will have four 18-hole scores listed. (Even though in an actual tournament, players who do not make the cut do not get to play the last two rounds of the tournament, for the purposes of this program all players wh