| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14824 | Map coloring |
|
| 14825 | Longest common subsequence |
|
Description
Write a program to color the countries on a map.
Given a map with n countries, determine whether it is possible to color these countries using c colors so that no two adjacent countries have the same color.
Each country is assigned a unique ID from 1 to n, and each color is assigned a unique ID from 1 to c.
Constraints:
0 < n ≤ 20, 0 < c ≤ 6, 0 < p ≤ 400
Input
The first line of input contains the number of countries n, the number of colors c, and the number of pairs of adjacent countries p.
The following p lines each contain two country IDs representing a pair of neighboring countries.
Ex. 5 3 7
0 1
0 4
1 2
1 3
1 4
2 3
3 4
Output
If a valid coloring exists, output the color ID assigned to each of the n countries in order.
Since multiple symmetric solutions may exist, output the one that is lexicographically smallest when viewed as a string.
If no solution exists, output "no solution".
Ex. 1 2 3 1 3
Sample Input Download
Sample Output Download
Discuss
Description
Write a program to compute the Longest Common Subsequence (LCS).
A subsequence of a sequence is obtained by deleting some characters from the original sequence.
For example, aed is a subsequence of bacedf.
The longest common subsequence of two sequences is the common subsequence with the greatest length.
For instance, ade is one of the longest common subsequences of abcde and zzadfess.
Use the following recursive algorithm to compute the length of the LCS:
-
If the first characters of both strings are the same,
the length of the LCS is 1 plus the LCS length of the two strings with their first characters removed. -
If the first characters are different,
the LCS length is the maximum of the following two results:-
The LCS length after removing the first character from the first string.
-
The LCS length after removing the first character from the second string.
-
Constraints:
0 < n ≤ 16
Input
Two lines, each containing a lowercase letter string of length ≤ n.
Ex. abcde
zzadfess
Output
The length of the longest common subsequence.
Ex. 3