| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9336 | Connected Component(I) |
|
| 9372 | 8 Queens |
|
| 9388 | All combinations |
|
Description
You will be given an IC design graph with several connected chips components. In order to improve the design, your job is to find out the component with the largest number of chips. A connected chips component is a subset of chips in which any two chips are connected to each other by paths, and which is connected to no additional chips.
Input
There will be several test cases. In each test case, the first line will be an integer N representing the number of chips. The second line contains an integer K which is the number of wires. In the next K lines, each line contains two integers, A and B (0 <= A, B < N), which denotes that there is a wire between chip #A and chip #B. If N = 0, the input ends. Chips are numbered from 0~N-1.
Case 1: 1<=N<=10, 1<=K<=N^2
Case 2: 1<=N<=100, 1<=K<=N^2
Case 3: 1<=N<=1000, 1<=K<=min {N^2, 100000}
Case 4: 1<=N<=200000, 1<=K<=min {N^2, 200000}
Output
For each design graph, print the number of chips for the largest connected chips component.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 chess queens. The task is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the sum of the numbers on the squares selected is the maximum . (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one queen.)
Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions.
Input
Input will consist of K (the number of boards), on a line by itself, followed by K sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a non-negative integer less than 100. Each case is separated by a blank line. There will never be more than 20 boards.
Testcase 1: K<=5
Testcase 2: K<=10
Testcase 3: K<=15
Testcase 4: K<=20
Output
The outputs of all test cases should be printed in order. For each test case a line, print the highest score right justified in field 5 characters wide.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N different hexadecimal digits. You have to choose M from them to create all possible numbers in ascending order. For example, given 3 digits "1", "5", "D", and M = 2, the possible answers are "15", "1D", "51", "5D", "D1", "D5".
Input
The first line contains a positive integer T (T <= 100), which indicates how many cases in the input. Each case starts with two positive integers N and M (1 <= M <= N <= 16), which denote the amount of the digits and the amount of digits of desired numbers. The next line contains exactly n different digits(0~F) separated by blanks.
Case 1: 1 <= M <= N <= 10, digit range (0~9), T <= 10
Case 2: 1 <= M <= N <= 10, digit range (0~F), T <= 10
Case 3: 1 <= M <= N <= 10, digit range (0~F), T <= 20
Case 4: 1 <= M <= 10, 1 <= N <= 16, digit range (0~F), T <= 20
Output
For each case, first line outputs the case number. Then, output all the possible numbers in ascending order. (See the Sample Output)