日度归档：11 3 月, 2017

Openjudge Charm Bracelet

发表评论

Charm Bracelet

总时间限制:
1000ms
内存限制:
65536kB
描述

Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charmiin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability’ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

输入
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
输出
Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
样例输入
4 6
1 4
2 6
3 12
2 7
样例输出
23
来源
USACO 2007 December Silver

继续阅读 →

Openjudge 棋盘问题

发表评论

棋盘问题

总时间限制:
1000ms
内存限制:
65536kB
描述
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
输入
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
输出
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
样例输入
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
样例输出
2
1
来源
蔡错@pku

继续阅读 →

Openjudge A Knight’s Journey

发表评论

A Knight’s Journey

总时间限制:
1000ms
内存限制:
65536kB
描述
Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
输入
The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
输出
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
样例输入
3
1 1
2 3
4 3
样例输出
Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
来源
TUD Programming Contest 2005, Darmstadt, Germany

继续阅读 →

Openjudge 红与黑

发表评论

红与黑

总时间限制:
1000ms
内存限制:
65536kB
描述
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
输出
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0
样例输出
45
来源
1979

继续阅读 →

数据结构 邓俊辉 PA#2 旅行商(TSP) 题解

发表评论

旅行商(TSP)

Description

Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is out of repair for long time, such that some road is one-way road. There are even some villages that can’t be reached from any other village. In such a case, we only hope as many villages can receive mails as possible.

Shrek hopes to choose a village A as starting point (He will be air-dropped to this location), then pass by as many villages as possible. Finally, Shrek will arrived at village B. In the travelling process, each villages is only passed by once. You should help Shrek to design the travel route.

Input

There are 2 integers, n and m, in first line. Stand for number of village and number of road respectively.

In the following m line, m road is given by identity of villages on two terminals. From v1 to v2. The identity of village is in range [1, n].

Output

Output maximum number of villages Shrek can pass by.

Example

Input

4 3
1 4
2 4
4 3

Output

3

Restrictions

1 <= n <= 1,000,000

0 <= m <= 1,000,000

These is no loop road in the input.

Time: 2 sec

Memory: 256 MB

Hints

Topological sorting

描述

Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。

Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。

输入

第一行包括两个整数n，m，分别表示村庄的个数以及可以通行的道路的数目。

以下共m行，每行用两个整数v1和v2表示一条道路，两个整数分别为道路连接的村庄号，道路的方向为从v1至v2，n个村庄编号为[1, n]。

输出

输出一个数字，表示符合条件的最长道路经过的村庄数。

样例

见英文题面

限制

1 ≤ n ≤ 1,000,000

0 ≤ m ≤ 1,000,000

输入保证道路之间没有形成环

时间：2 sec

空间：256 MB

提示

拓扑排序

继续阅读 →

数据结构 邓俊辉 PA#2 真二叉树重构(Proper Rebuild)题解

发表评论

真二叉树重构(Proper Rebuild)

Description

In general, given the preorder traversal sequence and postorder traversal sequence of a binary tree, we cannot determine the binary tree.

Figure 1

In Figure 1 for example, although they are two different binary tree, their preorder traversal sequence and postorder traversal sequence are both of the same.

But for one proper binary tree, in which each internal node has two sons, we can uniquely determine it through its given preorder traversal sequence and postorder traversal sequence.

Label n nodes in one binary tree using the integers in [1, n], we would like to output the inorder traversal sequence of a binary tree through its preorder and postorder traversal sequence.

Input

The 1st line is an integer n, i.e., the number of nodes in one given binary tree,

The 2nd and 3rd lines are the given preorder and postorder traversal sequence respectively.

Output

The inorder traversal sequence of the given binary tree in one line.

Example

Input

5
1 2 4 5 3
4 5 2 3 1

Output

4 2 5 1 3

Restrictions

For 95% of the estimation, 1 <= n <= 1,000,00

For 100% of the estimation, 1 <= n <= 4,000,000

The input sequence is a permutation of {1,2…n}, corresponding to a legal binary tree.

Time: 2 sec

Memory: 256 MB

Hints

Figure 2

In Figure 2, observe the positions of the left and right children in preorder and postorder traversal sequence.

描述

一般来说，给定二叉树的先序遍历序列和后序遍历序列，并不能确定唯一确定该二叉树。

（图一）

比如图一中的两棵二叉树，虽然它们是不同二叉树，但是它们的先序、后序遍历序列都是相同的。

但是对于“真二叉树”（每个内部节点都有两个孩子的二叉树），给定它的先序、后序遍历序列足以完全确定它的结构。

将二叉树的n个节点用[1, n]内的整数进行编号，输入一棵真二叉树的先序、后序遍历序列，请输出它的中序遍历序列。

输入

第一行为一个整数n，即二叉树中节点的个数。

第二、三行为已知的先序、后序遍历序列。

输出

仅一行，给定真二叉树的中序遍历序列。

样例

见英文题面

限制

对于95%的测例：1 ≤ n ≤ 1,000,000

对于100%的测例：1 ≤ n ≤ 4,000,000

输入的序列是{1,2…n}的排列，且对应于一棵合法的真二叉树

时间：2 sec

空间：256 MB

提示

观察左、右孩子在先序、后序遍历序列中的位置

重温视频05e5-3

目测一辈子也忘不了二叉树重构怎么写了…………
继续阅读 →