An anagram of a string is formed by rearranging the letters in the string. For example, the anagrams of aab are aab, aba, and baa.
A wildcard anagram of a string is an anagram of the string where some of the letters might have been replaced with an asterisk (*). For example, two possible wildcard anagrams of aab are ab and b*.
Given two strings, determine whether the second string is a wildcard anagram of the first string.
The two lines of input will both consist of \(N\) \((1 \leq N \leq 100)\) characters. Each character in the first line will be a lowercase letter. Each character in the second line will be either a lowercase letter or an asterisk.
For 8 of the 15 available marks, the second line will not contain any asterisk characters.
Output the character A if the string on the
second line is a wildcard anagram of the string on the first line.
Otherwise, output the character N.
abba
baaaN
cccrocks
socc*rk*A
Since time immemorial, the citizens of Dmojistan and Pegland have been at war. Now, they have finally signed a truce. They have decided to participate in a tandem bicycle ride to celebrate the truce. There are \(N\) citizens from each country. They must be assigned to pairs so that each pair contains one person from Dmojistan and one person from Pegland.
Each citizen has a cycling speed. In a pair, the fastest person will always operate the tandem bicycle while the slower person simply enjoys the ride. In other words, if the members of a pair have speeds \(a\) and \(b\), then the bike speed of the pair is \(\max(a,b)\). The total speed is the sum of the \(N\) individual bike speeds.
For this problem, in each test case, you will be asked to answer one of two questions:
Question 1: what is the minimum total speed, out of all possible assignments into pairs?
Question 2: what is the maximum total speed, out of all possible assignments into pairs?
The first line will contain the type of question you are to solve, which is either \(1\) or \(2\).
The second line contains \(N\) \((1 \leq N \leq 100)\).
The third line contains \(N\) space-separated integers: the speeds of the citizens of Dmojistan.
The fourth line contains \(N\) space-separated integers: the speeds of the citizens of Pegland.
Each person’s speed will be an integer between \(1\) and \(1\ 000\ 000\).
For 8 of the 15 available marks, questions of type \(1\) will be asked. For 7 of the 15 available marks, questions of type \(2\) will be asked.
Output the maximum or minimum total speed that answers the question asked.
1
3
5 1 4
6 2 412
There is a unique optimal solution:
Pair the citizen from Dmojistan with speed 5 and the citizen from Pegland with speed 6.
Pair the citizen from Dmojistan with speed 1 and the citizen from Pegland with speed 2.
Pair the citizen from Dmojistan with speed 4 and the citizen from Pegland with speed 4.
2
3
5 1 4
6 2 415
There are multiple possible optimal solutions. Here is one optimal solution:
Pair the citizen from Dmojistan with speed 5 and the citizen from Pegland with speed 2.
Pair the citizen from Dmojistan with speed 1 and the citizen from Pegland with speed 6.
Pair the citizen from Dmojistan with speed 4 and the citizen from Pegland with speed 4.
2
5
202 177 189 589 102
17 78 1 496 5402016
There are multiple possible optimal solutions. Here is one optimal solution:
Pair the citizen from Dmojistan with speed 202 and the citizen from Pegland with speed 1.
Pair the citizen from Dmojistan with speed 177 and the citizen from Pegland with speed 540.
Pair the citizen from Dmojistan with speed 189 and the citizen from Pegland with speed 17.
Pair the citizen from Dmojistan with speed 589 and the citizen from Pegland with speed 78.
Pair the citizen from Dmojistan with speed 102 and the citizen from Pegland with speed 496.
This sum yields \(202+540+189+589+496=2016\).
Jo is a blogger, specializing in the critique of restaurants. Today, she wants to visit all the Vietnamese Pho restaurants in the Waterloo area, in order to determine which one is the best.
There are \(N\) restaurants in the city of Waterloo, numbered \(0\) to \(N-1\). However, only \(M\) of them are Pho restaurants. Jo can choose to start at any restaurant. There are \(N-1\) roads in Waterloo, each road connecting exactly two restaurants. It is possible to reach every restaurant from any restaurant using these roads. It takes Jo exactly 1 minute to travel along any road.
In computer science, a road network with this structure is called a tree. Here are three examples of trees:
One property that is true for all trees is that there is exactly one path that does not repeat any roads between any two points in the tree.
What is the minimal length of time that Jo needs to spend on travelling on roads to visit all of the Pho restaurants?
The first line of input contains 2 integers, \(N\) and \(M\) \((2 \leq M \leq N \leq 100\ 000)\).
The second line of input contains \(M\) distinct integers indicating the restaurants which are Pho restaurants.
The next \(N\)-1 lines contain 2 integers each. The \(i\)-th line contains \(a_i\) and \(b_i\), \((0 \leq a_i , b_i \leq N-1)\), representing a path between the two restaurants numbered \(a_i\) and \(b_i\).
For 3 of the 15 available marks, \(M = 2\) and \(N \leq 100\).
For an additional 3 of the 15 available marks, \(M \leq 3\) and \(N \leq 100\).
For an additional 3 of the 15 available marks, \(M \leq 8\) and \(N \leq 100\).
For an additional 4 of the 15 available marks, \(M \leq N \leq 1000\).
Your program should output one line, containing one integer - the minimum amount of time Jo needs to spend travelling on roads in order to visit all Pho restaurants, in minutes.
8 2
5 2
0 1
0 2
2 3
4 3
6 1
1 5
7 33
The path between \(5\) and \(2\) goes through \(5 \rightarrow 1 \rightarrow 0 \rightarrow 2\), which uses 3 roads.
8 5
0 6 4 3 7
0 1
0 2
2 3
4 3
6 1
1 5
7 37
If Jo begins at restaurant 6, she will only need to use 7 roads. One possible path that she can take is: \(6 \to 1 \to 0 \to 2 \to 3 \to 7 \to 3 \to 4\). Notice that she doesn’t need to visit restaurant 5, since it is not a Pho restaurant. A diagram of the road network is shown below:
Alphonse has \(N\) rice balls of various sizes in a row. He wants to form the largest rice ball possible for his friend to eat. Alphonse can perform the following operations:
If two adjacent rice balls have the same size, Alphonse can combine them to make a new rice ball. The new rice ball’s size is the sum of the two old rice balls’ sizes. It occupies the position in the row previously occupied by the two old rice balls.
If two rice balls have the same size, and there is exactly one rice ball between them, Alphonse can combine all three rice balls to make a new rice ball. (The middle rice ball does not need to have the same size as the other two.) The new rice ball’s size is the sum of the three old rice balls’ sizes. It occupies the position in the row previously occupied by the three old rice balls.
Alphonse can perform each operation as many times as he wants.
Determine the size of the largest rice ball in the row after performing 0 or more operations.
The first line will contain the integer, \(N\) \((1 \leq N \leq 400)\).
The next line will contain \(N\) space separated integers representing the sizes of the riceballs, in order from left to right. Each integer is at least \(1\) and at most \(1\ 000\ 000\).
For 1 of the 15 available marks, \(N = 4\).
For an additional 2 of the 15 available marks, \(N \leq 10\).
For an additional 5 of the 15 available marks, \(N \leq 50\).
Output the size of the largest riceball Alphonse can form.
7
47 12 12 3 9 9 348
One possible set of moves to create a riceball of size 48 is to combine 12 and 12, forming a riceball of size 24. Then, combine 9 and 9 to form a riceball of size 18. Then, combine 3, 18 and 3 to form a riceball of size 24. Finally, combine the two riceballs of size 24 to form a riceball of size 48.
4
1 2 3 13
There are no moves to make, thus the largest riceball in the row is size 3.
You may have heard of Conway’s Game of Life, which is a simple set of rules for cells on a grid that can produce incredibly complex configurations. In this problem we will deal with a simplified version of the game.
There is a one-dimensional circular strip of \(N\) cells. The cells are numbered from \(1\) to \(N\) in the order you would expect: that is, cell 1 and cell 2 are adjacent, cell 2 and cell 3 are adjacent, and so on up to cell \(N-1\), which is adjacent to cell \(N\). Since the strip is circular, cell \(1\) is also adjacent to cell \(N\).
Each cell is either alive (represented by a ‘1’) or dead (represented by a ‘0’). The cells change over a number of generations. If exactly one of a cell’s neighbours is alive in the current generation, then the cell will be alive in the next generation. Otherwise, the cell will be dead in the next generation.
Given the initial state of the strip, find the state after \(T\) generations.
The first line will contain two space-separated integers \(N\) and \(T\) \((3 \leq N \leq 100\ 000; 1 \leq T \leq 10^{15})\). The second line will contain a string consisting of exactly \(N\) characters, representing the initial configuration of the \(N\) cells. Each character in the string will be either ‘0’ or ‘1’. The initial state of cell \(i\) is given by the \(i\)-th character of the string. The character ‘1’ represents an alive cell and the character ‘0’ represents a dead cell.
For 1 of the 15 available marks, \(N \leq 15\) and \(T \leq 15\).
For an additional 6 of the 15 available marks, \(N \leq 15\).
For an additional 4 of the 15 available marks, \(N \leq 4000\) and \(T \leq 10\ 000\ 000\).
Note that for full marks, solutions will need to handle 64-bit integers. For example
in C/C++, the type long long should be
used;
in Java, the type long should be
used;
in Pascal, the type int64 should be
used.
Output the string of \(N\) characters representing the final state of the cells, in the same format and order as the input.
7 1
00000011000010
Cell 1 and cell \(N-1\) are adjacent to cell \(N\), and thus are alive after one generation.
5 3
0101110100
After one generation, the configuration becomes
00011.
After two generations, the configuration becomes
10111.