hqt

Untitled

hqt
Oct 4th, 2013
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.56 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.File;
  4. import java.io.IOException;
  5. import java.io.InputStream;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.util.ArrayList;
  11. import java.util.HashMap;
  12. import java.util.Map;
  13. import java.util.Scanner;
  14. import java.util.SortedSet;
  15. import java.util.StringTokenizer;
  16. import java.util.TreeSet;
  17.  
  18. /**
  19.  * <b> Algorithm on Codeforces. Problem C div 2 </b> </br>
  20.  * @author Huynh Quang Thao
  21.  *
  22.  */
  23. public class Main {
  24.  
  25.         public static void main(String[] args) throws Exception {
  26.                 Main main = new Main();
  27.                 main.run();
  28.         }
  29.        
  30.         public void run() throws Exception {
  31.                  Scanner sc = null;
  32.              PrintWriter pr = null;
  33.  
  34.              pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  35.              sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  36.              //sc = new Scanner(new File("input.txt"));
  37.              
  38.              int n = sc.nextInt();
  39.              Map<Integer, ArrayList<Integer>> map = new HashMap<>();
  40.              for (int i = 1; i <= n; i++) {
  41.                  int key = sc.nextInt();
  42.                  if (map.containsKey(key)) {
  43.                          ArrayList<Integer> value = map.get(key);
  44.                          value.add(i);
  45.                          map.put(key, value);
  46.                  }
  47.                  else {
  48.                          ArrayList<Integer> value = new ArrayList<>();
  49.                          value.add(i);
  50.                          map.put(key, value);
  51.                  }
  52.              }
  53.              
  54.              // process
  55.              SortedSet<Integer> keys = new TreeSet<Integer>(map.keySet());
  56.              int count = 0;
  57.              StringBuilder sb = new StringBuilder();
  58.              for (Integer key : keys) {
  59.                  ArrayList<Integer> values = map.get(key);
  60.                  if (values.size() == 1) {
  61.                          //sb.append("%d %d\n", key, 0);
  62.                          sb.append(key + " " + 0 + "\n");
  63.                          count++;
  64.                  }
  65.                  else if (check(values)) {
  66.                          sb.append(key + " " + (values.get(1) - values.get(0))  + "\n");
  67.                          //sb.append("%d %d\n", key, values.get(1) - values.get(0));
  68.                          count++;
  69.                  }
  70.              }
  71.              
  72.              System.out.println(count);
  73.              System.out.println(sb.toString());
  74.              
  75.              
  76.              pr.close();
  77.              sc.close();
  78.         }
  79.        
  80.         public boolean check(ArrayList<Integer> list) {
  81.                 // assume size >= 2
  82.                 int d = list.get(1) - list.get(0);
  83.                 for (int i = 1; i < list.size(); i++) {
  84.                         if (list.get(i) - list.get(i-1) != d) return false;
  85.                 }
  86.                 return true;
  87.         }
  88.        
  89.         static class InputReader {
  90.                 public BufferedReader reader;
  91.  
  92.                 public StringTokenizer tokenizer;
  93.  
  94.                 public InputReader(InputStream stream) {
  95.                         reader = new BufferedReader(new InputStreamReader(stream));
  96.                         tokenizer = null;
  97.                 }
  98.  
  99.                 public String next() {
  100.                         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  101.                                 try {
  102.                                         tokenizer = new StringTokenizer(reader.readLine());
  103.                                 }
  104.                                 catch (IOException e) {
  105.                                         throw new RuntimeException(e);
  106.                                 }
  107.                         }
  108.                         return tokenizer.nextToken();
  109.                 }
  110.  
  111.                 public int nextInt() {
  112.                         return Integer.parseInt(next());
  113.                 }
  114.  
  115.                 public double nextDouble() {
  116.                         return Double.parseDouble(next());
  117.                 }
  118.  
  119.                 public float nextFloat() {
  120.                         return Float.parseFloat(next());
  121.                 }
  122.  
  123.                 public long nextLong() {
  124.                         return Long.parseLong(next());
  125.                 }
  126.  
  127.                 public BigInteger nextBigInteger() {
  128.                         return new BigInteger(next());
  129.                 }
  130.  
  131.         }
  132. }
Advertisement
Add Comment
Please, Sign In to add comment