UVa 846 - Steps

// UVa 846 - Steps

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for (int cases = scanner.nextInt(); cases > 0; cases--) {
            int from = scanner.nextInt(), to = scanner.nextInt();
            System.out.println(neededSteps(to - from));
        }
    }

    private static int neededSteps(int target) {
        if (target == 0) return 0;

        int x = (int) ((Math.sqrt(1 + 4 * target) - 1) / 2);
        int leftover = target - x * (x + 1);

        if (leftover == 0)
            return 2 * x;
        else if (leftover <= x + 1)
            return 2 * x + 1;
        else
            return 2 * x + 2;

    }

}

UVa 10245 - The Closest Pair Problem

// UVa 10245 - The Closest Pair Problem

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        for (int n = scanner.nextInt(); n != 0; n = scanner.nextInt()) {
            List<Point> points = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                points.add(new Point(scanner.nextDouble(), scanner.nextDouble()));
            }
            points.sort(Comparator.comparing(p -> p.x));

            ClosestPointsFinder cpf = new ClosestPointsFinder(points);
            double closestPointsDistance = cpf.getClosestPointsDistance();
            if (closestPointsDistance < 10000) {
                System.out.printf("%.4f\n", closestPointsDistance);
            } else {
                System.out.println("INFINITY");
            }
        }
    }

    private static class Point {
        final double x, y;

        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        double distance(Point other) {
            double x2 = Math.pow(this.x - other.x, 2);
            double y2 = Math.pow(this.y - other.y, 2);
            return Math.sqrt(x2 + y2);
        }
    }

    private static class ClosestPointsFinder {
        private static double INFINITY = 10000;
        private final List<Point> points;

        ClosestPointsFinder(List<Point> points) {
            this.points = points;
        }

        double getClosestPointsDistance() {
            return getClosestPointsDistance(0, points.size(), INFINITY);
        }

        private double getClosestPointsDistance(int start, int end, double distSoFar) {

            if (start + 2 == end) {
                return points.get(start).distance(points.get(start + 1));
            } else if (start + 1 >= end) {
                return INFINITY;
            }

            int mid = (start + end) / 2;

            double subDist = getClosestPointsDistance(start, mid, distSoFar);
            if (subDist < distSoFar)
                distSoFar = subDist;

            subDist = getClosestPointsDistance(mid, end, distSoFar);
            if (subDist < distSoFar)
                distSoFar = subDist;

            List<Point> strip = new ArrayList<>();
            for (int i = mid - 1; i >= start; i--) {
                if (points.get(i).x + distSoFar >= points.get(mid - 1).x) {
                    strip.add(points.get(i));
                } else {
                    break;
                }
            }
            for (int i = mid; i < end; i++) {
                if (points.get(mid - 1).x + distSoFar >= points.get(i).x) {
                    strip.add(points.get(i));
                } else {
                    break;
                }
            }
            strip.sort(Comparator.comparing(p -> p.y));

            for (int i = 0; i < strip.size(); i++) {
                for (int j = i + 1; j < strip.size() && j < i + 8; j++) {
                    subDist = strip.get(i).distance(strip.get(j));
                    if (subDist < distSoFar)
                        distSoFar = subDist;
                }
            }

            return distSoFar;
        }
    }
}

UVa 10419 - Sum-up the Primes

// UVa 10419 - Sum-up the Primes

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    private static final List<Integer> LEXICOGRAPHICALLY_SORTED_PRIMES = lexicographicallySortedPrimes();
    private static List<Integer> P;
    private static int t, n;
    private static boolean[][] canGet;
    private static int[][] lastIndex;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        for (int testCaseNumber = 1; true; testCaseNumber++) {
            n = scanner.nextInt();
            t = scanner.nextInt();
            if (n == 0 || t == 0) break;

            P = new ArrayList<>();
            for (Integer p : LEXICOGRAPHICALLY_SORTED_PRIMES) {
                if (p <= n) {
                    P.add(p);
                    if (p != 2)
                        P.add(p);
                }
            }

            canGet = new boolean[t + 1][n + 1];
            canGet[0][0] = true;
            lastIndex = new int[t + 1][n + 1];

            rec(0, 0, 0);

            System.out.printf("CASE %d:\n", testCaseNumber);
            if (canGet[t][n]) {
                int[] sol = new int[t + 1];
                int m = n;
                for (int a = t; a > 0; a--) {
                    sol[a] = P.get(lastIndex[a][m]);
                    m -= sol[a];
                }
                StringBuilder sb = new StringBuilder();
                sb.append(sol[1]);
                for (int a = 2; a <= t; a++) {
                    sb.append('+');
                    sb.append(sol[a]);
                }
                System.out.println(sb.toString());
            } else {
                System.out.println("No Solution.");
            }
        }
    }

    private static void rec(int a, int m, int z) {
        for (int pi = z; pi < P.size(); pi++) {
            int p = P.get(pi);

            int aa = a + 1;
            int mm = m + p;
            int zz = pi + 1;
            if (aa <= t && mm <= n && (!canGet[aa][mm] || pi < lastIndex[aa][mm])) {
                canGet[aa][mm] = true;
                lastIndex[aa][mm] = pi;
                if (canGet[t][n]) return;
                rec(aa, mm, zz);
                if (canGet[t][n]) return;
            }
        }
    }

    private static class Prime {
        final int p;
        final String s;

        Prime(int p) {
            this.p = p;
            this.s = String.valueOf(p);
        }
    }

    private static List<Integer> lexicographicallySortedPrimes() {
        boolean[] isComposite = new boolean[300];
        List<Prime> primes = new ArrayList<>();
        for (int i = 2; i < 300; i++) {
            if (!isComposite[i]) {
                for (int j = i * i; j < 300; j += i) {
                    isComposite[j] = true;
                }
                primes.add(new Prime(i));
            }
        }
        primes.sort(Comparator.comparing(a -> a.s));
        return primes.stream().map(a -> a.p).collect(Collectors.toList());
    }

}

