C Three displays
It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.

There are  n displays placed along a road, and the  i-th of them can display a text with font size si
only. Maria Stepanovna wants to rent such three displays with indices i<j<k that the font size increases if you move along the road in a particular direction. Namely, the condition si < sj < sk should be held.

The rent cost is for the i-th display is ci. Please determine the smallest cost Maria Stepanovna should pay.

Input
The first line contains a single integer n(3 ≤ n ≤ 3000) — the number of displays.

The second line contains n integers s1, s2, …, sn(1 ≤ si ≤ 10^9) — the font sizes on the displays in the order they stand along the road.

The third line contains n integers c1, c2, …, cn(1 ≤ ci ≤ 10^8) — the rent costs for each display.

Output
If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices i < j < k such that si < sj < sk.

Examples
input
5
2 4 5 4 10
40 30 20 10 40
output
90
input
3
100 101 100
2 4 5
output
-1
input
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13
output
33
Note
In the first example you can, for example, choose displays 1,  4 and 5, because s1 < s4 < s5(2 < 4 < 10), and the rent cost is  40 + 10 + 40 = 90.

In the second example you can't select a valid triple of indices, so the answer is -1.

题目类型：暴力枚举

算法分析：如果每次从枚举i的位置开始的话，那么j和k的位置是会相互牵连的，求解时间复杂度是O(n^3)的。此时若枚举j的位置，i和k的位置就被j所划分开来，然后分别在其左边范围内枚举i，在右边范围内枚举k，则时间复杂度为O(n^2)

D Fair
Some company is going to hold a fair in Byteland. There are n towns in Byteland and m two-way roads between towns. Of course, you can reach any town from any other town using roads. There are  k types of goods produced in Byteland and every town produces only one type. To hold a fair you have to bring at least s different types of goods. It costs d(u, v) coins to bring goods from town u to town v where d(u, v) is the length of the shortest path from u to v. Length of a path is the number of roads in this path.

The organizers will cover all travel expenses but they can choose the towns to bring goods from. Now they want to calculate minimum expenses to hold a fair in each of n towns.

Input
There are 4 integers n, m, k, s in the first line of input (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5, 1 ≤ s ≤ k ≤ min(n, 100)) — the number of towns, the number of roads, the number of different types of goods, the number of different types of goods necessary to hold a fair.

In the next line there are n integers a1, a2, …, an(1 ≤ ai ≤ k), where ai is the type of goods produced in the i-th town. It is guaranteed that all integers between 1 and k occur at least once among integers ai.

In the next m lines roads are described. Each road is described by two integers u v(1 ≤ u, v ≤ n, u ≠ v) — the towns connected by this road. It is guaranteed that there is no more than one road between every two towns. It is guaranteed that you can go from any town to any other town via roads.

Output
Print n numbers, the i-th of them is the minimum number of coins you need to spend on travel expenses to hold a fair in town i. Separate numbers with spaces.

Examples
input
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
output
2 2 2 2 3
input
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
output
1 1 1 2 2 1 1
Note
Let's look at the first sample.

To hold a fair in town 1 you can bring goods from towns 1(0 coins), 2(1 coin) and 4(1 coin). Total numbers of coins is 2.

Town 2: Goods from towns 2(0), 1(1), 3(1). Sum equals 2.

Town 3: Goods from towns 3(0), 2(1), 4(1). Sum equals 2.

Town 4: Goods from towns 4(0), 1(1), 5(1). Sum equals 2.

Town 5: Goods from towns 5(0), 4(1), 3(2). Sum equals 3.

题目类型：BFS搜索

算法分析：首先使用BFS计算k个物品所在的点对每个点的花费(最短路)，这里可以将具有相同物品种类的点放到一个BFS中计算。之后对于每个点累加前s小的花费即可，时间复杂度为O(k(m+n))+O(nklnk)

E Petr and Permutations
Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of numbers from 1 to n and then 3n times takes a random pair of different elements and swaps them. Alex envies Petr and tries to imitate him in all kind of things. Alex has also come up with a problem about random permutation. He generates a random permutation just like Petr but swaps elements 7n + 1 times instead of 3n times. Because it is more random, OK?!

You somehow get a test from one of these problems and now you want to know from which one.

Input
In the first line of input there is one integer n(10^3 ≤ n ≤ 10^6).

In the second line there are n distinct integers between 1 and n— the permutation of size n from the test.

It is guaranteed that all tests except for sample are generated this way: First we choose n— the size of the permutation. Then we randomly choose a method to generate a permutation — the one of Petr or the one of Alex. Then we generate a permutation using chosen method.

Output
If the test is generated via Petr's method print "Petr" (without quotes). If the test is generated via Alex's method print "Um_nik" (without quotes).

Example
input
5
2 4 5 1 3
output
Petr
Note
Please note that the sample is not a valid test (because of limitations for n) and is given only to illustrate input/output format. Your program still has to print correct answer to this test to get AC. Due to randomness of input hacks in this problem are forbidden.

题目类型：逆序对/置换群

算法分析：置换群求解逆序对问题的经典模型，逆序对的奇偶性和构成置换的循环的个数的奇偶性相关

F AND Graph
You are given a set of size m with integer elements between 0 and 2^n − 1 inclusive. Let's build an undirected graph on these integers in the following way: connect two integers x and y with an edge if and only if x&y = 0. Here & is the bitwise AND operation. Count the number of connected components in that graph.

Input
In the first line of input there are two integers n and m(0 ≤ n ≤ 22, 1 ≤ m ≤ 2^n).

In the second line there are m integers a1, a2, …, am(0 ≤ ai < 2^n) — the elements of the set. All ai are distinct.

Output
Print the number of connected components.

Examples
input
2 3
1 2 3
output
2
input
5 5
5 19 10 20 12
output
2

题目类型：DFS搜索

算法分析：重要的是依据'a&b'构造出图，然后计算图中的连通块数量，时间复杂度为O(n*2^n)，详见解法请参考CF485解题报告

« 上一篇：uva10129

uva10562：下一篇 »