Codeforces Round #190 (Div. 2) C Ciel and Robot

// Codeforces Round #190 (Div. 2) C Ciel and Robot

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 a = in.nextInt();
int b = in.nextInt();
String s = in.nextString();
int dx = 0;
int dy = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == 'L')
dx--;
else if (c == 'R')
dx++;
else if (c == 'D')
dy--;
else if (c == 'U')
dy++;
}
int repx = 0;
if (dx != 0)
repx = a / dx;
int repy = 0;
if (dy != 0)
repy = b / dy;
int rep = Math.max(repx, repy) - 100;
if (rep < 0)
rep = 0;
int px = rep * dx;
int py = rep * dy;
boolean located = false;
for (int k = 0; k < 200; k++) {
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == 'L')
px--;
else if (c == 'R')
px++;
else if (c == 'D')
py--;
else if (c == 'U')
py++;
if (px == a && py == b)
located = true;
}
}
if (a == 0 && b == 0)
located = true;
if (located)
out.println("Yes");
else
out.println("No");
}

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 #182 (Div. 2) B Eugeny and Play List

// Codeforces Round #182 (Div. 2) B Eugeny and Play List

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 M = in.nextInt();
        long[] c = new long[N + 1];
        long[] t = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            c[i] = in.nextLong();
            t[i] = in.nextLong();
        }
        long[] tstart = new long[N + 1];
        long[] tend = new long[N + 1];
        tstart[1] = 1;
        tend[1] = 1 + (c[1] * t[1]) - 1;
        for (int i = 2; i <= N; i++) {
            tstart[i] = tend[i - 1] + 1;
            tend[i] = tstart[i] + (c[i] * t[i]) - 1;
        }

        int[] v = new int[M + 1];
        in.nextLine();
        String ln = in.nextLine();
        String[] s = ln.split(" ");
        for (int i = 1; i <= M; i++) {
            v[i] = Integer.valueOf(s[i - 1]);
        }

        StringBuilder sb = new StringBuilder("");
        for (int i = 1; i <= M; i++) {
            int L = 1;
            int R = N;
            int tm = v[i];
            while (L <= R) {
                int idx = (L + R) / 2;
                if (tm >= tstart[idx] && tm <= tend[idx]) {
                    sb.append(idx);
                    sb.append("\n");
                    break;
                }
                if (tm < tstart[idx]) {
                    R = idx - 1;
                }
                else {
                    L = idx + 1;
                }
            }
        }
        out.println(sb.toString());
    }

    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();
        }

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

    }

}

Codeforces Round #176 (Div. 2) B Pipeline

// Codeforces Round #176 (Div. 2) B Pipeline

import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.*;
import java.text.*;
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;// change to false 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
    {
        Long n = in.nextLong();
        Long k = in.nextLong();
        if (n == 1) {
            out.println(0);
            return;
        }

        Long left = 2L;
        Long right = k;
        Long totSplitter = 0L;
        Long minAns = Long.MAX_VALUE;
        Long mid;
        while (true) {
            mid = (left + right) / 2;
            totSplitter = GetOut(mid, k);
            if (totSplitter >= n) {
                left = mid + 1;
                minAns = Math.min(minAns, k - mid + 1);
            }
            else {
                right = mid - 1;
            }
            if (left > right)
                break;
        }
        if (minAns == Long.MAX_VALUE)
            out.println(-1);
        else
            out.println(minAns);
    }

    static long GetOut(long k1, long k)
    {
        return k1 + (k1 + k - 1) * (k - k1) / 2;
    }

    // =====================================
    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();
        }

    }

}

Codeforces Round #168 (Div. 2) C. k-Multiple Free Set

// Codeforces Round #168 (Div. 2) C. k-Multiple Free Set

