hqt

Untitled

hqt
Oct 4th, 2013
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.29 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.Collections;
  12. import java.util.HashMap;
  13. import java.util.List;
  14. import java.util.Map;
  15. import java.util.Scanner;
  16. import java.util.SortedSet;
  17. import java.util.StringTokenizer;
  18.  
  19. /**
  20.  * <b> Algorithm on Codeforces. Problem C div 2 </b> </br>
  21.  * @author Huynh Quang Thao
  22.  *
  23.  */
  24. public class Main {
  25.  
  26.     public static void main(String[] args) throws Exception {
  27.         Main main = new Main();
  28.         main.run();
  29.     }
  30.    
  31.     public void run() throws Exception {
  32.          Scanner sc = null;
  33.          PrintWriter pr = null;
  34.  
  35.          pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  36.          sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  37.          sc = new Scanner(new File("input.txt"));
  38.          
  39.          int n = sc.nextInt();
  40.  
  41.          ArrayList<Integer> less = new ArrayList<>();
  42.          ArrayList<Integer> more = new ArrayList<>();
  43.          ArrayList<Integer> none = new ArrayList<>();
  44.          
  45.          for (int i = 0; i < 2*n; i++) {
  46.              double a = sc.nextDouble();
  47.              int con = (int) (a * 1000);
  48.              if (con % 1000 == 0 || con % 1000 == 500) none.add(con);
  49.              else if (con % 1000 < 500) less.add(con);
  50.              else more.add(con);
  51.          }
  52.  
  53.          Collections.sort(less);
  54.          Collections.sort(more);
  55.          Collections.reverse(more);
  56.          
  57.          System.out.println(none.size());
  58.          System.out.println(more.size());
  59.          System.out.println(less.size());
  60.          
  61.          if (less.size() > more.size()) {
  62.              ArrayList<Integer> tmp = less;
  63.              less = more;
  64.              more = tmp;
  65.          }
  66.          
  67.          int start = 0;
  68.          int end = 0;
  69.          int pivot = 0;
  70.          long sum  = 0;
  71.          if (more.size() - less.size() <= none.size()) {
  72.              // nothing strange happened
  73.          }
  74.          // more.size() - less.size() > none.size()
  75.          else {
  76.              start = less.size() + none.size();
  77.              end = more.size();
  78.              pivot = start - 1;
  79.              List<Integer> sub = more.subList(start, end);
  80.              if (sub.get(0) > sub.get(1)) Collections.reverse(sub);
  81.              for (int i = 0; i < sub.size() / 2; i++) {
  82.                  sum += sub.get(i) - (sub.get(i) % 1000); // round down
  83.                  int ops = sub.size() - 1 - i;
  84.                  sum += sub.get(ops) % 1000 + (sub.get(i) % 1000 - 1000);   // round up
  85.              }
  86.          }
  87.          
  88.          // sum all elements
  89.          for (int i = 0;  i< none.size(); i++) {
  90.              if (none.get(i) % 1000 == 500) sum += 500;
  91.          }
  92.          for (int i = 0; i < less.size(); i++) {
  93.              if (less.get(i) % 1000 < 500) sum += less.get(i) - (less.get(i) % 1000);
  94.              else sum += less.get(i) % 1000 + (less.get(i) % 1000 - 1000);
  95.          }
  96.          for (int i = 0; i <= pivot; i++) {
  97.              if (more.get(i) % 1000 < 500) sum += more.get(i) - (more.get(i) % 1000);
  98.              else sum += more.get(i) % 1000 + (more.get(i) % 1000 - 1000);
  99.          }
  100.          
  101.          
  102.          System.out.println(sum);
  103.          
  104.          pr.close();
  105.          sc.close();
  106.     }
  107.    
  108.    
  109.    
  110.     public boolean check(ArrayList<Integer> list) {
  111.         // assume size >= 2
  112.         int d = list.get(1) - list.get(0);
  113.         for (int i = 1; i < list.size(); i++) {
  114.             if (list.get(i) - list.get(i-1) != d) return false;
  115.         }
  116.         return true;
  117.     }
  118.    
  119.     static class InputReader {
  120.         public BufferedReader reader;
  121.  
  122.         public StringTokenizer tokenizer;
  123.  
  124.         public InputReader(InputStream stream) {
  125.             reader = new BufferedReader(new InputStreamReader(stream));
  126.             tokenizer = null;
  127.         }
  128.  
  129.         public String next() {
  130.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  131.                 try {
  132.                     tokenizer = new StringTokenizer(reader.readLine());
  133.                 }
  134.                 catch (IOException e) {
  135.                     throw new RuntimeException(e);
  136.                 }
  137.             }
  138.             return tokenizer.nextToken();
  139.         }
  140.  
  141.         public int nextInt() {
  142.             return Integer.parseInt(next());
  143.         }
  144.  
  145.         public double nextDouble() {
  146.             return Double.parseDouble(next());
  147.         }
  148.  
  149.         public float nextFloat() {
  150.             return Float.parseFloat(next());
  151.         }
  152.  
  153.         public long nextLong() {
  154.             return Long.parseLong(next());
  155.         }
  156.  
  157.         public BigInteger nextBigInteger() {
  158.             return new BigInteger(next());
  159.         }
  160.  
  161.     }
  162. }
Advertisement
Add Comment
Please, Sign In to add comment