Unique Ascending Array

http://acm.zju.edu.cn/show_problem.php?pid=2481

Time limit: 1 Seconds

Memory limit: 32768K

Given an array of integers A[N], you are asked to decide the shortest array of integers B[M], such that the following two conditions hold.

For all integers 0 <= i < N, there exists an integer 0 <= j < M, such that A[i] == B[j]
For all integers 0 =< i < j < M, we have B[i] < B[j]

Notice that for each array A[] a unique array B[] exists.

1. Input

The input consists of several test cases. For each test case, an integer N (1 <= N <= 100) is given, followed by N integers A[0], A[1], ..., A[N - 1] in a line. A line containing only a zero indicates the end of input.

2. Output

For each test case in the input, output the array B in one line. There should be exactly one space between the numbers, and there should be no initial or trailing spaces.

3. Sample Input

8 1 2 3 4 5 6 7 8
8 8 7 6 5 4 3 2 1
8 1 3 2 3 1 2 3 1
0

4. Sample Output

1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3

   1 /*written by proby*/
   2 #include <iostream>
   3 #include <list>
   4 using namespace std;
   5 
   6 void Add(list<int>& objList, int i){
   7         list<int>::iterator objIter;
   8         for(objIter=objList.begin(); ; objIter++){
   9                 if(objIter==objList.end() || *objIter>i){
  10                         objList.insert(objIter, i);
  11                         return;
  12                 }
  13                 if(*objIter==i){
  14                         return;
  15                 }
  16         }
  17 }
  18 
  19 void MyPrint(list<int>& objList){
  20         list<int>::iterator objIter;
  21         list<int>::iterator nextIter;
  22         nextIter=objList.begin();
  23         nextIter++;
  24         for(objIter=objList.begin(); objIter!=objList.end(); objIter++){
  25                 cout<<(*objIter);
  26                 if( nextIter!=objList.end() ){
  27                         cout<<" ";
  28                 }
  29                 nextIter++;
  30         }
  31         cout<<endl;
  32 }
  33 
  34 int main(){
  35         list<int> objList;
  36         list<int>::iterator listIter;
  37         int nLen, objInt, i;
  38         cin>>nLen;
  39         while(nLen!=0){
  40                 for(i=0; i<nLen; i++){
  41                         cin>>objInt;
  42                         Add(objList, objInt);
  43                 }
  44                 MyPrint(objList);
  45                 objList.clear();
  46                 cin>>nLen;
  47         }
  48 
  49         return 1;
  50 }