import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.Arrays;
import java.util.Random;

public class Tester {
  
  static public class Pair<X,Y> { 
    private X fst;
    private Y snd; 
    public Pair(X fst, Y snd) {this.fst=fst; this.snd=snd;} 
    public X getFirst() { return fst; } 
    public Y getSecond() { return snd; }
    public void setFirst(X fst) { this.fst=fst; }
    public void setSecond(Y snd) { this.snd=snd; }
  }
  
  public static double compare(Pair<SortedList<Integer>,int[]> P)
  // return the number of points, max: 0.4
  {
    print(P);
    SortedList<Integer> L=P.getFirst();
    int[] A=P.getSecond();
    double points=0.0;
    if (A.length==L.size())
      points += 0.05;
    if (isSorted(L))
      points += 0.05;
    int count=0;
    for (int i=0; i<A.length; i++) {
      if (i+1 <= L.size() && A[i]==L.get(i+1).intValue())
        count++;
    }
    if (count>A.length-3)
      points += 0.2-0.05*(A.length-count);
    // test count()
    int idcount=1;
    count=0;
    int maxcount=0;
    for (int i=1; i<A.length; i++) {
      if (A[i]==A[i-1]) {
        idcount++;
      } else {
        maxcount++;
        if (L.count(new Integer(A[i-1]))==idcount)
          count++;
        idcount=1;
      }
    }
    maxcount++;
    if (L.count(new Integer(A[A.length-1]))==idcount)
      count++;
    if (count>maxcount-3)
      points += 0.1-0.025*(maxcount-count);
    return points;
  }
  
  public static Pair<SortedList<Integer>,int[]> 
  generate(int size,Random generator,int minindex,int maxindex)
  // for minindex and maxindex: non-positive values mean size()+1-index
  {
    SortedList<Integer> L=new SortedList<Integer>();
    int A[]=new int[size];
    int mini,maxi;
    for (int i=0; i<size; i++) {
      if (maxindex<=0)
        maxi=L.size()+1-maxindex;
      else
        maxi=maxindex;
      if (minindex<=0)
        mini=L.size()+1-minindex;
      else
        mini=minindex;
      int item=generator.nextInt(20);
      L.add(generator.nextInt(maxi-mini+1)+mini,
          new Integer(item));
      A[i]=item;
    }
    Arrays.sort(A);
    Pair<SortedList<Integer>,int[]> P;
    P=new Pair <SortedList<Integer>, int[]>(L,A);
    return P;
  }
    
  private static boolean isSorted(SortedList<? extends Comparable> L) {
    for (int i=1; i<L.size(); i++)
      if (L.get(i).compareTo(L.get(i+1)) > 0)
        return false;
    
    return true;
  }
  
  private static void print(Pair<SortedList<Integer>,int[]> P) {
    System.out.println("Sorted List:");
    for (int i=1; i<=P.getFirst().size(); i++)
      System.out.print(" "+P.getFirst().get(i));
    System.out.println();
    System.out.println("Sorted array:");
    for (int i=0; i<P.getSecond().length; i++)
      System.out.print(" "+P.getSecond()[i]);
    System.out.println();
  }
  
  public static void main(String[] args) {
    double points=0.0;
    NumberFormat f = new DecimalFormat("0.00");
    Random R=new Random(20062);

    // 5 tests, each 0.4 points:
    Pair<SortedList<Integer>,int[]> P;
    
    System.out.println("Test 1.");
    // test adding at the beginning
    try {
      P=generate(10,R,1,1);
      points += compare(P);
    } 
    catch (Exception e)
    {
      // no exception expected
      System.out.println("Unexpected exception"+e);
    }
    
    System.out.println("Test 2.");
    // test adding at the end
    try {
      P=generate(20,R,0,0);
      points += compare(P);
    } 
    catch (Exception e)
    {
      // no exception expected
      System.out.println("Unexpected exception"+e);
    }
    
    System.out.println("Test 3.");
    // test adding at random positions
    try {
      P=generate(30,R,1,0);
      points += compare(P);
    } 
    catch (Exception e)
    {
      // no exception expected
      System.out.println("Unexpected exception"+e);
    }
    
    System.out.println("Test 4.");
    // test remove at position
    try {
      P=generate(30,R,1,-1);
      P.getFirst().remove(10);
      int A[]=new int[P.getSecond().length-1];
      for (int i=0, j=0; i<P.getSecond().length; i++)
        if (i!=9)
          A[j++]=P.getSecond()[i];
      P.setSecond(A);
      points += compare(P)/2.0;
      P.getFirst().remove(20);
      A=new int[P.getSecond().length-1];
      for (int i=0, j=0; i<P.getSecond().length; i++)
        if (i!=19)
          A[j++]=P.getSecond()[i];
      P.setSecond(A);
      points += compare(P)/2.0;
    } 
    catch (Exception e)
    {
      // no exception expected
      System.out.println("Unexpected exception"+e);
    }
    
    System.out.println("Test 5.");
    // test remove item
    try {
      P=generate(30,R,1,-1);
      P.getFirst().remove(new Integer(9));
      // count items 9
      int count=0;
      for (int i=0; i<P.getSecond().length; i++)
        if (P.getSecond()[i]==9)
          count++;
      int A[]=new int[P.getSecond().length-count];
      for (int i=0, j=0; i<P.getSecond().length; i++)
        if (P.getSecond()[i]!=9)
          A[j++]=P.getSecond()[i];
      P.setSecond(A);
      points += compare(P);
    } 
    catch (Exception e)
    {
      // no exception expected
      System.out.println();
      System.out.println("Unexpected exception"+e);
    }

    System.out.println("Points="+f.format(points)+" out of 2");
  }
}