import java.io.*;
import java.math.*;
import java.text.*;
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;// change to false 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 K = in.nextInt();
        int ans;
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);

        long max = a[N - 1];
        boolean[] used = new boolean[N];
        for (int i = 0; i < N; i++) {
            used[i] = true;
        }

        ans = 0;
        for (int i = 0; i < N; i++) {
            if (used[i]) {
                ans++;
                long mul = K * (long) a[i];
                if (mul <= max) {
                    int index = Arrays.binarySearch(a, (int) mul);
                    if (index >= 0)
                    {
                        used[index] = false;
                    }
                }
            }
        }

        if (K == 1)
            ans = N;
        out.println(ans);

    }

    // =====================================
    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();
        }

    }

}

Codeforces Round #154 (Div. 2): B - Physics Practical

// Codeforces Round #154 (Div. 2): B - Physics Practical 

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

//codeforces
public class Main2 {
    private static Scanner in;
    private static PrintStream out = System.out;

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

    private static void solve()
    {
        int N = in.nextInt();
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            c[i] = in.nextInt();
        }
        Arrays.sort(c);
        Map<Integer, Integer> cntGreaterThanX = new HashMap<Integer, Integer>();
        Map<Integer, Integer> cntLessThanX = new HashMap<Integer, Integer>();

        int lastnum = c[0];
        cntLessThanX.put(c[0], 0);
        for (int i = 1; i < N; i++) {
            if (c[i] != lastnum) {
                cntLessThanX.put(c[i], i);
                cntGreaterThanX.put(c[i - 1], N - i);
                lastnum = c[i];
            }
        }
        cntGreaterThanX.put(c[N - 1], 0);

        int minRemove = Integer.MAX_VALUE;
        for (int istart = 0; istart < N; istart++) {
            if (istart > 0 && c[istart] == c[istart - 1])
                continue;
            int remove = cntLessThanX.get(c[istart]);
            // binary search
            int L = istart;
            int R = N - 1;
            int iend = (L + R + 1) / 2;
            while (L < R) {
                iend = (L + R + 1) / 2;
                if (c[iend] == 2 * c[istart]) {
                    break;
                }
                if (c[iend] < 2 * c[istart]) {
                    L = iend + 1;
                }
                else {
                    R = iend - 1;
                }
            }
            while (c[iend] < 2 * c[istart] && iend < N - 1) {
                iend++;
            }
            while (c[iend] > 2 * c[istart]) {
                iend--;
            }
            remove += cntGreaterThanX.get(c[iend]);
            minRemove = Math.min(minRemove, remove);
        }
        out.println(minRemove);
    }
}

Codeforces Round #153 (Div. 2): C - Points on Line

//  Codeforces Round #153 (Div. 2): C - Points on Line

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

public class Main2 {
    private static Scanner in;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        in = new Scanner(System.in);
        if (LOCAL_TEST) {
            in = new Scanner(new FileInputStream("E:\\zin2.txt"));
        }

        Integer N = in.nextInt();
        Long D = in.nextLong();
        Long[] nums = new Long[N];
        for (int i = 0; i < N; i++) {
            nums[i] = in.nextLong();
        }

        long[] plusplus = new long[100001];
        plusplus[0] = 0;
        for (int i = 1; i < plusplus.length; i++) {
            plusplus[i] += plusplus[i - 1] + i;
        }
        Long cnt = 0L;
        for (int i = 0; i < N - 2; i++) {
            int iendMin = i + 2;
            int iendMax = N - 1;
            int iL = iendMin;
            int iR = iendMax;
            int iend = (iL + iR) / 2;
            while (iL < iR) {
                if (nums[iend] - nums[i] > D)
                    iR = iend - 1;
                else
                    iL = iend + 1;
                iend = (iL + iR) / 2;
            }
            if (nums[iend] - nums[i] > D)
                iend--;
            int nn = iend - i - 1;
            // calc 1+2+3+...+nn
            if (nn > 0)
            {
                long add = plusplus[nn];
                cnt += add;
            }
        }
        System.out.println(cnt);

    }

}