UVa 1388 - Graveyard

// UVa 1388 - Graveyard

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextInt()) {
            int Nb = scanner.nextInt(); // number of statues at the beginning
            int Nadd = scanner.nextInt(); // statues to add
            int Ne = Nb + Nadd; // number of statues at the end

            BigDecimal Cb = BigDecimal.valueOf(10000).divide(BigDecimal.valueOf(Nb), MathContext.DECIMAL128);
            BigDecimal Ce = BigDecimal.valueOf(10000).divide(BigDecimal.valueOf(Ne), MathContext.DECIMAL128);

            BigDecimal allMovement = BigDecimal.ZERO;

            for (int i = 1; i < Nb; i++) {
                BigDecimal location = Cb.multiply(BigDecimal.valueOf(i));
                BigDecimal destination = location.divide(Ce, MathContext.DECIMAL128).setScale(0, RoundingMode.HALF_UP).multiply(Ce);
                BigDecimal movement = destination.subtract(location).abs();
                allMovement = allMovement.add(movement);
            }

            System.out.printf("%.4f\n", allMovement);
        }
    }
}
/*

for the i-th statue
its location is
  i*Cb
its destination is
  round(i*Cb / Ce) * Ce
so its movement is
  abs(round(i*Cb / Ce) * Ce - i*Cb)

Cb = 10,000 / Nb where Nb = number of statues at the beginning
Ce = 10,000 / Ne where Ne = number of statues at the end

sol = sum of abs(round(i*Cb / Ce) * Ce - i*Cb) for all i=0..Nb

*/

UVa 110 - Meta-Loopless Sorts

// UVa 110 - Meta-Loopless Sorts

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        for (int numberOfTestCases = scanner.nextInt(); numberOfTestCases > 0; numberOfTestCases--) {
            int n = scanner.nextInt();

            new PascalProgramPrinter(n).print();

            if (numberOfTestCases > 1)
                System.out.println();
        }

    }

    private static class PascalProgramPrinter {

        private static char[] VAR_IDS = new char[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};

        private final int n; // e.g. 3
        private final String vars; // e.g. "a,b,c"

        private char[] relativeOrdering;

        PascalProgramPrinter(int n) {
            this.n = n;
            this.vars = commaSeparated(VAR_IDS);
            this.relativeOrdering = new char[n + 1];
        }

        private String commaSeparated(char[] charArray) {
            StringBuilder sb = new StringBuilder();
            sb.append(charArray[0]);
            for (int i = 1; i < n; i++) {
                sb.append(',');
                sb.append(charArray[i]);
            }
            return sb.toString();
        }

        void print() {
            printHeader();
            printIfs();
            printFooter();
        }

        private void printHeader() {
            System.out.println("program sort(input,output);");
            System.out.println("var");
            System.out.println(vars + " : integer;");
            System.out.println("begin");
            System.out.println("  readln(" + vars + ");");
        }

        private void printIfs() {
            relativeOrdering[0] = 'a';
            printIfs('b', 1);
        }

        private void printIfs(char varToOrder, int level) {
            if (varToOrder >= 'a' + this.n) {
                printIdent(level);
                System.out.println("writeln(" + commaSeparated(relativeOrdering) + ")");
                return;
            }

            for (int pos = level; pos >= 0; pos--) {
                printIdent(level);
                if (pos < level)
                    System.out.print("else ");
                relativeOrdering[pos + 1] = relativeOrdering[pos];
                relativeOrdering[pos] = varToOrder;
                if (pos > 0)
                    printOneIf(relativeOrdering[pos - 1], relativeOrdering[pos]);
                else
                    System.out.println();
                printIfs((char) (varToOrder + 1), level + 1);
            }
            for (int pos = 0; pos < level; pos++)
                relativeOrdering[pos] = relativeOrdering[pos + 1];
        }

        private static void printIdent(int identLevel) {
            for (int i = 0; i < identLevel; i++)
                System.out.print("  ");
        }

        private static void printOneIf(char v1, char v2) {
            System.out.println(String.format("if %c < %c then", v1, v2));
        }

        private void printFooter() {
            System.out.println("end.");
        }
    }
}

