2013
11-11

# Ambiguous permutations

Some programming contest problems are really tricky: not only do they require a different output format from what you might have expected, but also the sample output does not show the difference. For an example, let us look at permutations.

A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1.

However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.

An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation. The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same. To get rid of such annoying sample test cases, you have to write a program which detects if a given permutation is ambiguous or not.

The input contains several test cases.

The first line of each test case contains an integer n (1 <= n <= 100000). Then a permutation of the integers 1 to n follows in the next line. There is exactly one space character between consecutive integers. You can assume that every integer between 1 and n appears exactly once in the permutation.

The last test case is followed by a zero.

For each test case output whether the permutation is ambiguous or not. Adhere to the format shown in the sample output.

4
1 4 3 2
5
2 3 4 5 1
1
1
0

ambiguous
not ambiguous
ambiguous

Huge input,scanf is recommended.

//* @author 洪晓鹏<[email protected]>
//读大数据 buffered

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

while (true) {
int n = Integer.parseInt(in.readLine());
if (n == 0)
break;
//StringTokenizer st = new StringTokenizer(in.readLine()," ");
String s = in.readLine();
String[] sArray=s.split(" ");
Map< Integer, Integer> map = new HashMap< Integer, Integer>();
int[] array = new int[n];
int i = 0;
//	while(st.hasMoreTokens()) {
//		int key = Integer.parseInt(st.nextToken());
//		array[i] = key;
//		map.put(key, i+1);
//		i++;
//	}
//	int sl = sArray.length;
//System.out.println(sl);
for(i = 0; i< n; i++){
int key = Integer.parseInt(sArray[i]);
array[i] = key;
map.put(key, i+1);
}
int count = 0;
for (i = 0; i < n; i++) {
if (map.get(i+1) == array[i])
count++;
else
break;
//System.out.println(array[i]+" "+map.get(i+1));

}
if (count == n)
System.out.println("ambiguous");
else
System.out.println("not ambiguous");

}
}
}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

2. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？