// Codeforces Round #150 (Div. 2) : C - The Brand New Function
import java.io.*;
import java.math.*;
import java.util.*;
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[] nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = in.nextInt();
}
Set<Integer> set = new HashSet<Integer>();
Set<Integer> tmp = new HashSet<Integer>();
Set<Integer> tmpset;
int k = nums[0];
set.add(k);
tmp.add(k);
for (int i = 1; i < N; i++) {
k = nums[i];
tmpset = new HashSet<Integer>();
tmpset.add(k);
for (Integer x : tmp) {
tmpset.add(x | k);
}
tmp = tmpset;
for (Integer xx : tmpset) {
set.add(xx);
}
}
int cnt = set.size();
out.print(cnt);
}
static class MyScanner {
StreamTokenizer in;
public MyScanner() throws IOException
{
Reader r = new BufferedReader(new InputStreamReader(System.in));
in = new StreamTokenizer(r);
}
public MyScanner(String inputFile) throws IOException {
Reader r;
r = new BufferedReader(new FileReader(inputFile));
in = new StreamTokenizer(r);
}
public int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
public double nextDouble() throws IOException {
in.nextToken();
return in.nval;
}
public String nextString() throws IOException {
in.nextToken();
return in.sval;
}
}
}
Some solution examples of problems in topcoder, codeeval, google code jam, interviewstreet, onlinejudge-uva, codeforces, projecteuler, etc
Tuesday, December 18, 2012
Sunday, December 16, 2012
Codeforces Round #150 (Div. 2): B. Undoubtedly Lucky Numbers
// Codeforces Round #150 (Div. 2): B. Undoubtedly Lucky Numbers
import java.io.*;
import java.math.*;
import java.util.*;
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();
cnt = 0;
dfs(0, N);
out.print(cnt);
}
static int cnt;
static Set<Integer> set = new HashSet<Integer>();
private static void dfs(int x, int N) {
if (x > N)
return;
for (int i = 0; i <= 9; i++) {
int xx = x * 10 + i;
if (xx > 0 && xx <= N) {
int test = xx;
set.clear();
while (test > 0) {
set.add(test % 10);
test = test / 10;
if (set.size() > 2)
break;
}
if (set.size() <= 2) {
cnt++;
dfs(xx, N);
}
}
}
}
static class MyScanner {
StreamTokenizer in;
public MyScanner() throws IOException
{
Reader r = new BufferedReader(new InputStreamReader(System.in));
in = new StreamTokenizer(r);
}
public MyScanner(String inputFile) throws IOException {
Reader r;
r = new BufferedReader(new FileReader(inputFile));
in = new StreamTokenizer(r);
}
public int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
public double nextDouble() throws IOException {
in.nextToken();
return in.nval;
}
public String nextString() throws IOException {
in.nextToken();
return in.sval;
}
}
}
import java.io.*;
import java.math.*;
import java.util.*;
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();
cnt = 0;
dfs(0, N);
out.print(cnt);
}
static int cnt;
static Set<Integer> set = new HashSet<Integer>();
private static void dfs(int x, int N) {
if (x > N)
return;
for (int i = 0; i <= 9; i++) {
int xx = x * 10 + i;
if (xx > 0 && xx <= N) {
int test = xx;
set.clear();
while (test > 0) {
set.add(test % 10);
test = test / 10;
if (set.size() > 2)
break;
}
if (set.size() <= 2) {
cnt++;
dfs(xx, N);
}
}
}
}
static class MyScanner {
StreamTokenizer in;
public MyScanner() throws IOException
{
Reader r = new BufferedReader(new InputStreamReader(System.in));
in = new StreamTokenizer(r);
}
public MyScanner(String inputFile) throws IOException {
Reader r;
r = new BufferedReader(new FileReader(inputFile));
in = new StreamTokenizer(r);
}
public int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
public double nextDouble() throws IOException {
in.nextToken();
return in.nval;
}
public String nextString() throws IOException {
in.nextToken();
return in.sval;
}
}
}
Saturday, December 15, 2012
Codeforces Round #150 (Div. 2): A - Dividing Orange
// Codeforces Round #150 (Div. 2): A - Dividing Orange
import java.io.*;
import java.math.*;
import java.util.*;
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 K = in.nextInt();
// int[] nums = new int[K];
boolean[] used = new boolean[N * K + 1];
for (int i = 1; i <= N * K; i++) {
used[i] = false;
}
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int i = 1; i <= K; i++) {
int x = in.nextInt();
List<Integer> l = new ArrayList<Integer>();
l.add(x);
used[x] = true;
map.put(i, l);
}
int iused = 1;
for (int i = 1; i <= K; i++) {
List<Integer> ls = map.get(i);
while (ls.size() < N) {
while (used[iused]) {
iused++;
}
used[iused] = true;
ls.add(iused);
}
map.put(i, ls);
}
for (int i = 1; i <= K; i++) {
List<Integer> ls = map.get(i);
for (int j = 0; j < ls.size(); j++) {
if (j > 0)
out.print(" ");
out.print(ls.get(j));
}
out.println();
}
}
static class MyScanner {
StreamTokenizer in;
public MyScanner() throws IOException
{
Reader r = new BufferedReader(new InputStreamReader(System.in));
in = new StreamTokenizer(r);
}
public MyScanner(String inputFile) throws IOException {
Reader r;
r = new BufferedReader(new FileReader(inputFile));
in = new StreamTokenizer(r);
}
public int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
public double nextDouble() throws IOException {
in.nextToken();
return in.nval;
}
public String nextString() throws IOException {
in.nextToken();
return in.sval;
}
}
}
import java.io.*;
import java.math.*;
import java.util.*;
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 K = in.nextInt();
// int[] nums = new int[K];
boolean[] used = new boolean[N * K + 1];
for (int i = 1; i <= N * K; i++) {
used[i] = false;
}
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int i = 1; i <= K; i++) {
int x = in.nextInt();
List<Integer> l = new ArrayList<Integer>();
l.add(x);
used[x] = true;
map.put(i, l);
}
int iused = 1;
for (int i = 1; i <= K; i++) {
List<Integer> ls = map.get(i);
while (ls.size() < N) {
while (used[iused]) {
iused++;
}
used[iused] = true;
ls.add(iused);
}
map.put(i, ls);
}
for (int i = 1; i <= K; i++) {
List<Integer> ls = map.get(i);
for (int j = 0; j < ls.size(); j++) {
if (j > 0)
out.print(" ");
out.print(ls.get(j));
}
out.println();
}
}
static class MyScanner {
StreamTokenizer in;
public MyScanner() throws IOException
{
Reader r = new BufferedReader(new InputStreamReader(System.in));
in = new StreamTokenizer(r);
}
public MyScanner(String inputFile) throws IOException {
Reader r;
r = new BufferedReader(new FileReader(inputFile));
in = new StreamTokenizer(r);
}
public int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
public double nextDouble() throws IOException {
in.nextToken();
return in.nval;
}
public String nextString() throws IOException {
in.nextToken();
return in.sval;
}
}
}
Friday, December 14, 2012
Codeforces Round #154 (Div. 2): A. Cards with Numbers
// Codeforces Round #154 (Div. 2): A. Cards with Numbers
import java.io.*;
import java.math.*;
import java.util.*;
//codeforces
public class Main2 {
private static MyScanner 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
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin2.txt");
}
else {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
// in = new MyScanner(true);
out = new PrintStream("output.txt");
}
solve();
}
private static void solve() throws IOException
{
int N = in.nextInt();
List<Integer>[] mm = new ArrayList[5001];
for (int i = 0; i <= 5000; i++) {
mm[i] = new ArrayList<Integer>();
}
for (int i = 0; i < 2 * N; i++) {
int k = in.nextInt();
mm[k].add(i + 1);
}
boolean flag = false;
for (List<Integer> list : mm) {
if (list.size() % 2 == 1) {
flag = true;
break;
}
}
if (flag) {
out.println(-1);
}
else {
StringBuilder sb = new StringBuilder("");
for (List<Integer> list : mm) {
for (int j = 0; j < list.size(); j += 2) {
sb.append(list.get(j));
sb.append(" ");
sb.append(list.get(j + 1));
sb.append("\n");
}
}
out.println(sb);
}
}
}
class MyScanner {
StreamTokenizer in;
public MyScanner() throws IOException
{
this("input.txt");
}
public MyScanner(String inputFile) throws IOException {
Reader r;
r = new BufferedReader(new FileReader(inputFile));
in = new StreamTokenizer(r);
}
public MyScanner(boolean usingStdin)
{
if (usingStdin)
{
Reader r;
r = new BufferedReader(new InputStreamReader(System.in));
in = new StreamTokenizer(r);
}
}
public int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
public double nextDouble() throws IOException {
in.nextToken();
return in.nval;
}
public String nextString() throws IOException {
in.nextToken();
return in.sval;
}
}
import java.io.*;
import java.math.*;
import java.util.*;
//codeforces
public class Main2 {
private static MyScanner 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
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin2.txt");
}
else {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
// in = new MyScanner(true);
out = new PrintStream("output.txt");
}
solve();
}
private static void solve() throws IOException
{
int N = in.nextInt();
List<Integer>[] mm = new ArrayList[5001];
for (int i = 0; i <= 5000; i++) {
mm[i] = new ArrayList<Integer>();
}
for (int i = 0; i < 2 * N; i++) {
int k = in.nextInt();
mm[k].add(i + 1);
}
boolean flag = false;
for (List<Integer> list : mm) {
if (list.size() % 2 == 1) {
flag = true;
break;
}
}
if (flag) {
out.println(-1);
}
else {
StringBuilder sb = new StringBuilder("");
for (List<Integer> list : mm) {
for (int j = 0; j < list.size(); j += 2) {
sb.append(list.get(j));
sb.append(" ");
sb.append(list.get(j + 1));
sb.append("\n");
}
}
out.println(sb);
}
}
}
class MyScanner {
StreamTokenizer in;
public MyScanner() throws IOException
{
this("input.txt");
}
public MyScanner(String inputFile) throws IOException {
Reader r;
r = new BufferedReader(new FileReader(inputFile));
in = new StreamTokenizer(r);
}
public MyScanner(boolean usingStdin)
{
if (usingStdin)
{
Reader r;
r = new BufferedReader(new InputStreamReader(System.in));
in = new StreamTokenizer(r);
}
}
public int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
public double nextDouble() throws IOException {
in.nextToken();
return in.nval;
}
public String nextString() throws IOException {
in.nextToken();
return in.sval;
}
}
Thursday, December 13, 2012
Topcoder SRM 564 DIV 2, L1: FauxPalindromes
// Topcoder SRM 564 DIV 2, L1: FauxPalindromes
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
FauxPalindromes obj = new FauxPalindromes();
System.out.println(
// obj.numPairs(numbers)
);
}
}
// change to public before submit
public class FauxPalindromes {
public String classifyIt(String word) {
String rev = (new StringBuffer(word)).reverse().toString();
if (word.equals(rev))
return "PALINDROME";
String word2 = word.substring(0, 1);
for (int i = 1; i < word.length(); i++) {
if (word.charAt(i) == word.charAt(i - 1))
continue;
else
word2 = word2 + String.valueOf(word.charAt(i));
}
if (word2.equals((new StringBuffer(word2)).reverse().toString()))
return "FAUX";
return "NOT EVEN FAUX";
}
}
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
FauxPalindromes obj = new FauxPalindromes();
System.out.println(
// obj.numPairs(numbers)
);
}
}
// change to public before submit
public class FauxPalindromes {
public String classifyIt(String word) {
String rev = (new StringBuffer(word)).reverse().toString();
if (word.equals(rev))
return "PALINDROME";
String word2 = word.substring(0, 1);
for (int i = 1; i < word.length(); i++) {
if (word.charAt(i) == word.charAt(i - 1))
continue;
else
word2 = word2 + String.valueOf(word.charAt(i));
}
if (word2.equals((new StringBuffer(word2)).reverse().toString()))
return "FAUX";
return "NOT EVEN FAUX";
}
}
Tuesday, December 11, 2012
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);
}
}
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 #154 (Div. 2): A - Boys and Girls
// Codeforces Round #154 (Div. 2): A - Boys and Girls
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"));
}
in = new Scanner(new FileInputStream("input.txt"));
out = new PrintStream("output.txt");
solve();
}
private static void solve()
{
int N = in.nextInt();
int M = in.nextInt();
boolean moreBoys = false;
if (N >= M)
moreBoys = true;
while (N > 0 || M > 0) {
if (moreBoys) {
if (N > 0) {
out.print("B");
N--;
}
if (M > 0) {
out.print("G");
M--;
}
}
else {
if (M > 0) {
out.print("G");
M--;
}
if (N > 0) {
out.print("B");
N--;
}
}
}
System.out.println("");
}
}
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"));
}
in = new Scanner(new FileInputStream("input.txt"));
out = new PrintStream("output.txt");
solve();
}
private static void solve()
{
int N = in.nextInt();
int M = in.nextInt();
boolean moreBoys = false;
if (N >= M)
moreBoys = true;
while (N > 0 || M > 0) {
if (moreBoys) {
if (N > 0) {
out.print("B");
N--;
}
if (M > 0) {
out.print("G");
M--;
}
}
else {
if (M > 0) {
out.print("G");
M--;
}
if (N > 0) {
out.print("B");
N--;
}
}
}
System.out.println("");
}
}
Monday, December 10, 2012
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);
}
}
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);
}
}
Friday, December 7, 2012
Codeforces Round #153 (Div. 2): B - Unsorting Array
// Codeforces Round #153 (Div. 2): B - Unsorting Array
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"));
}
int N = in.nextInt();
int[] nums = new int[N];
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < N; i++) {
nums[i] = in.nextInt();
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
if (!map.containsKey(nums[i]))
map.put(nums[i], 1);
else
map.put(nums[i], map.get(nums[i]) + 1);
}
if (N <= 2) {
System.out.println(-1);
return;
}
if (map.size() == 1) {
System.out.println(-1);
return;
}
// for
boolean isSortedAsc = isAscending(nums);
boolean isSortedDesc = isDescending(nums);
if (isSortedAsc || isSortedDesc) {
for (int i = 0; i < N - 1; i++) {
if (nums[i] != nums[i + 1]) {
System.out.println((i + 1) + " " + (i + 2));
return;
}
}
}
else {
for (int i = 1; i < N - 1; i++) {
int x = nums[i];
if (x != min && x != max && x != nums[0]) {
System.out.println((i + 1) + " " + 1);
return;
}
if (x != min && x != max && x != nums[N - 1]) {
System.out.println((i + 1) + " " + (N));
return;
}
}
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (nums[i] != nums[j]) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
if (!isSorted(nums)) {
System.out.println((i + 1) + " " + (j + 1));
return;
}
else {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
}
}
System.out.println(-1);
}
static boolean isSorted(int[] n)
{
return (isAscending(n) || isDescending(n));
}
static boolean isAscending(int[] n) {
boolean isSortedAscending = true;
for (int i = 1; i < n.length; i++) {
if (n[i] < n[i - 1])
isSortedAscending = false;
}
return isSortedAscending;
}
static boolean isDescending(int[] n) {
boolean isSortedDescending = true;
for (int i = 1; i < n.length; i++) {
if (n[i] > n[i - 1])
isSortedDescending = false;
}
return isSortedDescending;
}
}
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"));
}
int N = in.nextInt();
int[] nums = new int[N];
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < N; i++) {
nums[i] = in.nextInt();
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
if (!map.containsKey(nums[i]))
map.put(nums[i], 1);
else
map.put(nums[i], map.get(nums[i]) + 1);
}
if (N <= 2) {
System.out.println(-1);
return;
}
if (map.size() == 1) {
System.out.println(-1);
return;
}
// for
boolean isSortedAsc = isAscending(nums);
boolean isSortedDesc = isDescending(nums);
if (isSortedAsc || isSortedDesc) {
for (int i = 0; i < N - 1; i++) {
if (nums[i] != nums[i + 1]) {
System.out.println((i + 1) + " " + (i + 2));
return;
}
}
}
else {
for (int i = 1; i < N - 1; i++) {
int x = nums[i];
if (x != min && x != max && x != nums[0]) {
System.out.println((i + 1) + " " + 1);
return;
}
if (x != min && x != max && x != nums[N - 1]) {
System.out.println((i + 1) + " " + (N));
return;
}
}
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (nums[i] != nums[j]) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
if (!isSorted(nums)) {
System.out.println((i + 1) + " " + (j + 1));
return;
}
else {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
}
}
System.out.println(-1);
}
static boolean isSorted(int[] n)
{
return (isAscending(n) || isDescending(n));
}
static boolean isAscending(int[] n) {
boolean isSortedAscending = true;
for (int i = 1; i < n.length; i++) {
if (n[i] < n[i - 1])
isSortedAscending = false;
}
return isSortedAscending;
}
static boolean isDescending(int[] n) {
boolean isSortedDescending = true;
for (int i = 1; i < n.length; i++) {
if (n[i] > n[i - 1])
isSortedDescending = false;
}
return isSortedDescending;
}
}
Tuesday, December 4, 2012
Topcoder SRM 466 DIV 2, L2: LotteryCheating
// Topcoder SRM 466 DIV 2, L2: LotteryCheating
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
LotteryCheating obj = new LotteryCheating();
System.out.println(
obj.minimalChange("7654321")
);
}
}
// change to public before submit
public class LotteryCheating {
List<String> winnums;
public int minimalChange(String ID) {
int len = ID.length();
winnums = new ArrayList<String>();
for (long i = 0; i <= 100000; i++) {
long sqr = i * i;
String sn = String.valueOf(sqr);
if (sn.length() > len)
break;
String s = "0000000000" + sn;
s = s.substring(s.length() - len);
winnums.add(s);
}
int min = Integer.MAX_VALUE;
for (String s : winnums) {
min = Math.min(min, CountDiff(s, ID));
}
return min;
}
private int CountDiff(String s, String id) {
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != id.charAt(i))
cnt++;
}
return cnt;
}
}
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
LotteryCheating obj = new LotteryCheating();
System.out.println(
obj.minimalChange("7654321")
);
}
}
// change to public before submit
public class LotteryCheating {
List<String> winnums;
public int minimalChange(String ID) {
int len = ID.length();
winnums = new ArrayList<String>();
for (long i = 0; i <= 100000; i++) {
long sqr = i * i;
String sn = String.valueOf(sqr);
if (sn.length() > len)
break;
String s = "0000000000" + sn;
s = s.substring(s.length() - len);
winnums.add(s);
}
int min = Integer.MAX_VALUE;
for (String s : winnums) {
min = Math.min(min, CountDiff(s, ID));
}
return min;
}
private int CountDiff(String s, String id) {
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != id.charAt(i))
cnt++;
}
return cnt;
}
}
Topcoder SRM 466 DIV 2, L1: LotteryTicket
// Topcoder SRM 466 DIV 2, L1: LotteryTicket
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
LotteryTicket obj = new LotteryTicket();
System.out.println(
obj.buy(10, 1, 5, 10, 50)
);
}
}
// change to public before submit
class LotteryTicket {
public String buy(int price, int b1, int b2, int b3, int b4) {
int[] b = new int[] { b1, b2, b3, b4 };
for (int i = 0; i < 16; i++) {
int sum = 0;
for (int j = 0; j < 4; j++) {
if ((i >> j & 1) == 1) {
sum += b[j];
}
}
if (sum == price) {
return "POSSIBLE";
}
}
return "IMPOSSIBLE";
}
}
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
LotteryTicket obj = new LotteryTicket();
System.out.println(
obj.buy(10, 1, 5, 10, 50)
);
}
}
// change to public before submit
class LotteryTicket {
public String buy(int price, int b1, int b2, int b3, int b4) {
int[] b = new int[] { b1, b2, b3, b4 };
for (int i = 0; i < 16; i++) {
int sum = 0;
for (int j = 0; j < 4; j++) {
if ((i >> j & 1) == 1) {
sum += b[j];
}
}
if (sum == price) {
return "POSSIBLE";
}
}
return "IMPOSSIBLE";
}
}
Topcoder SRM 467 DIV 2, L1: ShorterSuperSum
// Topcoder SRM 467 DIV 2, L1: ShorterSuperSum
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
ShorterSuperSum obj = new ShorterSuperSum();
System.out.println(
obj.calculate(14, 14)
);
}
}
// change to public before submit
class ShorterSuperSum {
public int calculate(int k, int n) {
return SuperSum(k, n);
}
private int SuperSum(int k, int n) {
if (k == 0)
return n;
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += SuperSum(k - 1, i);
}
return sum;
}
}
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
ShorterSuperSum obj = new ShorterSuperSum();
System.out.println(
obj.calculate(14, 14)
);
}
}
// change to public before submit
class ShorterSuperSum {
public int calculate(int k, int n) {
return SuperSum(k, n);
}
private int SuperSum(int k, int n) {
if (k == 0)
return n;
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += SuperSum(k - 1, i);
}
return sum;
}
}
Monday, December 3, 2012
CodeEval Ugly Numbers
// CodeEval Ugly Numbers
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
ugly_numbers.main(args);
}
}
class ugly_numbers {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(",");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
static long totUgly;
private static void Process(String[] lineArray) {
String s0 = lineArray[0].trim();
long lastPart = Long.valueOf(s0.substring(0, 1));
totUgly = 0;
Generate('+', lastPart, s0, 1, lastPart);
System.out.println(totUgly);
}
private static boolean IsUgly(long n) {
if (n == 0 || n % 2 == 0 || n % 3 == 0
|| n % 5 == 0 || n % 7 == 0)
return true;
return false;
}
private static void Generate(char lastSign, long lastPart, String s, int xc,
long currentSum) {
if (xc == s.length()) {
if (IsUgly(currentSum))
totUgly++;
return;
}
else {
String firstChar = String.valueOf(s.charAt(xc));
long newLastPart;
long newCurSum;
// concat
newLastPart = (Math.abs(lastPart) * 10) + Long.valueOf(firstChar);
if (lastSign == '+')
newCurSum = currentSum - lastPart + newLastPart;
else
newCurSum = currentSum + lastPart - newLastPart;
Generate(lastSign, newLastPart, s, xc + 1, newCurSum);
// +
newLastPart = Long.valueOf(firstChar);
newCurSum = currentSum + newLastPart;
Generate('+', newLastPart, s, xc + 1, newCurSum);
// -
newLastPart = Long.valueOf(firstChar);
newCurSum = currentSum - newLastPart;
Generate('-', newLastPart, s, xc + 1, newCurSum);
}
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
ugly_numbers.main(args);
}
}
class ugly_numbers {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(",");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
static long totUgly;
private static void Process(String[] lineArray) {
String s0 = lineArray[0].trim();
long lastPart = Long.valueOf(s0.substring(0, 1));
totUgly = 0;
Generate('+', lastPart, s0, 1, lastPart);
System.out.println(totUgly);
}
private static boolean IsUgly(long n) {
if (n == 0 || n % 2 == 0 || n % 3 == 0
|| n % 5 == 0 || n % 7 == 0)
return true;
return false;
}
private static void Generate(char lastSign, long lastPart, String s, int xc,
long currentSum) {
if (xc == s.length()) {
if (IsUgly(currentSum))
totUgly++;
return;
}
else {
String firstChar = String.valueOf(s.charAt(xc));
long newLastPart;
long newCurSum;
// concat
newLastPart = (Math.abs(lastPart) * 10) + Long.valueOf(firstChar);
if (lastSign == '+')
newCurSum = currentSum - lastPart + newLastPart;
else
newCurSum = currentSum + lastPart - newLastPart;
Generate(lastSign, newLastPart, s, xc + 1, newCurSum);
// +
newLastPart = Long.valueOf(firstChar);
newCurSum = currentSum + newLastPart;
Generate('+', newLastPart, s, xc + 1, newCurSum);
// -
newLastPart = Long.valueOf(firstChar);
newCurSum = currentSum - newLastPart;
Generate('-', newLastPart, s, xc + 1, newCurSum);
}
}
}
CodeEval String List
// CodeEval String List
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
string_list.main(args);
}
}
class string_list {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(",");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
Integer n = Integer.valueOf(lineArray[0]);
String s0 = lineArray[1];
char[] cs0 = s0.toCharArray();
Set<Character> cset = new TreeSet<Character>();
for (int i = 0; i < cs0.length; i++) {
cset.add(cs0[i]);
}
String s = "";
for (Character c : cset) {
s += c.toString();
}
Integer slen = s.length();
Set<String> set = new LinkedHashSet<String>();
FillSet("", s, set, n);
String[] ss = set.toArray(new String[set.size()]);
for (int i = 0; i < ss.length; i++) {
if (i > 0)
System.out.print(",");
System.out.print(ss[i]);
}
System.out.println();
}
private static void FillSet(String pre, String s, Set<String> set, int n) {
if (pre.length() == n) {
set.add(pre);
}
else {
for (int i = 0; i < s.length(); i++) {
String s2 = pre + s.substring(i, i + 1);
FillSet(s2, s, set, n);
}
}
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
string_list.main(args);
}
}
class string_list {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(",");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
Integer n = Integer.valueOf(lineArray[0]);
String s0 = lineArray[1];
char[] cs0 = s0.toCharArray();
Set<Character> cset = new TreeSet<Character>();
for (int i = 0; i < cs0.length; i++) {
cset.add(cs0[i]);
}
String s = "";
for (Character c : cset) {
s += c.toString();
}
Integer slen = s.length();
Set<String> set = new LinkedHashSet<String>();
FillSet("", s, set, n);
String[] ss = set.toArray(new String[set.size()]);
for (int i = 0; i < ss.length; i++) {
if (i > 0)
System.out.print(",");
System.out.print(ss[i]);
}
System.out.println();
}
private static void FillSet(String pre, String s, Set<String> set, int n) {
if (pre.length() == n) {
set.add(pre);
}
else {
for (int i = 0; i < s.length(); i++) {
String s2 = pre + s.substring(i, i + 1);
FillSet(s2, s, set, n);
}
}
}
}
CodeEval String Permutations
// CodeEval String Permutations
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
str_perm.main(args);
}
}
class str_perm {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(";");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
String s = lineArray[0];
List<String> ss = GetPermutation(s);
Collections.sort(ss);
System.out.print(ss.get(0));
for (int i = 1; i < ss.size(); i++) {
System.out.print("," + ss.get(i));
}
System.out.println();
}
public static List<String> GetPermutation(String s) {
List<String> result = new ArrayList<String>();
Permutation("", s, result);
return result;
}
private static void Permutation(String prefix, String s, List<String> result) {
int n = s.length();
if (n == 0)
result.add(prefix);
else {
for (int i = 0; i < n; i++)
Permutation(prefix + s.charAt(i),
s.substring(0, i) + s.substring(i + 1), result);
}
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
str_perm.main(args);
}
}
class str_perm {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(";");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
String s = lineArray[0];
List<String> ss = GetPermutation(s);
Collections.sort(ss);
System.out.print(ss.get(0));
for (int i = 1; i < ss.size(); i++) {
System.out.print("," + ss.get(i));
}
System.out.println();
}
public static List<String> GetPermutation(String s) {
List<String> result = new ArrayList<String>();
Permutation("", s, result);
return result;
}
private static void Permutation(String prefix, String s, List<String> result) {
int n = s.length();
if (n == 0)
result.add(prefix);
else {
for (int i = 0; i < n; i++)
Permutation(prefix + s.charAt(i),
s.substring(0, i) + s.substring(i + 1), result);
}
}
}
Sunday, December 2, 2012
Topcoder SRM 471 DIV 2, L1 PrimeContainers
// Topcoder PrimeContainers
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
PrimeContainers obj = new PrimeContainers();
System.out.println(
obj.containerSize(47)
);
}
}
// change to public before submit
public class PrimeContainers {
public int containerSize(int N)
{
boolean[] primes = GetPrimeTable(1000000);
int div = 1;
int cnt = 0;
while (true) {
if (N / div == 0)
break;
if (primes[N / div])
cnt++;
div *= 2;
}
return cnt;
}
public static boolean[] GetPrimeTable(int maxNum) {
boolean[] isPrime = new boolean[maxNum + 1];
for (int i = 0; i < isPrime.length; i++) {
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false;
int sqrtMaxNum = (int) Math.sqrt(maxNum) + 1;
for (int i = 2; i <= sqrtMaxNum; i++) {
if (!isPrime[i])
continue;
int k = i * i;
while (k <= maxNum) {
isPrime[k] = false;
k += i;
}
}
return isPrime;
}
}
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
PrimeContainers obj = new PrimeContainers();
System.out.println(
obj.containerSize(47)
);
}
}
// change to public before submit
public class PrimeContainers {
public int containerSize(int N)
{
boolean[] primes = GetPrimeTable(1000000);
int div = 1;
int cnt = 0;
while (true) {
if (N / div == 0)
break;
if (primes[N / div])
cnt++;
div *= 2;
}
return cnt;
}
public static boolean[] GetPrimeTable(int maxNum) {
boolean[] isPrime = new boolean[maxNum + 1];
for (int i = 0; i < isPrime.length; i++) {
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false;
int sqrtMaxNum = (int) Math.sqrt(maxNum) + 1;
for (int i = 2; i <= sqrtMaxNum; i++) {
if (!isPrime[i])
continue;
int k = i * i;
while (k <= maxNum) {
isPrime[k] = false;
k += i;
}
}
return isPrime;
}
}
Topcoder SRM 562 DIV 2, L1: CucumberMarket
// Topcoder SRM 562 DIV 2, L1: CucumberMarket
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
CucumberMarket obj = new CucumberMarket();
System.out.println(obj.check(new int[] { 1, 2, 3, 4, 5 },
10, 3));
}
}
// change to public before submit
class CucumberMarket {
public String check(int[] price, int budget, int k) {
Arrays.sort(price);
ReversePrimitiveArray(price);
int sum = 0;
for (int i = 0; i < k; i++) {
sum += price[i];
}
if (sum <= budget)
return "YES";
else
return "NO";
}
public static void ReversePrimitiveArray(int[] a) {
for (int l = 0, r = a.length - 1; l < r; l++, r--) {
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
}
}
import java.util.*;
class TopcoderSolution {
public static void main(String[] args) {
CucumberMarket obj = new CucumberMarket();
System.out.println(obj.check(new int[] { 1, 2, 3, 4, 5 },
10, 3));
}
}
// change to public before submit
class CucumberMarket {
public String check(int[] price, int budget, int k) {
Arrays.sort(price);
ReversePrimitiveArray(price);
int sum = 0;
for (int i = 0; i < k; i++) {
sum += price[i];
}
if (sum <= budget)
return "YES";
else
return "NO";
}
public static void ReversePrimitiveArray(int[] a) {
for (int l = 0, r = a.length - 1; l < r; l++, r--) {
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
}
}
CodeEval Prefix expressions
// CodeEval Prefix expressions
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
prefix.main(args);
}
}
class prefix {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split("\\s");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
Stack<String> stk = new Stack<String>();
for (int i = 0; i < lineArray.length; i++) {
String s = lineArray[i];
if (IsOperator(s))
stk.push(s);
else {
if (IsOperator(stk.peek())) {
stk.push(s);
} else {
double operand1 = Double.valueOf(stk.pop());
double operand2 = Double.valueOf(s);
String operator = stk.pop();
double result = 0;
if (operator.equals("+"))
result = operand1 + operand2;
if (operator.equals("*"))
result = operand1 * operand2;
if (operator.equals("/"))
result = operand1 / operand2;
stk.push(String.valueOf(result));
}
}
}
System.out.println(Double.valueOf(stk.pop()).intValue());
}
static boolean IsOperator(String s) {
return ("+*/".contains(s));
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) {
prefix.main(args);
}
}
class prefix {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split("\\s");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
Stack<String> stk = new Stack<String>();
for (int i = 0; i < lineArray.length; i++) {
String s = lineArray[i];
if (IsOperator(s))
stk.push(s);
else {
if (IsOperator(stk.peek())) {
stk.push(s);
} else {
double operand1 = Double.valueOf(stk.pop());
double operand2 = Double.valueOf(s);
String operator = stk.pop();
double result = 0;
if (operator.equals("+"))
result = operand1 + operand2;
if (operator.equals("*"))
result = operand1 * operand2;
if (operator.equals("/"))
result = operand1 / operand2;
stk.push(String.valueOf(result));
}
}
}
System.out.println(Double.valueOf(stk.pop()).intValue());
}
static boolean IsOperator(String s) {
return ("+*/".contains(s));
}
}
CodeEval Longest Common Subsequence
// CodeEval Longest Common Subsequence
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
class Main {
public static void main(String[] args) {
lcs.main(args);
}
}
class lcs {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
if (line.trim().equals(""))
continue;
String[] lineArray = line.split(";");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
String S1 = lineArray[0].trim();
String S2 = lineArray[1].trim();
String lcs = LCSAsString(S1, S2);
System.out.println(lcs.trim());
}
public static String LCSAsString(String X, String Y) {
int M = X.length();
int N = Y.length();
int[][] lcs = new int[M + 1][N + 1];
String[][] lcsString = new String[M + 1][N + 1];
for (int i = 0; i <= M; i++) {
lcs[i][0] = 0;
lcsString[i][0] = "";
}
for (int j = 0; j <= N; j++) {
lcs[0][j] = 0;
lcsString[0][j] = "";
}
for (int i = 1; i <= M; i++)
for (int j = 1; j <= N; j++) {
if (X.charAt(i - 1) == Y.charAt(j - 1)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
lcsString[i][j] = lcsString[i - 1][j - 1]
+ String.valueOf(X.charAt(i - 1));
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
if (lcs[i - 1][j] > lcs[i][j - 1])
lcsString[i][j] = lcsString[i - 1][j];
else
lcsString[i][j] = lcsString[i][j - 1];
}
}
return lcsString[M][N];
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
class Main {
public static void main(String[] args) {
lcs.main(args);
}
}
class lcs {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
if (line.trim().equals(""))
continue;
String[] lineArray = line.split(";");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
private static void Initialize() {
}
private static void Process(String[] lineArray) {
String S1 = lineArray[0].trim();
String S2 = lineArray[1].trim();
String lcs = LCSAsString(S1, S2);
System.out.println(lcs.trim());
}
public static String LCSAsString(String X, String Y) {
int M = X.length();
int N = Y.length();
int[][] lcs = new int[M + 1][N + 1];
String[][] lcsString = new String[M + 1][N + 1];
for (int i = 0; i <= M; i++) {
lcs[i][0] = 0;
lcsString[i][0] = "";
}
for (int j = 0; j <= N; j++) {
lcs[0][j] = 0;
lcsString[0][j] = "";
}
for (int i = 1; i <= M; i++)
for (int j = 1; j <= N; j++) {
if (X.charAt(i - 1) == Y.charAt(j - 1)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
lcsString[i][j] = lcsString[i - 1][j - 1]
+ String.valueOf(X.charAt(i - 1));
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
if (lcs[i - 1][j] > lcs[i][j - 1])
lcsString[i][j] = lcsString[i - 1][j];
else
lcsString[i][j] = lcsString[i][j - 1];
}
}
return lcsString[M][N];
}
}
Saturday, December 1, 2012
CodeEval Cash Register
// CodeEval Cash Register
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
class Main {
public static void main(String[] args) {
cash_register.main(args);
}
}
class cash_register {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(";");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
static Map<Double, String> coins;
static List<Double> coinvals;
private static void Initialize() {
coins = new LinkedHashMap<Double, String>();
coins.put(100.0d, "ONE HUNDRED");
coins.put(50.0d, "FIFTY");
coins.put(20.0d, "TWENTY");
coins.put(10.0d, "TEN");
coins.put(5.0d, "FIVE");
coins.put(2.0d, "TWO");
coins.put(1.0d, "ONE");
coins.put(0.5d, "HALF DOLLAR");
coins.put(0.25d, "QUARTER");
coins.put(0.1d, "DIME");
coins.put(0.05d, "NICKEL");
coins.put(0.01d, "PENNY");
coinvals = new ArrayList<Double>();
Set<Double> v = coins.keySet();
for (Double d : v) {
coinvals.add(d);
}
}
private static void Process(String[] lineArray) {
double PP = Double.valueOf(lineArray[0]);
double CH = Double.valueOf(lineArray[1]);
// System.out.println(PP + ";" + CH + " : " + (PP - CH));
if (CH < PP) {
System.out.println("ERROR");
return;
} else if (CH - PP < 0.001) {
System.out.println("ZERO");
return;
} else {
List<String> chg = new ArrayList<String>();
double money = CH - PP + 0.001;
while (money > 0.005) {
for (Double val : coinvals) {
if (money >= val) {
money -= val;
String c = coins.get(val);
chg.add(c);
break;
}
}
}
String[] achg = chg.toArray(new String[chg.size()]);
Arrays.sort(achg);
for (int i = 0; i < chg.size(); i++) {
if (i > 0)
System.out.print(",");
System.out.print(achg[i]);
}
System.out.println();
}
}
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
class Main {
public static void main(String[] args) {
cash_register.main(args);
}
}
class cash_register {
public static void main(String[] args) {
boolean LOCAL_TEST = false;
// LOCAL_TEST = true;// comment it before submitting
if (LOCAL_TEST)
CodeEvalGetInput("e:\\zin.txt");
else
CodeEvalGetInput(args[0]);
}
public static void CodeEvalGetInput(String arg) {
try {
File file = new File(arg);
BufferedReader in = new BufferedReader(new FileReader(file));
Initialize();
String line;
while ((line = in.readLine()) != null) {
String[] lineArray = line.split(";");
if (lineArray.length > 0) {
// Process line of input Here
Process(lineArray);
}
}
} catch (IOException e) {
System.out.println("File Read Error: " + e.getMessage());
}
}
static Map<Double, String> coins;
static List<Double> coinvals;
private static void Initialize() {
coins = new LinkedHashMap<Double, String>();
coins.put(100.0d, "ONE HUNDRED");
coins.put(50.0d, "FIFTY");
coins.put(20.0d, "TWENTY");
coins.put(10.0d, "TEN");
coins.put(5.0d, "FIVE");
coins.put(2.0d, "TWO");
coins.put(1.0d, "ONE");
coins.put(0.5d, "HALF DOLLAR");
coins.put(0.25d, "QUARTER");
coins.put(0.1d, "DIME");
coins.put(0.05d, "NICKEL");
coins.put(0.01d, "PENNY");
coinvals = new ArrayList<Double>();
Set<Double> v = coins.keySet();
for (Double d : v) {
coinvals.add(d);
}
}
private static void Process(String[] lineArray) {
double PP = Double.valueOf(lineArray[0]);
double CH = Double.valueOf(lineArray[1]);
// System.out.println(PP + ";" + CH + " : " + (PP - CH));
if (CH < PP) {
System.out.println("ERROR");
return;
} else if (CH - PP < 0.001) {
System.out.println("ZERO");
return;
} else {
List<String> chg = new ArrayList<String>();
double money = CH - PP + 0.001;
while (money > 0.005) {
for (Double val : coinvals) {
if (money >= val) {
money -= val;
String c = coins.get(val);
chg.add(c);
break;
}
}
}
String[] achg = chg.toArray(new String[chg.size()]);
Arrays.sort(achg);
for (int i = 0; i < chg.size(); i++) {
if (i > 0)
System.out.print(",");
System.out.print(achg[i]);
}
System.out.println();
}
}
}
Subscribe to:
Posts (Atom)