## Thursday, November 17, 2011

### SRM524:

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3
This contest is probably the best score I ever had.
Keep trying, and keep being part of what you like to do.

## Tutorials:

### Solution

The same with Div2-Level2

### 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)
}

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

### 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%>
}

### 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%>
}