UVa 465 - Overflow

// UVa 465 - Overflow

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {

            String line = scanner.nextLine();

            String[] tokens = line.split(" ");
            String sa = tokens[0];
            String sb = tokens[tokens.length - 1];
            char operator = '?';
            for (int i = 1; i < tokens.length - 1; i++)
                if (!tokens[i].equals("")) {
                    operator = tokens[i].charAt(0);
                    break;
                }

            BigInteger a = new BigInteger(sa);
            BigInteger b = new BigInteger(sb);

            BigInteger c = (operator == '+')
                    ? a.add(b)
                    : a.multiply(b);

            System.out.println(line);
            warnIfNecessary("first number", a);
            warnIfNecessary("second number", b);
            warnIfNecessary("result", c);
        }
    }

    private static final BigInteger LIMIT = BigInteger.valueOf(Integer.MAX_VALUE);

    private static void warnIfNecessary(String prefix, BigInteger number) {
        if (number.compareTo(LIMIT) > 0) {
            System.out.println(prefix + " too big");
        }
    }
}

UVa 908 - Re-connecting Computer Sites

// UVa 908 - Re-connecting Computer Sites

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int testCase = 0;
        while (scanner.hasNextInt()) {
            testCase++;
            if (testCase > 1)
                System.out.println();

            Mst mst = new Mst();

            int n = scanner.nextInt();
            for (int i = 1; i < n; i++) {
                int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt();
                mst.addEdge(a, b, c);
            }
            System.out.println(mst.getCurrentCost());

            int k = scanner.nextInt();
            for (int i = 0; i < k; i++) {
                int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt();
                mst.offerNewEdge(a, b, c);
            }
            System.out.println(mst.getCurrentCost());

            int m = scanner.nextInt();
            for (int i = 0; i < m; i++) {
                scanner.nextInt();
                scanner.nextInt();
                scanner.nextInt();
            }
        }
    }

    private static class Mst {

        private int currentCost = 0;
        private Map<Integer, Map<Integer, Edge>> matrix = new HashMap<>();

        public int getCurrentCost() {
            return currentCost;
        }

        public int offerNewEdge(int from, int to, int cost) {
            Edge costlyEdge = getMostCostlyEdgeInPath(from, to);
            if (costlyEdge.cost > cost) {
                removeEdge(costlyEdge);
                addEdge(from, to, cost);
            }
            return currentCost;
        }


        private Edge getMostCostlyEdgeInPath(int from, int to) {
            Queue<EdgePair> q = new LinkedList<>();
            q.add(new EdgePair(
                    new Edge(-1, from, 0),
                    new Edge(-1, from, 0)
            ));
            while (!q.isEmpty()) {
                EdgePair head = q.poll();
                int node = head.last.to;
                for (Integer next : matrix.get(node).keySet()) {
                    if (next == head.last.from) continue;
                    Edge edge = matrix.get(node).get(next);
                    Edge newCostlyEdge = edge.cost > head.costly.cost
                            ? edge : head.costly;
                    if (next == to)
                        return newCostlyEdge;
                    q.add(new EdgePair(
                            edge,
                            newCostlyEdge
                    ));
                }
            }
            return null;
        }

        private static class EdgePair {
            public Edge last, costly;

            public EdgePair(Edge last, Edge costly) {
                this.last = last;
                this.costly = costly;
            }
        }

        private static class Edge {

            public final int from, to, cost;

            public Edge(int from, int to, int cost) {
                this.from = from;
                this.to = to;
                this.cost = cost;
            }
        }

        private void removeEdge(Edge edge) {
            matrix.get(edge.from).remove(edge.to);
            matrix.get(edge.to).remove(edge.from);
            currentCost -= edge.cost;
        }

        public void addEdge(int from, int to, int cost) {
            addToMatrix(from, to, cost);
            addToMatrix(to, from, cost);
            currentCost += cost;
        }

        private void addToMatrix(int a, int b, int c) {
            if (!matrix.containsKey(a))
                matrix.put(a, new HashMap<>());
            matrix.get(a).put(b, new Edge(a, b, c));
        }

    }


}