Codeforces Round #201 (Div. 2) A Difference Row

// Codeforces Round #201 (Div. 2) A Difference Row
// Problem statement: http://codeforces.com/contest/347/problem/A

import java.io.*;
import java.math.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
int[] x = new int[n];
for (int i = 0; i < x.length; i++)
x[i] = in.nextInt();
Arrays.sort(x);
int tmp = x[0];
x[0] = x[n - 1];
x[n - 1] = tmp;
for (int i = 0; i < x.length; i++) {
if (i > 0) {
out.print(" ");
}
out.print(x[i]);
}
out.println();
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #223 (Div. 2) B Sereja and Stairs

// Codeforces Round #223 (Div. 2) B Sereja and Stairs
// Problem: http://codeforces.com/contest/381/problem/B

import java.io.*;
import java.math.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
Integer[] x = new Integer[n];
for (int i = 0; i < x.length; i++) {
x[i] = in.nextInt();
}
Arrays.sort(x, Collections.reverseOrder());
ArrayList<Integer> list2 = new ArrayList<Integer>();
HashSet<Integer> set1 = new HashSet<Integer>();
list2.add(x[0]);
for (int i = 1; i < x.length; i++) {
if (x[i] < x[i - 1]) {
list2.add(x[i]);
}
else {
if (!x[i].equals(x[0])) {
set1.add(x[i]);
}
}
}
ArrayList<Integer> list1 = new ArrayList<Integer>();
list1.addAll(set1);
Collections.sort(list1);
list1.addAll(list2);
out.println(list1.size());
for (int i = 0; i < list1.size(); i++) {
if (i > 0)
out.print(" ");
out.print(list1.get(i));
}
out.println();
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #223 (Div. 2) A Sereja and Dima

// Codeforces Round #223 (Div. 2) A Sereja and Dima
import java.io.*;
import java.math.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
Integer[] x = new Integer[n];
for (int i = 0; i < x.length; i++) {
x[i] = in.nextInt();
}
int p1 = 0;
int p2 = 0;
int idxLeft = 0;
int idxRight = n - 1;
int i = 0;
while (idxLeft <= idxRight) {
int chosen;
if (x[idxLeft] > x[idxRight]) {
chosen = x[idxLeft];
idxLeft++;
}
else {
chosen = x[idxRight];
idxRight--;
}
if (i % 2 == 0)
p1 += chosen;
else
p2 += chosen;
i++;
}
out.print(p1);
out.print(" ");
out.print(p2);
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #224 (Div. 2) C Arithmetic Progression

//Codeforces Round #224 (Div. 2) C Arithmetic Progression
import java.io.*;
import java.math.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
int[] x = new int[n];
for (int i = 0; i < x.length; i++) {
x[i] = in.nextInt();
}
ArrayList<Integer> ansList = new ArrayList<Integer>();
if (n == 1) {
out.println(-1);
return;
}
else {
Arrays.sort(x);
int minDiff = Integer.MAX_VALUE;
if (n == 2) {
if ((x[1] - x[0]) % 2 == 0) {
minDiff = (x[1] - x[0]);
ansList.add(x[0] - minDiff);
if (minDiff > 0)
ansList.add(x[0] + minDiff / 2);
if (minDiff > 0)
ansList.add(x[1] + minDiff);
}
else {
minDiff = (x[1] - x[0]);
ansList.add(x[0] - minDiff);
ansList.add(x[1] + minDiff);
}
}
else {
HashSet<Integer> diffSet = new HashSet<Integer>();
for (int i = 1; i < x.length; i++) {
int diff = x[i] - x[i - 1];
diffSet.add(diff);
minDiff = Math.min(diff, minDiff);
}
if (diffSet.size() == 1) {
ansList.add(x[0] - minDiff);
if (minDiff > 0)
ansList.add(x[x.length - 1] + minDiff);
}
else if (diffSet.size() > 2) {
out.println(0);
return;
}
else {// if (diffSet.size() == 2) {
if (minDiff == 0) {
out.println(0);
return;
}

boolean added = false;
for (int i = 0; i < x.length - 1; i++) {
if (x[i + 1] - x[i] == minDiff)
continue;
else if (x[i + 1] - x[i] == 2 * minDiff) {
if (!added) {
ansList.add(x[i] + minDiff);
added = true;
}
else {
out.println(0);
return;
}
}
else {
out.println(0);
return;
}
}
}
}
}
out.println(ansList.size());
for (int i = 0; i < ansList.size(); i++) {
out.print(ansList.get(i));
out.print(" ");
}
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Croc Champ 2013 - Round 2 (Div. 2 Edition) A Ksusha and Array

//Croc Champ 2013 - Round 2 (Div. 2 Edition) A Ksusha and Array
import java.io.*;
import java.math.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
    private static MyScanner in;
    private static PrintStream out;
    private static boolean LOCAL_TEST = false;

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        int num = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] % num != 0) {
                num = -1;
                break;
            }
        }
        out.println(num);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        out = System.out;
        try {
            String cname = System.getenv("COMPUTERNAME");
            LOCAL_TEST = (cname.equals("ALPHA530"));
        } catch (Exception e) {
        }
        if (LOCAL_TEST) {
            in = new MyScanner("E:\\zin.txt");
        }
        else {
            boolean usingFileForIO = false;
            if (usingFileForIO) {
                // using input.txt and output.txt as I/O
                in = new MyScanner("input.txt");
                out = new PrintStream("output.txt");
            }
            else {
                in = new MyScanner();
                out = System.out;
            }
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

    }

}

Google Code Jam Round 1A 2008 A Minimum Scalar Product

// Google Code Jam Round 1A 2008 A Minimum Scalar Product
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        in.nextLine();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ": ");
            solveCase();
        }
    }

    private static void solveCase() throws IOException {
        int n = in.nextInt();
        long[] x = new long[n];
        long[] y = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = in.nextLong();
        }
        for (int i = 0; i < n; i++) {
            y[i] = in.nextLong();
        }
        Arrays.sort(x);
        Arrays.sort(y);
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += x[i] * y[n - 1 - i];
        }
        out.println(sum);
    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}

Codeforces Round #159 (Div. 2) A - Sockets

// Codeforces Round #159 (Div. 2) A - Sockets

import java.io.*;
import java.math.*;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.*;

//codeforces
public class MainCodeforces1 {
    private static MyScanner in;
    private static PrintStream out;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        out = System.out;
        if (LOCAL_TEST) {
            in = new MyScanner("E:\\zin2.txt");
        }
        else {
            boolean usingFileForIO = false;
            if (usingFileForIO) {
                // using input.txt and output.txt as I/O
                in = new MyScanner("input.txt");
                out = new PrintStream("output.txt");
            }
            else {
                in = new MyScanner();
                out = System.out;
            }
        }

        solve();
    }

    private static void solve() throws IOException
    {
        int N = in.nextInt();
        int M = in.nextInt();
        int K = in.nextInt();
        Integer[] A = new Integer[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = in.nextInt();
        }
        Arrays.sort(A, Collections.reverseOrder());

        int nsockets = K;
        if (nsockets >= M)
        {
            out.println(0);
            return;
        }
        for (int i = 0; i < N; i++) {
            nsockets += A[i] - 1;
            if (nsockets >= M)
            {
                out.println(i + 1);
                return;
            }
        }

        out.println(-1);
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

    }

}