Codeforces Round #485(Div.2) (6/6)

maksyuki 发表于 比赛 分类，标签:
01 6月 2018
0
A Infinity Gauntlet
You took a peek on Thanos wearing Infinity Gauntlet. In the Gauntlet there is a place for six Infinity Gems:
the Power Gem of purple color, the Time Gem of green color, the Space Gem of blue color, the Soul Gem of orange color, the Reality Gem of red color, the Mind Gem of yellow color.
Using colors of Gems you saw in the Gauntlet determine the names of absent Gems.
In the first line of input there is one integer n(0 ≤ n ≤ 6) — the number of Gems in Infinity Gauntlet.
Input
In next n lines there are colors of Gems you saw. Words used for colors are: purple, green, blue, orange, red, yellow. It is guaranteed that all the colors are distinct. All colors are given in lowercase English letters.

Output
In the first line output one integer m(0 ≤ m ≤ 6) — the number of absent Gems.

Then in m lines print the names of absent Gems, each on its own line. Words used for names are: Power, Time, Space, Soul, Reality, Mind. Names can be printed in any order. Keep the first letter uppercase, others lowercase.

Examples
input
4
red
purple
yellow
orange
output
2
Space
Time
input
0
output
6
Time
Mind
Soul
Power
Reality
Space
Note
In the first sample Thanos already has Reality, Power, Mind and Soul Gems, so he needs two more: Time and Space.

In the second sample Thanos doesn't have any Gems, so he needs all six.

题目类型：简单模拟
算法分析：使用map将对应的关系存下来，然后用set依次判断是否存在

 

B  High School: Become Human
Year 2118. Androids are in mass production for decades now, and they do all the work for humans. But androids have to go to school to be able to solve creative tasks. Just like humans before.
It turns out that high school struggles are not gone. If someone is not like others, he is bullied. Vasya-8800 is an economy-class android which is produced by a little-known company. His design is not perfect, his characteristics also could be better. So he is bullied by other androids.
One of the popular pranks on Vasya is to force him to compare x^y with y^x. Other androids can do it in milliseconds while Vasya's memory is too small to store such big numbers.
Please help Vasya! Write a fast program to compare x^y with y^x for Vasya, maybe then other androids will respect him.
Input
On the only line of input there are two integers x and y(1≤ x, y ≤ 10^9).
Output
If x^y < y^x , then print '<' (without quotes). If x^y > y^x, then print '>' (without quotes). If x^y = y^x, then print '=' (without quotes).
Examples
input
5 8
output
>
input
10 3
output
<
input
6 6
output
=
Note
In the first example 5^8 = 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 = 390625, and 8^5 = 8 ⋅ 8 ⋅ 8 ⋅ 8 ⋅ 8 = 32768. So you should print '>'.
In the second example 10^3 = 1000 < 3^10 = 59049.
In the third example 6^6 = 46656 = 6^ 6.
题目类型：简单数学
算法分析：可以对两个式子取对数然后直接比较

算法分析：更好的方法是xlny和ylnx同时除以xy(xy > 1)，则转换成比较lnx/x和lny/y之间的大小关系，易知f(x)=lnx/x在x=e处取得最大值，题目给定x为整数，则可以得到f(3) > f(2)=f(4) > f(5) > f(6) > ...f(n) > f(1)，按照这个大小关系直接判断即可

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

maksyuki 发表于 oj 分类，标签:
01 6月 2018
0

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ‘acm’ can be followed by the word ‘motorola’. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number N that indicates the number of plates (1 ≤ N ≤ 100000). Then exactly N lines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters ‘a’ through ‘z’ will appear in the word. The same word may appear several times in the list.

Output

Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.

If there exists such an ordering of plates, your program should print the sentence ‘Ordering is possible.’. Otherwise, output the sentence ‘The door cannot be opened.’

Sample Input

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

Sample Output

The door cannot be opened.

Ordering is possible.

The door cannot be opened.

 

题目类型：欧拉回路/路径

算法分析：将每个单词的头尾字符看做为两个点，从单词头到尾看做是从头到尾点的一个有向边，建完图后判断是否存在欧拉回路或路径即可

 

uva10305

maksyuki 发表于 oj 分类，标签:
01 6月 2018
0

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 ≤ n ≤ 100 and m. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j.

An instance with n = m = 0 will finish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.

Sample Input

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

Sample Output

1 4 2 5 3

 

题目类型：拓扑排序

算法分析：按照基本算法直接计算输出即可，下面第一个是基于队列的BFS实现，第二个是基于栈的DFS实现

 

 

uva816

maksyuki 发表于 oj 分类，标签:
01 6月 2018
0

The 1999 World Finals Contest included a problem based on a dice maze. At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last years problem statement. But we are happy to report that Mr. Abbott has offered his expertise to this years contest with his original and unpublished walk-through arrow mazes.

As are most mazes, a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited. These directions are always left, forward or right, or any combination of these.

Figure 1 illustrates a walk-through arrow maze. The intersections are identified as (row, column) pairs, with the upper left being (1,1). The Entrance intersection for Figure 1 is (3,1), and the Goal intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit (1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from (1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual (unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).

You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course.

Input

The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9. The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.

All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is ‘N’, ‘S’, ‘E’ or ‘W’ to indicate in what direction of travel the sign would be seen. For example, ‘S’ indicates that this is the sign that is seen when travelling south. (This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be ‘L’, ‘F’ or ‘R’ indicating left, forward, and right, respectively.

The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word ‘END’ on a single line by itself.

Output

For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase ‘No Solution Possible’. Maze names should start in column 1, and all other lines should start in column 3, i.e., indented two spaces. Solutions should be output as a list of intersections in the format (R,C) in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.

Note: Figure 2: Robert Abbott’s Atlanta Maze Robert Abbotts walk-through arrow mazes are actually intended for large-scale construction, not paper. Although his mazes are unpublished, some of them have actually been built. One of these is on display at an Atlanta museum. Others have been constructed by the American Maze Company over the past two summers. As their name suggests these mazes are intended to be walked through.

For the adventurous, Figure 2 a graphic of Robert Abbotts Atlanta maze. Solving it is quite difficult, even when you have an overview of the entire maze. Imagine trying to solve this by actually walking through the maze and only seeing one sign at a time! Robert Abbott himself indicated that the maze is too complex and most people give up before finishing. Among the people that did not give up was Donald Knuth: it took him about thirty minutes to solve the maze.

The first maze in the following sample input is the maze in Figure 1.

Sample Input

SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END

Sample Output

SAMPLE

(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)

(2,2) (1,2) (1,3) (2,3) (3,3)

NOSOLUTION

No Solution Possible

 

题目类型：简单BFS

算法分析：使用一个三元组(x,y,dir)表示走到每个点的状态，再使用一个par[x][y][dir]记录路径