Archive for the ‘Cycle-finding’ Category

UVA – 11549 – Calculator Conundrum   Leave a comment


use Floyd’s cycle finding algorithm for O(1) memory and O(n) time 🙂

#include <stdio.h>
typedef long long int ll;
int pow[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
		1000000000 };
ll f(ll x, int p) {
	x = x * x;
	while (x >= pow[p])
		x /= 10;
	return x;
}
int main() {
	int tc;
	scanf("%d", &tc);
	while (tc-- > 0) {
		int p;
		ll x;
		scanf("%d %lld", &p, &x);
		int max = x;
		ll t = x;
		ll h = x;
		do {
			t = f(t, p);
			if (t > max)
				max = t;
			h = f(h, p);
			if (h > max)
				max = h;
			h = f(h, p);
			if (h > max)
				max = h;
		} while (t != h);
		printf("%lld\n", max);
	}
	return 0;
}

Posted July 5, 2012 by epicrado in Cycle-finding

UVA – 202 – Repeating Decimals   Leave a comment


import java.util.HashMap;
import java.util.*;

public class decimal {
	static class rational {
		int num, denum;

		public boolean greater(rational r) {
			return num * r.denum - r.num * denum > 0;
		}

		public boolean equals(Object o) {
			rational r = (rational) o;
			return r.num == num && r.denum == denum;
		}

		public int hashCode() {
			return num * 31 + denum * 17;
		}

		public rational(int n, int m) {
			num = n;
			denum = m;
		}

		public String toString() {
			return num + "/" + denum;
		}

		public rational next() {
			rational r = new rational(0, 10);
			while (!r.greater(this))
				r.num++;
			r.num--;
			return r;
		}

		public int gcd(int n, int m) {
			int t;
			while (m != 0) {
				t = m;
				m = n % m;
				n = t;
			}
			return n;
		}

		public void simplify() {
			int g = gcd(num, denum);
			num /= g;
			denum /= g;
		}

		public rational subtract(rational r) {
			rational rr = new rational(num * r.denum - denum * r.num, denum
					* r.denum);
			rr.simplify();
			return rr;
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		rational r1 = new rational(10, 25);
		while (in.hasNext()) {
			int m = in.nextInt();
			int n = in.nextInt();
			int x = m;
			int y = n;
			int q = m / n;
			m = m % n;
			rational r = new rational(m, n);
			r.simplify();
			HashMap<rational, Integer> cycle = new HashMap<rational, Integer>();
			String res = "";
			String s = "";
			int cur = 0;
			while (!cycle.containsKey(r)) {
				cycle.put(r, cur++);
				rational z = r.next();
				rational k = r.subtract(z);
				s = z.num + "";
				r = k;
				r.num *= 10;
				r.simplify();
				res = res + s;
			}
			s = res.substring(0, cycle.get(r));
			String rep = res.substring(cycle.get(r), res.length());
			String out = q + "." + s + "(";
			int i;
			for (i = 0; i < rep.length() && i < 50; i++) {
				out = out + rep.charAt(i);
			}
			if (i == 50)
				out = out + "...";
			out = out + ")";
			System.out.printf("%d/%d = %s\n", x, y, out);
			System.out.println("   " + rep.length()
					+ " = number of digits in repeating cycle");
			System.out.println();
		}
	}
}

Posted September 24, 2011 by epicrado in Cycle-finding