Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.BufferedWriter;
- import java.io.File;
- import java.io.IOException;
- import java.io.InputStream;
- import java.io.InputStreamReader;
- import java.io.OutputStreamWriter;
- import java.io.PrintWriter;
- import java.math.BigInteger;
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.List;
- import java.util.Map;
- import java.util.Scanner;
- import java.util.SortedSet;
- import java.util.StringTokenizer;
- /**
- * <b> Algorithm on Codeforces. Problem C div 2 </b> </br>
- * @author Huynh Quang Thao
- *
- */
- public class Main {
- public static void main(String[] args) throws Exception {
- Main main = new Main();
- main.run();
- }
- public void run() throws Exception {
- Scanner sc = null;
- PrintWriter pr = null;
- pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
- sc = new Scanner(new File("input.txt"));
- int n = sc.nextInt();
- ArrayList<Integer> less = new ArrayList<>();
- ArrayList<Integer> more = new ArrayList<>();
- ArrayList<Integer> none = new ArrayList<>();
- for (int i = 0; i < 2*n; i++) {
- double a = sc.nextDouble();
- int con = (int) (a * 1000);
- if (con % 1000 == 0 || con % 1000 == 500) none.add(con);
- else if (con % 1000 < 500) less.add(con);
- else more.add(con);
- }
- Collections.sort(less);
- Collections.sort(more);
- Collections.reverse(more);
- System.out.println(none.size());
- System.out.println(more.size());
- System.out.println(less.size());
- if (less.size() > more.size()) {
- ArrayList<Integer> tmp = less;
- less = more;
- more = tmp;
- }
- int start = 0;
- int end = 0;
- int pivot = 0;
- long sum = 0;
- if (more.size() - less.size() <= none.size()) {
- // nothing strange happened
- }
- // more.size() - less.size() > none.size()
- else {
- start = less.size() + none.size();
- end = more.size();
- pivot = start - 1;
- List<Integer> sub = more.subList(start, end);
- if (sub.get(0) > sub.get(1)) Collections.reverse(sub);
- for (int i = 0; i < sub.size() / 2; i++) {
- sum += sub.get(i) - (sub.get(i) % 1000); // round down
- int ops = sub.size() - 1 - i;
- sum += sub.get(ops) % 1000 + (sub.get(i) % 1000 - 1000); // round up
- }
- }
- // sum all elements
- for (int i = 0; i< none.size(); i++) {
- if (none.get(i) % 1000 == 500) sum += 500;
- }
- for (int i = 0; i < less.size(); i++) {
- if (less.get(i) % 1000 < 500) sum += less.get(i) - (less.get(i) % 1000);
- else sum += less.get(i) % 1000 + (less.get(i) % 1000 - 1000);
- }
- for (int i = 0; i <= pivot; i++) {
- if (more.get(i) % 1000 < 500) sum += more.get(i) - (more.get(i) % 1000);
- else sum += more.get(i) % 1000 + (more.get(i) % 1000 - 1000);
- }
- System.out.println(sum);
- pr.close();
- sc.close();
- }
- public boolean check(ArrayList<Integer> list) {
- // assume size >= 2
- int d = list.get(1) - list.get(0);
- for (int i = 1; i < list.size(); i++) {
- if (list.get(i) - list.get(i-1) != d) return false;
- }
- return true;
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream));
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- }
- catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public double nextDouble() {
- return Double.parseDouble(next());
- }
- public float nextFloat() {
- return Float.parseFloat(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public BigInteger nextBigInteger() {
- return new BigInteger(next());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment