The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - A
The Himalayas
Time Limit: 2 Seconds Memory Limit: 65536 KB
As an artist, Bob usually need to travel around the world. He made a lot of sketch of scenery on his journey. A famous spot he have visited recently is the Himalayas. The Himalayas is a mountain range in South Asia separating the plains of the Indian subcontinent from the Qinghai-Tibet Plateau. The Himalayas include over a hundred mountains exceeding 7,200 meters in elevation.
One day, Bob came up with an strange idea. He wanted to know the number of mountain peaks in his paintings. As his best friend, he turned to you for help. You are given a list of N height sampling values Hi. You should determine how many peaks are there. For all i which satisfies 2 <= i <= N - 1, Hi is defined as a peak if and only if Hi-1 < Hi > Hi+1.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains one integer N (1 <= N <= 50). The next line contains N integers Hi (1 <= Hi <= 8844). It is guaranteed that any two adjacent height sampling values will be different.
Output
For each test case, output the number of peaks.
Sample Input
2
9
1 3 2 4 6 3 2 3 1
5
1 2 3 4 5
Sample Output
3
0
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - B
A Volcanic Island
Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge
An underwater volcano has erupted massively in somewhere of the deep Atlantis Ocean. This large eruption led to the birth of a new volcanic island, which had a shape of square. Near the island, there are N countries. All of them have claimed the sovereignty over the island.
After a lot of multilateral negotiation and occasional armed conflicts, the N countries decided to divide the square volcanic island equally. They partitioned the island into N x N small equal-sized square chunks. Each country could get a connected region consists of exact N chunks.
Two chunks A and B are called "connected" if they share an edge, or there exists another chunk C connected with both A and B. A group of chunks are called "connected region" if any two of these chunks are connected.
Every country want a unique region. It means the N regions should be different with each other. Two regions are considered as the same if and only if one can transform into the other by an isometry (a combination of rigid motions, including translation, rotation and reflection).
In a nutshell, your task is to divide a square island with N x N chunks into N connected regions with different shape. You also need to draw a map to color the regions of the map so that no two edge-adjacent regions have the same color. Most of the people in these countries believed that four different colors are enough. So you can mark these regions with at most four colors, red, green, blue and yellow.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
There is only an integer N (1 <= N <= 100).
Output
For each test case, output a valid map described above. If there is no solution, output "No solution!" instead. Please note that only four colors ('R', 'G', 'B' and 'Y') can be used to drawing the map.
Sample Input
2
2
5
Sample Output
No solution!
YYYGR
YGGGR
YGYYR
BYYYR
BBBBR
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - C
Untrusted Patrol
Time Limit: 3 Seconds Memory Limit: 65536 KB
Edward is a rich man. He owns a large factory for health drink production. As a matter of course, there is a large warehouse in the factory.
To ensure the safety of drinks, Edward hired a security man to patrol the warehouse. The warehouse has N piles of drinks and M passageways connected them (warehouse is not big enough). When the evening comes, the security man will start to patrol the warehouse following a path to check all piles of drinks.
Unfortunately, Edward is a suspicious man, so he sets sensors on K piles of the drinks. When the security man comes to check the drinks, the sensor will record a message. Because of the memory limit, the sensors can only record for the first time of the security man's visit.
After a peaceful evening, Edward gathered all messages ordered by recording time. He wants to know whether is possible that the security man has checked all piles of drinks. Can you help him?
The security man may start to patrol at any piles of drinks. It is guaranteed that the sensors work properly. However, Edward thinks the security man may not works as expected. For example, he may digs through walls, climb over piles, use some black magic to teleport to anywhere and so on.
Input
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains three integers N (1 <= N <= 100000), M (1 <= M <= 200000) and K (1 <= K <= N).
The next line contains K distinct integers indicating the indexes of piles (1-based) that have sensors installed. The following M lines, each line contains two integers Ai and Bi (1 <= Ai, Bi <= N) which indicates a bidirectional passageway connects piles Ai and Bi.
Then, there is an integer L (1 <= L <= K) indicating the number of messages gathered from all sensors. The next line contains L distinct integers. These are the indexes of piles where the messages came from (each is among the K integers above), ordered by recording time.
Output
For each test case, output "Yes" if the security man worked normally and has checked all piles of drinks, or "No" if not.
Sample Input
2
5 5 3
1 2 4
1 2
2 3
3 1
1 4
4 5
3
4 2 1
5 5 3
1 2 4
1 2
2 3
3 1
1 4
4 5
3
4 1 2
Sample Output
No
Yes
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - D
We Need Medicine
Time Limit: 10 Seconds Memory Limit: 65536 KB Special Judge
A terrible disease broke out! The disease was caused by a new type of virus, which will lead to lethal lymphoedema symptom. For convenience, it was named LL virus.
After several weeks of research, the scientists found the LL virus highly lethal and infectious. But more importantly, it has a long incubation period. Many victims were unaware of being infected until everything was too late. To prevent from the apocalypse, we need medicine!
Fortunately, after another several weeks of research, the scientists have finished the analysis of the LL virus. You need write a program to help them to produce the medicine.
The scientists provide you N kinds of chemical substances. For each substance, you can either use it exact Wi milligrams in a medicine, or not use it. Each selected substance will add Ti points of therapeutic effect value (TEV) to the medicine.
The LL virus has Q different variants. For each variant, you need design a medicine whose total weight equals to Mi milligrams and total TEV equals to Si points. Since the LL virus is spreading rapidly, you should start to solve this problem as soon as possible!
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers N (1 <= N <= 400) and Q (1 <= Q <= 400).
For the next N lines, each line contains two integers Wi (1 <= Wi <= 50) and Ti (1 <= Ti <= 200000).
Then followed by Q lines, each line contains two integers Mi (1 <= Mi <= 50) and Si (1 <= Si <= 200000).
Output
For each test case, output Q lines. For the i-th line, output the indexes (1-based) of chemical substances in the i-th medicine, separated by a space. If there are multiple solutions, output any one. If there is no solution, output "No solution!" instead.
Sample Input
1
3 3
2 10
1 12
1 5
3 15
4 27
3 17
Sample Output
1 3
3 2 1
No solution!
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - E
Alternating Sum
Time Limit: 2 Seconds Memory Limit: 65536 KB
There is a digit string S with infinite length. In addition, S is periodic and it can be formed by concatenating infinite repetitions of a base string P. For example, if P = 3423537, then S = 3423537342353734235373423537...
Let's define the alternating sum on substrings of S. Assume Sl..r is a substring of S from index l to index r (all indexes are 1-based), then the alternating sum of Sl..r is:
G(l, r) = Sl - Sl+1 + Sl+2 - ... + (-1)r-lSr
For example, S2..10 = 423537342, then G(2, 10) = 4 - 2 + 3 - 5 + 3 - 7 + 3 - 4 + 2 = -3.
Now, you are given the base string P and you have to do many operations. There are only two kinds of operations:
- 1 x d: set Px to d, d is a single digit.
- 2 l r: find the sum of G(i, j) that l <= i <= j <= r.
For each second operation, you should output the sum modulo 109 + 7.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains a digit string P (1 <= length(P) <= 100000).
The second line contains an integer Q (1 <= Q <= 100000) indicating the number of operations. Each of the following Q lines is an operation in such format:
- 1 x d (1 <= x <= length(P), 0 <= d <= 9)
- 2 l r (1 <= l <= r <= 1018)
Output
For each "2 l r" operation, output an integer, indicating the sum modulo 109 + 7.
Sample Input
2
324242
4
2 1 1
2 1 4
1 3 7
2 3 4
324242
6
2 1 1
1 3 7
2 2 4
1 3 4
2 7 10
2 1 30
Sample Output
3
20
14
3
8
20
870
|
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - F |
Sawtooth Puzzle
Time Limit: 10 Seconds Memory Limit: 65536 KB
Recently, you found an interesting game called Sawtooth Puzzle. This is a single-player game played on a grid with 3 x 3 cells. Each cell contains a part of an image. Besides, each edge of a cell will be either smooth or saw-toothed. Two edge-adjacent cells are considered as meshed if their adjacent edges are both saw-toothed.
The game contains zero or more steps. At each step, the player can choose one cell, rotate it by 90 degrees clockwise. At the beginning of rotation, any cell which is going to rotate will drive other cells to rotate together if they are meshed. Of course, the driven (passive) cell will rotate in the opposite direction against the driver (active) cell. The following image demonstrates the procedure of rotating the middle cell clockwise:
Given the initial image and target image of the puzzle, please find out the minimum number of steps needed to solve it.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The input data consists of three parts. The first part represents the initial image of the puzzle. It contains 26 lines. Each line has 26 characters (excluding the line break ' '). The image is composed of 3 x 3 cells. Each cell is a monochrome image of 8 x 8 pixels ('#' for black, '.' for white). These cells are separated by space characters of 1 pixel width.
The second part represents the target image of the puzzle. It has the same format as which described above.
The last part contains 9 lines. Each line has 4 integers indicating the edge type (0 for smooth, 1 for saw-toothed) of a cell. The cells are listed in the order of top-left, top-middle, top-right, middle-left, ... , till bottom-right. For each cell, the edge type are given in the order of left, top, right and bottom.
There is an empty line between any two adjacent parts (including of different cases).
Output
For each test case, output the minimum number of steps needed to solve the puzzle. If there is no solution, output -1 instead.
Sample Input
1
......#. ........ ........
......## ........ ........
.......# #....... ........
.......# ##...... ...##...
.......# ###..... .###....
.......# ####...# ####....
.......# ######## ###.....
.......# ######## ###.....
........ ######## ###.....
.......# ######## ##......
.....### ######## ##......
....#### ######## ###.....
..###### ######## ####....
######## ######## #####...
...##### ######## ######..
........ ######## #######.
........ ........ ..######
........ .....### ........
........ ######## ........
........ .####### ........
........ ...##### ........
........ .....### ........
........ .......# ........
........ ........ ........
......#. ........ ........
......## ........ ........
.......# #....... ........
.......# ##...... ...##...
.......# ###..... .###....
.......# ####...# ####....
.......# ######## ###.....
.......# ######## ###.....
........ ######## ###.....
.......# ######## ##......
.....### ######## ##......
....#### ######## ###.....
..###### ######## ####....
######## ######## #####...
...##### ######## ######..
........ ######## #######.
........ .######. ..######
........ .#####.. ........
........ .#####.. ........
........ ..###... ........
........ ..###... ........
........ ..##.... ........
........ ..##.... ........
........ ..#..... ........
0 1 0 1
0 0 1 1
1 0 0 1
0 0 1 1
1 1 1 0
1 0 1 1
1 1 1 1
0 0 1 0
0 1 1 0
Sample Output
6
Hint
Here is the detailed solution to the sample input: (1,2) (1,2) (1,2) (1,2) (1,3) (3,1).
This problem comes from an interesting game. You can play it here (Level 2-2).
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - G
Diophantine Equations
Time Limit: 2 Seconds Memory Limit: 65536 KB
Alice: Hi Bob! Let's play a game.
Bob: Oh no! It's boring because both of us always choose the optimal strategy.
Alice: Well, then let's solve some Diophantine equations. What's the integer solutions of x2 + y2 = n if n is a fixed positive integer?
Bob: Er.. It's easy to get the solutions when n is a prime or 1. But it's a bit hard to solve this equation when n is a composite number.
Alice: Do you know Brahmagupta-Fibonacci identity? It says that the product of two sums each of two squares is itself a sum of two squares. Specifically: (a2 + b2)(c2 + d2) = (ac + bd)2 + (ad - bc)2 = (ac - bd)2 + (ad + bc)2. When n is a composite number, perhaps the solutions when n is a prime can be combined via this indentity.
Bob: Yes, the Brahmagupta-Fibonacci identity helps a lot. Now we can solve the equation easily. Let's solve some other equations. What about the integer solutions of x2 + y2 + z2 = A and x + y + z = B?
Alice: It's similar to the former equation but more complicated. Let's write a program to solve it.
Bob: Ok! It seems that we should get the decomposition of 3A - B2 first. And when 3A - B2 is less than zero, there cannot be any integer solutions.
Alice: I can write the prime factorization part. Can you complete the remaining part?
Bob doesn't know how to write a program. He turned to you for help. You are given two integers A and B. The prime factors of 3A - B2 will also be given. You should output all the integer solutions of x2 + y2 + z2 = A and x + y + z = B. Because of the symmetry, only the integer solutions (x, y, z) that x <= y <= z are required.
Input
There are multiple test cases. The first line of input contains an integer T (about 2000) indicating the number of test cases. For each test case:
There are two or more integers in one line. The first two integers are A (0 <= A <= 1018) and B (-109 <= B <= 109) respectively. The following integers in the same line are the prime factors of 3A - B2. If 3A - B2 is less than 2, no prime factors will be given.
Output
For each test case, output a label "Case #id:" first where id (starting from 1) is the case number. The following lines should be all the integer solutions (listed in x increasing order). For each integer solution, there should be three integer numbers x, y and z separated by a space.
You can assume that the total output will be no more than 20000 lines.
Sample Input
7
10 2 2 13
3 -3
1 1 2
15 -7
467716406 4 2 7 13 19
999278059394184698 1000000000 2 999007 999907 1000003
666666666666666645 -1 2 999999999999999967
Sample Output
Case #1:
-1 0 3
Case #2:
-1 -1 -1
Case #3:
0 0 1
Case #4:
Case #5:
-17655 8609 9050
-17641 8175 9470
-17554 7131 10427
-17494 6677 10821
-17410 6159 11255
-17215 5210 12009
-17059 4586 12477
-16773 3611 13166
-16591 3065 13530
-15954 1427 14531
-15499 426 15077
-15225 -130 15359
-14641 -1225 15870
-14323 -1779 16106
-14029 -2269 16302
-13714 -2773 16491
-13398 -3259 16661
-12966 -3895 16865
-12615 -4390 17009
-12265 -4866 17135
-11859 -5398 17261
-10585 -6945 17534
-9766 -7855 17625
-9298 -8349 17651
Case #6:
-325445947 576237380 749208567
-325096053 574086620 751009433
-324917875 573008543 751909332
-324556125 570853457 753702668
Case #7:
-641498974 163610588 477888385
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - H
Generalized Palindromic Number
Time Limit: 2 Seconds Memory Limit: 65536 KB
A number that will be the same when it is written forwards or backwards is known as a palindromic number. For example, 1234321 is a palindromic number.
We call a number generalized palindromic number, if after merging all the consecutive same digits, the resulting number is a palindromic number. For example, 122111 is a generalized palindromic number. Because after merging, 122111 turns into 121 which is a palindromic number.
Now you are given a positive integer N, please find the largest generalized palindromic number less than N.
Input
There are multiple test cases. The first line of input contains an integer T (about 5000) indicating the number of test cases. For each test case:
There is only one integer N (1 <= N <= 1018).
Output
For each test case, output the largest generalized palindromic number less than N.
Sample Input
4
12
123
1224
1122
Sample Output
11
121
1221
1121
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - I
Chinese Knot
Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge
Chinese knot is a decorative handicraft that began as a form of Chinese folk artifact in the Tang and Song Dynasty in China. It was later popularized in the Ming.
Alice is learning Chinese knotting. To take the first step, she went to the store and bought a string. To her surprise, she found the string was composed of characters! Anyway, she made a simple Chinese knot. It consists of one knot with 4 loops:
Look at the picture above. There are four loops connected at the center black knot. To make the image clear and neat, the characters on the string are shown as red and yellow points. As a Mid-Autumn Festival gift, Alice give this handcrafted Chinese knot to you. Then she asked you a question:
You are given a target character sequence. Can you get the sequence by walking on the knot? "Walking on the knot" means:
- You can start at any point you want.
- You can not start at or move to the black knot in the center.
- Each step, you can only move to an adjacent point, except for the point you came from immediately.
- The 8 points closely around the black knot are adjacent to each other. For example, in the picture above, they are the 8 yellow points adjacent to the black knot.
- Your path should not contain three continuous points which are both one of the 8 points mentioned above.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers N and M (3 <= N, M <= 100000). The total length of string that Alice bought from store is 4 * N.
Then followed by 4 lines, each line contains N lower case letters as a loop of the Chinese knot. These characters are indexed from 1 to 4 * N corresponding to the input order.
The next line contains M lower case letters indicating the target character sequence.
Output
For each test case, output the M indexes of characters you visited. If there are multiple solutions, output any one. If there is no solution, output "No solution!" instead.
Sample Input
2
3 3
abc
abc
abc
abc
baa
3 3
abc
abc
abc
abc
bab
Sample Output
2 1 4
No solution!
Hint
In the first case, we start at the second character of the first loop and stop at the first character of the second loop.
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round - J
Pretty Poem
Time Limit: 2 Seconds Memory Limit: 65536 KB
Poetry is a form of literature that uses aesthetic and rhythmic qualities of language. There are many famous poets in the contemporary era. It is said that a few ACM-ICPC contestants can even write poetic code. Some poems has a strict rhyme scheme like "ABABA" or "ABABCAB". For example, "niconiconi" is composed of a rhyme scheme "ABABA" with A = "ni" and B = "co".
More technically, we call a poem pretty if it can be decomposed into one of the following rhyme scheme: "ABABA" or "ABABCAB". The symbol A, B and C are different continuous non-empty substrings of the poem. By the way, punctuation characters should be ignored when considering the rhyme scheme.
You are given a line of poem, please determine whether it is pretty or not.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
There is a line of poem S (1 <= length(S) <= 50). S will only contains alphabet characters or punctuation characters.
Output
For each test case, output "Yes" if the poem is pretty, or "No" if not.
Sample Input
3
niconiconi~
pettan,pettan,tsurupettan
wafuwafu
Sample Output
Yes
Yes
No