Level 1 | Level 2 | Level 3 | |
---|---|---|---|
Div 1 | Level 2 | Level 3 | |
Keep trying, and keep being part of what you like to do.
Tutorials:
Division One - Level Three:
Solution
Source Code:
Division One - Level Two:
Solution
Source Code:
Division One - Level One:
Solution
The same with Div2-Level2Source Code:
Sivision Two - Level Three:
Solution
1st, filter out all the available digits left.2nd, using BFS to compose every possible number, then check if it's the multiple of the given N.
PS: Redefine the comparator for String is another key for this solution. The default comparator compares the two strings character by character, which take the alphabetical order as higher priority, while the length of the string is set as second.
Source Code:
/*** 1st, filter out all the available digits.
*
* 2nd, using BFS to compose every possible digits,
* check the number when it's the multiple of the given N;
*/
/**
* @author antonio081014
* @since Nov 17, 2011, 8:16:26 AM
*/
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class MultiplesWithLimit {
public List<String> nonForbidden;
public boolean[] visited;
public String minMultiples(int N, int[] forbiddenDigits) {
nonForbidden = new ArrayList<String>();
for (int i = 0; i <= 9; i++) {
boolean flag = true;
for (int j = 0; j < forbiddenDigits.length && flag; j++) {
if (i == forbiddenDigits[j])
flag = false;
}
if (flag)
nonForbidden.add(Integer.toString(i));
}
visited = new boolean[10002];
Queue<String> queue = new PriorityQueue<String>(10,
new Comparator<String>() {
// overriding the compare method
public int compare(String i, String j) {
if (i.compareTo(j) == 0)
return 0;
if (i.length() < j.length())
return -1;
if (i.length() == j.length() && i.compareTo(j) < 0)
return -1;
return 1;
}
});
queue.add("");
while (queue.isEmpty() == false) {
String top = queue.poll();
String tmp;
for (int i = 0; i < nonForbidden.size(); i++) {
tmp = top + nonForbidden.get(i);
if (tmp.startsWith("0"))
continue;
int number = compose(tmp, N);
if (visited[number])
continue;
if (number == 0) {
return getReturn(tmp);
}
queue.add(tmp);
visited[number] = true;
}
}
return "IMPOSSIBLE";
}
public String getReturn(String s) {
if (s.length() < 9)
return s;
else
return s.substring(0, 3) + "..." + s.substring(s.length() - 3)
+ "(" + s.length() + " digits)";
}
public int compose(String s, int N) {
int sum = 0;
for (int i = 0; i < s.length(); i++) {
sum = sum * 10 + s.charAt(i) - '0';
sum %= N;
}
return sum;
}
// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
Division Two - Level Two:
Solution
Take the closest non-prime number, which is smaller than n. Greedy Algorithm.Source Code:
/***
*/
/**
* @author antonio081014
* @since Nov 17, 2011, 8:08:21 AM
*/
public class MagicDiamonds {
public long minimalTransfer(long n) {
long count = 0;
while (n > 0) {
count++;
n -= closestNonePrime(n);
}
return count;
}
public long closestNonePrime(long n) {
for (long x = n; x >= 1; x--) {
if (isPrime(x) == false)
return x;
}
return -1;
}
public boolean isPrime(long n) {
if (n == 2)
return true;
if (n <= 1)
return false;
if (n % 2 == 0)
return false;
for (long i = 3; i * i <= n; i += 2) {
if (n % i == 0)
return false;
}
return true;
}
// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
Division Two - Level One:
Solution
Iterate every possible combination of a, b, c. Then check if is smaller than what I have already.Source Code:
/***
*/
/**
* @author antonio081014
* @since Nov 17, 2011, 8:03:13 AM
*/
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;
public class ShippingCubes {
public int minimalCost(int N) {
int mmin = Integer.MAX_VALUE;
for (int a = 1; a <= N; a++) {
for (int b = 1; b <= N; b++) {
for (int c = 1; c <= N; c++) {
if (a * b * c == N) {
mmin = Math.min(mmin, a + b + c);
}
}
}
}
return mmin;
}
// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!