Archive for the ‘ad-hoc’ Category

UVA – 846 – Steps   1 comment


I was too lazy to write formula for solving quadratic equation so i solved it using binary search.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Steps {

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			long a = in.nextInt();
			long b = in.nextInt();
			long dist = b - a;
			long sqrt = (long) (Math.sqrt(dist) + 1);
			long lo = 0;
			long hi = sqrt;
			while (hi > lo) {
				long mid = (lo + hi) / 2;
				if (mid * (mid + 1) >= dist)
					hi = mid;
				else
					lo = mid + 1;
			}
			long left = hi * (hi + 1) - dist;
			hi *= 2;
			if (left >= lo && lo != 0)
				hi--;
			System.out.println(hi);
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted July 5, 2012 by epicrado in ad-hoc

UVA – 1225 – Digit Counting   Leave a comment


#include 
#define MAXN 10001
int count[MAXN][10];
int main()
{
    int i,j,k;
    for(i=0;i<10;i++)count[0][i]=0;
    for(i=1;i<MAXN;i++)
    {
        for(j=0;j0)
    {
        scanf("%d",&j);
        printf("%d",count[j][0]);
        for(i=1;i<10;i++)
            printf(" %d",count[j][i]);
        putchar('\n');
    }
    return 0;
}

Posted May 17, 2012 by epicrado in ad-hoc

UVA – 10976 – Fractions Again?!   3 comments


#include <stdio.h>
int main()
{
	int k,i,count;
	while(scanf("%d",&k)==1)
	{
		count = 0;
		for(i = k+1;i<=2*k;i++)
			if((i*k)%(i-k)==0)
				count++;
		printf("%d\n",count);
		for(i = k+1;i<=2*k;i++)
			if((i*k)%(i-k)==0)
					printf("%d/%d = %d/%d + %d/%d\n",1,k,1,(i*k)/(i-k),1,i);

	}
	return 0;
}

Posted April 27, 2012 by epicrado in ad-hoc, Iterative, Mathematics

UVA – 496 – Simply Subsets   Leave a comment


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

public class SimplySubsets {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String s1 = in.readLine();
			if (s1 == null)
				break;
			String s2 = in.readLine();
			TreeSet<Integer> A = new TreeSet<Integer>();
			String[] sp = s1.split(" ");
			for (int i = 0; i < sp.length; i++)
				A.add(Integer.parseInt(sp[i]));
			TreeSet<Integer> B = new TreeSet<Integer>();
			sp = s2.split(" ");
			for (int i = 0; i < sp.length; i++)
				B.add(Integer.parseInt(sp[i]));
			TreeSet<Integer> AB = new TreeSet<Integer>(A);
			AB.retainAll(B);
			boolean sA = A.equals(AB);
			boolean sB = B.equals(AB);
			boolean phi = AB.size() == 0;
			if (sA && sB)
				System.out.println("A equals B");
			else if (sA)
				System.out.println("A is a proper subset of B");
			else if (sB)
				System.out.println("B is a proper subset of A");
			else if (phi)
				System.out.println("A and B are disjoint");
			else
				System.out.println("I'm confused!");
		}
	}
}

Posted April 19, 2012 by epicrado in ad-hoc

UVA – 11342 – Three-square   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ThreeSquare {
	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		int[][] res = new int[50001][];
		for (int i = 0; i * i <= 50000; i++) {
			for (int j = i; i * i + j * j <= 50000; j++) {
				for (int k = j; k * k + j * j + i * i <= 50000; k++) {
					int r = i * i + j * j + k * k;
					if (res[r] == null) {
						int[] a = { i, j, k };
						res[r] = a;
					}
				}
			}
		}
		StringBuilder out = new StringBuilder();
		while (tc-- > 0) {
			int n = Integer.parseInt(in.readLine());
			if (res[n] == null)
				out.append(-1 + "\n");
			else
				out.append(res[n][0] + " " + res[n][1] + " " + res[n][2] + "\n");
		}
		System.out.print(out);
	}
}

Posted April 19, 2012 by epicrado in ad-hoc

UVA – 10527 – Persistent Numbers   Leave a comment


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class PNumbers {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String s = in.readLine();
			if (s.equals("-1"))
				break;
			if (s.length() == 1)
				System.out.println("1" + s);
			else {
				int[] a = new int[10];
				BigInteger n = new BigInteger(s);
				int tot = 0;
				for (int i = 9; i > 1; i--) {
					BigInteger ii = new BigInteger(i + "");
					while (n.mod(ii).equals(BigInteger.ZERO)) {
						n = n.divide(ii);
						a[i]++;
						tot++;
					}
				}
				if (!n.equals(BigInteger.ONE))
					System.out.println("There is no such number.");
				else {
					char[] res = new char[tot];
					tot = 0;
					for (int i = 2; i <= 9; i++)
						while (a[i] > 0) {
							a[i]--;
							res[tot++] = (char) (i + '0');
						}
					System.out.println(new String(res));
				}
			}
		}
	}
}

Posted March 19, 2012 by epicrado in ad-hoc, Mathematics, Prime numbers

UVA – 11436 – Cubes – EXTREME!!!   3 comments


Here’s the Solution
X^3-Y^3 = (X-Y)(X^2 + XY + Y^2) = N
Then we should check all factors of N,assume we have a factor i
let X-Y=i,X^2 + XY + Y^2 = N/i
solving those equations together Will give us X and Y.
However the problem here is the bounds.i.e what is the limit for i
for i to be maximum then X-Y must be maximum.
then Y must be zero
at Y = 0
N=(X-Y)*(X^2+XY+Y^2)=X*(X^2)
then i must be <= cubicRoot(N)
Also since Y cannot be zero
then i must be < cubicRoot(N)

import java.util.Scanner;
public class CubesExtreme {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (true) {
			long l = in.nextLong();
			if (l == 0)
				break;
			long xx = -1;
			long yy = Integer.MAX_VALUE;
			for (long i = 1; i * i * i < l; i++) {
				if (l % i == 0) {
					// x=i+y
					// (i+y)^2 + (i+y)y + y^2
					// i^2 + 3y^2 + 3iy
					long a = 3;
					long b = 3 * i;
					long c = i * i - (l / i);
					if (b * b >= 4 * a * c) {
						long r1 = (long) ((-b - Math.sqrt(b * b - 4 * a * c)) / (2 * a));
						long r2 = (long) ((-b + Math.sqrt(b * b - 4 * a * c)) / (2 * a));
						if (r1 > 0
								&& (i + r1) * (i + r1) * (i + r1) - r1 * r1
										* r1 == l) {
							if (r1 < yy) {
								xx = i + r1;
								yy = r1;
							}
						}
						if (r2 > 0
								&& (i + r2) * (i + r2) * (i + r2) - r2 * r2
										* r2 == l) {
							if (r2 < yy) {
								xx = i + r2;
								yy = r2;
							}
						}
					}
				}
			}
			if (xx > 0)
				System.out.println(xx + " " + yy);
			else
				System.out.println("No solution");
		}

	}
}

Posted February 8, 2012 by epicrado in ad-hoc, Mathematics