Friendship Networks
For a group of N people registered at a social network, a friendship network can be constructed with the N people as the nodes and a non-directed edge between every pair of friends. For such a network, it is usual to say that a node, i.e., a person, has degree d iff there are d nodes connected to it. Note that the degree of a node is exactly his/her number of friends. Since nobody is friends with himself / herself, the degree of each node is less than N.
A key property of a friendship network is the number of friends for each one of its members, i.e., its members’ degrees. However, given an intended number of network friends for each one of the members, such a network may or may not exist. For example, for a group of 4 people there is a friendship network in which the people have 3, 2, 2, and 3 friends. However, there is no friendship network corresponding to the enumeration 1, 3, 2, and 3 for a group of 4 people.
You are working at a company that researches friendship networks with the business idea of eventually developing applications on them. Your specific job is part of a test data validation. More precisely, you must write a program that given an enumeration of positive integers, decides if there exists a friendship network with such number of friends for each of its members.
Input
The input consists of several cases. Each test case is given in a single line by a blank-separated list of integers N, d1, d2, . . . , dN, with N (2 ≤ N ≤ 1000) the number of people in the social network and the d(i) (1 ≤ i ≤ N) an enumeration of a possible friendship network. You can assume that 0 < di < N for 1 ≤ i ≤ N.
The input must be read from standard input.
Output
Output a single line for each test case. If d1, d2, . . . , dN describes a friendship network with such number of friends for each of its members, then output 1; otherwise output 0.
The output must be written to standard output.
Sample Input
4 3 2 2 3
4 1 3 2 3
8 2 5 4 5 4 3 5 2
Sample Output
1
0
1
SOLUTION: Python
Extend to Palindrome
Your task is, given an integer N, to make a palidrome (word that reads the same when you reverse it) of length at least N. Any palindrome will do. Easy, isn’t it? That’s what you thought before you passed it on to your inexperienced team-mate. When the contest is almost over, you find out that that problem still isn’t solved. The problem with the code is that the strings generated are often not palindromic. There’s not enough time to start again from scratch or to debug his messy code. Seeing that the situation is desperate, you decide to simply write some additional code that takes the output and adds just enough extra characters to it to make it a palindrome and hope for the best. Your solution should take as its input a string and produce the smallest palindrome that can be formed by adding zero or more characters at its end.
Input
Input will consist of several lines ending in EOF. Each line will contain a non-empty string made up of upper case and lower case English letters (‘A’-‘Z’ and ‘a’-‘z’). The length of the string will be less than or equal to 100,000.
Output
For each line of input, output will consist of exactly one line. It should contain the palindrome formed by adding the fewest number of extra letters to the end of the corresponding input string.
Sample Input
aaaa
abba
amanaplanacanal
xyz
Sample Output
aaaa
abba
amanaplanacanalpanama
xyzyx
SOLUTION: Python
Ultra-QuickSort
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4
Ultra-QuickSort produces the output
0 1 4 5 9
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 50000, the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] < 10^10, the i-th input sequence element.
Input is terminated by a sequence of length n = 0. This sequence must not be processed.
The input must be read from standard input.
Output
For every input sequence, your program prints a single line containing the minimum number of swap operations necessary to sort the given input sequence.
The output must be written to standard output.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
SOLUTION: Python
Longest Match
A newly opened detective agency is struggling with their limited intelligence to find out a secret information passing technique among its detectives. Since they are new in this profession, they know well that their messages will easily be trapped and hence modified by other groups. They want to guess the intensions of other groups by checking the changed sections of messages. First they have to get the length of longest match. You are going to help them.
Input
The input may contain multiple test cases. Each case will contain two successive lines of string. Blank lines and non-letter printable punctuation characters may appear; any letter or digit is considered to be a letter character. Each line will be no longer than 1000 characters. Length of each word will at most 20 characters long.
The input must be read from standard input.
Output
For each case of input, you have to output a line starting with the case number right justified in a field width of two columns, followed by the longest match as shown in the sample output. In case of at least one blank line for each input output ‘Blank!’. Consider the non-letter characters as white-spaces.
The output must be written to standard output.
Sample Input
This is a test.
test
Hello!
The document provides late-breaking information
late breaking.
Sample Output
1. Length of longest match: 1
2. Blank!
3. Length of longest match: 2
SOLUTION: Python
