Category Archives: UVA
12517 – Digit Sum
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class DigitSum {
private static long[][][] dp;
private static long[][][] dp2;
private static int[] b;
private static int[] a;
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
StringBuilder ans = new StringBuilder("");
while (true) {
StringTokenizer str = new StringTokenizer(buf.readLine());
int n = Integer.parseInt(str.nextToken());
int m = Integer.parseInt(str.nextToken());
if (n + m == 0) {
System.out.print(ans);
break;
}
String nn = n + "";
String mm = m + "";
while (nn.length() < mm.length())
nn = "0" + nn;
char[] aa = nn.toCharArray();
char[] bb = mm.toCharArray();
a = new int[aa.length];
b = new int[bb.length];
for (int i = 0; i < a.length; i++) {
a[i] = aa[i] - '0';
b[i] = bb[i] - '0';
}
dp = new long[a.length][2][2];
dp2 = new long[a.length][2][2];
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[0].length; j++) {
Arrays.fill(dp[i][j], -1);
Arrays.fill(dp2[i][j], -1);
}
long sum = go(0, 0, 0);
ans.append(sum + "\n");
}
}
private static long go(int index, int flag1, int flag2) {
if (index == a.length)
return 0;
if (dp[index][flag1][flag2] != -1)
return dp[index][flag1][flag2];
else {
long tot = 0;
for (int i = 0; i < 10; i++) {
int newFlag1 = flag1;
int newFlag2 = flag2;
if (flag1 == 0) {
if (i < a[index])
continue;
if (i > a[index])
newFlag1 = 1;
}
if (flag2 == 0) {
if (i > b[index])
continue;
if (i < b[index])
newFlag2 = 1;
}
tot += go(index + 1, newFlag1, newFlag2) + i
* go2(index + 1, newFlag1, newFlag2);
}
return dp[index][flag1][flag2] = tot;
}
}
private static long go2(int index, int flag1, int flag2) {
if (index == a.length)
return 1;
if (dp2[index][flag1][flag2] != -1)
return dp2[index][flag1][flag2];
else {
long tot = 0;
for (int i = 0; i < 10; i++) {
int newFlag1 = flag1;
int newFlag2 = flag2;
if (flag1 == 0) {
if (i < a[index])
continue;
if (i > a[index])
newFlag1 = 1;
}
if (flag2 == 0) {
if (i > b[index])
continue;
if (i < b[index])
newFlag2 = 1;
}
tot += go2(index + 1, newFlag1, newFlag2);
}
return dp2[index][flag1][flag2] = tot;
}
}
}
12063 – Zeros and Ones
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;
public class ZerosAndOnes {
private static long[][][] dp;
private static int k;
private static int n;
private static int[] pow;
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
int tt = Integer.parseInt(buf.readLine());
StringBuilder ans = new StringBuilder("");
for (int t = 1; t <= tt; t++) {
StringTokenizer str = new StringTokenizer(buf.readLine());
n = Integer.parseInt(str.nextToken());
k = Integer.parseInt(str.nextToken());
if (k == 0){
ans.append("Case " + t + ": 0\n");
continue;
}
pow = new int[64];
pow[0] = 1 % k;
for (int i = 1; i < 64; i++)
pow[i] = (pow[i - 1] * 2) % k;
dp = new long[n][n + 1][k];
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[0].length; j++)
Arrays.fill(dp[i][j], -1);
long tot = go(1, 1, 0, pow[n - 1]);
ans.append("Case " + t + ": " + tot + "\n");
}
System.out.print(ans);
}
private static long go(int index, int c1, int c0, int rem) {
if (index == n && c1 == c0 && rem == 0)
return 1;
else if (index == n)
return 0;
else if (dp[index][c1][rem] != -1)
return dp[index][c1][rem];
else {
long tot = 0;
int nextRem = pow[index - 1];
nextRem += rem;
nextRem %= k;
tot += go(index + 1, c1 + 1, c0, nextRem);
tot += go(index + 1, c1, c0 + 1, rem);
return dp[index][c1][rem] = tot;
}
}
}
11361 – Investigating Div-Sum Property
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class InvestigatingDivSumProperty {
private static int[] A;
private static int[] B;
private static int[][][][][] dp;
private static int k;
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
int t = Integer.parseInt(buf.readLine());
StringBuilder ans = new StringBuilder("");
while (t-- > 0) {
StringTokenizer str = new StringTokenizer(buf.readLine());
long a = Long.parseLong(str.nextToken());
long b = Long.parseLong(str.nextToken());
k = Integer.parseInt(str.nextToken());
String bb = b + "";
String aa = a + "";
B = new int[bb.length()];
for (int i = 0; i < B.length; i++)
B[i] = bb.charAt(i) - '0';
A = new int[B.length];
Arrays.fill(A, 0);
int index = A.length - 1;
for (int i = aa.length() - 1; i >= 0; i--)
A[index--] = aa.charAt(i) - '0';
dp = new int[2][2][A.length][k + 1][100];
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[0].length; j++)
for (int m = 0; m < dp[0][0].length; m++)
for (int l = 0; l < dp[0][0][0].length; l++)
Arrays.fill(dp[i][j][m][l], -1);
int total = go(0, 0, 0, 0, 0);
ans.append(total + "\n");
}
System.out.print(ans);
}
private static int go(int flag1, int flag2, int index, int rem, int sum) {
if (index == A.length) {
if (rem == 0 && sum % k == 0)
return 1;
else
return 0;
} else if (dp[flag1][flag2][index][rem][sum] != -1)
return dp[flag1][flag2][index][rem][sum];
else {
int total = 0;
for (int i = 0; i < 10; i++) {
int newFlag1 = flag1;
int newFlag2 = flag2;
if (flag1 == 0) {
if (i < A[index])
continue;
if (i > A[index])
newFlag1 = 1;
}
if (flag2 == 0) {
if (i > B[index])
continue;
if (i < B[index])
newFlag2 = 1;
}
int digit = (int) (i * Math.pow(10, A.length - index - 1));
digit %= k;
total += go(newFlag1, newFlag2, index + 1, (rem + digit) % k,
sum + i);
}
return dp[flag1][flag2][index][rem][sum] = total;
}
}
}
10819 – Trouble of 13-Dots
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Troubleof13Dots {
private static int total;
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
while (true) {
String line = buf.readLine();
if (line == null)
break;
StringTokenizer str = new StringTokenizer(line);
total = Integer.parseInt(str.nextToken());
int n = Integer.parseInt(str.nextToken());
a = new int[n][2];
for (int i = 0; i < n; i++) {
str = new StringTokenizer(buf.readLine());
int x = Integer.parseInt(str.nextToken());
int y = Integer.parseInt(str.nextToken());
a[i][0] = x;
a[i][1] = y;
}
dp = new int[total + 201][n];
for (int i = 0; i < dp.length; i++)
Arrays.fill(dp[i], -1);
int ans = go(0, 0);
System.out.println(ans);
}
}
static int[][] a;
static int[][] dp;
private static int go(int sum, int i) {
if (i == a.length) {
if (sum > total && sum > 2000 && total + 200 >= sum || sum <= total)
return 0;
else
return -1000000;
} else if (dp[sum][i] != -1)
return dp[sum][i];
else {
int max = go(sum, i + 1);
if (sum + a[i][0] <= total + 200)
max = Math.max(max, go(sum + a[i][0], i + 1) + a[i][1]);
return dp[sum][i] = max;
}
}
}
12532 – Interval Product
package Data_Structures;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class IntervalProduct {
static int[] tree1;
static int[] tree2;
public static void update(int index, int value, int[] tree) {
while (index 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
StringBuilder ans = new StringBuilder("");
while (true) {
String line = buf.readLine();
if (line == null || line.length() == 0)
break;
StringTokenizer str = new StringTokenizer(line);
int n = Integer.parseInt(str.nextToken());
int k = Integer.parseInt(str.nextToken());
tree1 = new int[n + 1];
tree2 = new int[n + 1];
int[] a = new int[n + 1];
str = new StringTokenizer(buf.readLine());
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(str.nextToken());
if (a[i] 0) {
str = new StringTokenizer(buf.readLine());
if (str.nextToken().equals("C")) {
int index = Integer.parseInt(str.nextToken());
int x = Integer.parseInt(str.nextToken());
int sign1 = get(x);
int sign2 = get(a[index]);
a[index] = x;
if (sign1 != sign2) {
if (sign1 == 0 && sign2 == 1) {
update(index, 1, tree2);
}
if (sign1 == 0 && sign2 == 2) {
update(index, 1, tree2);
update(index, -1, tree1);
}
if (sign1 == 1 && sign2 == 0) {
update(index, -1, tree2);
}
if (sign1 == 1 && sign2 == 2) {
update(index, -1, tree1);
}
if (sign1 == 2 && sign2 == 0) {
update(index, 1, tree1);
update(index, -1, tree2);
}
if (sign1 == 2 && sign2 == 1) {
update(index, 1, tree1);
}
}
} else {
int x = Integer.parseInt(str.nextToken());
int y = Integer.parseInt(str.nextToken());
int zeroSum = read(y, tree2) - read(x - 1, tree2);
int negSum = read(y, tree1) - read(x - 1, tree1);
if (zeroSum > 0)
ans.append("0");
else if (negSum % 2 == 0)
ans.append("+");
else
ans.append("-");
}
}
ans.append("\n");
}
System.out.print(ans);
}
private static int get(int x) {
if (x == 0)
return 0;
else if (x > 0)
return 1;
else
return 2;
}
}
11506 – Angry Programmer
package Max_Flow;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class AngryProgrammer {
private static ArrayList<Integer>[] list;
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
StringBuilder ans = new StringBuilder("");
while (true) {
StringTokenizer str = new StringTokenizer(buf.readLine());
int m = Integer.parseInt(str.nextToken());
int w = Integer.parseInt(str.nextToken());
if (m + w == 0)
break;
int[][] matrix = new int[2 * m][2 * m];
for (int i = 0; i < m - 2; i++) {
str = new StringTokenizer(buf.readLine());
int id = Integer.parseInt(str.nextToken()) - 1;
int c = Integer.parseInt(str.nextToken());
matrix[id * 2][id * 2 + 1] = c;
matrix[id * 2 + 1][id * 2] = c;
}
for (int i = 0; i < w; i++) {
str = new StringTokenizer(buf.readLine());
int x = Integer.parseInt(str.nextToken()) - 1;
int y = Integer.parseInt(str.nextToken()) - 1;
int c = Integer.parseInt(str.nextToken());
matrix[2 * x + 1][2 * y] = c;
matrix[2 * y + 1][2 * x] = c;
}
list = new ArrayList[matrix.length];
for (int i = 0 ; i <matrix.length;i++){
list[i] = new ArrayList<Integer>();
for (int j = 0 ; j<matrix.length;j++)
if(matrix[i][j]!=0)
list[i].add(j);
}
ans.append(countPathes(matrix, 1, matrix.length - 2)+"\n");
}
System.out.print(ans);
}
private static int countPathes(int[][] matrix, int s, int t) {
int result = 0;
while (true) {
int x = bfs(matrix, s, t);
if (x == 0)
break;
result += x;
}
return result;
}
private static int bfs(int[][] matrix, int s, int t) {
Queue<Integer> q = new LinkedList<Integer>();
boolean[] v = new boolean[matrix.length];
v[s] = true;
int[] parent = new int[matrix.length];
q.add(s);
int x = 0;
while (!q.isEmpty()) {
x = q.poll();
if (x == t)
break;
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < list[x].size(); i++)
if (!set.contains(list[x].get(i))) {
set.add(list[x].get(i));
if (matrix[x][list[x].get(i)] > 0 && !v[list[x].get(i)]) {
v[list[x].get(i)] = true;
q.add(list[x].get(i));
parent[list[x].get(i)] = x;
}
}
}
if (x != t)
return 0;
int min = Integer.MAX_VALUE;
while (parent[x] != s) {
int prev = parent[x];
min = Math.min(min, matrix[prev][x]);
x = prev;
}
min = Math.min(min, matrix[parent[x]][x]);
x = t;
while (parent[x] != 0) {
int prev = parent[x];
matrix[prev][x] -= min;
matrix[x][prev] += min;
list[x].add(prev);
x = prev;
}
matrix[s][x] -= min;
matrix[x][s] += min;
list[x].add(s);
return min;
}
}
10480 – Sabotage
min cut
package Max_Flow;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Sabotage {
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
StringBuilder ans = new StringBuilder("");
while (true) {
StringTokenizer str = new StringTokenizer(buf.readLine());
int n = Integer.parseInt(str.nextToken());
int m = Integer.parseInt(str.nextToken());
if (n + m == 0)
break;
int[][] matrix = new int[n][n];
int[][] matrix1 = new int[n][n];
for (int i = 0; i < m; i++) {
str = new StringTokenizer(buf.readLine());
int x = Integer.parseInt(str.nextToken()) - 1;
int y = Integer.parseInt(str.nextToken()) - 1;
int z = Integer.parseInt(str.nextToken());
matrix[x][y] = z;
matrix[y][x] = z;
matrix1[x][y]=z;
matrix1[y][x]=z;
}
int maxF = countPathes(matrix, 0, 1);
boolean[] v = new boolean[matrix.length];
Queue<Integer> q = new LinkedList<Integer>();
q.add(0);
v[0] = true;
while (!q.isEmpty()) {
int node = q.poll();
for (int i = 0; i < matrix.length; i++)
if (!v[i] && matrix[node][i] > 0) {
v[i] = true;
q.add(i);
}
}
for (int i = 0; i < v.length; i++)
if (v[i]) {
for (int j = 0; j < v.length; j++)
if (!v[j]) {
if (matrix1[i][j] != 0 && matrix[i][j] == 0)
ans.append((i + 1) + " " + (j + 1) + "\n");
}
}
ans.append("\n");
}
System.out.print(ans);
}
private static int countPathes(int[][] matrix, int s, int t) {
int result = 0;
while (true) {
int x = bfs(matrix, s, t);
if (x == 0)
break;
result += x;
}
return result;
}
private static int bfs(int[][] matrix, int s, int t) {
Queue<Integer> q = new LinkedList<Integer>();
boolean[] v = new boolean[matrix.length];
v[s] = true;
int[] parent = new int[matrix.length];
q.add(s);
int x = 0;
while (!q.isEmpty()) {
x = q.poll();
if (x == t)
break;
for (int i = 1; i < matrix.length; i++)
if (!v[i] && matrix[x][i] > 0) {
q.add(i);
v[i] = true;
parent[i] = x;
}
}
if (x != t)
return 0;
int min = Integer.MAX_VALUE;
while (parent[x] != 0) {
int prev = parent[x];
min = Math.min(min, matrix[prev][x]);
x = prev;
}
min = Math.min(min, matrix[parent[x]][x]);
x = t;
while (parent[x] != 0) {
int prev = parent[x];
matrix[prev][x] -= min;
matrix[x][prev] += min;
x = prev;
}
matrix[0][x] -= min;
matrix[x][0] += min;
return min;
}
}
10092 – The Problem with the Problem Setter
Adjacency List plus Adjacency Matrix
package Max_Flow;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class TheProblemwiththeProblemSetter {
private static int[][] matrix;
private static ArrayList<Integer>[] list;
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
StringBuilder ans = new StringBuilder("");
while (true) {
StringTokenizer str = new StringTokenizer(buf.readLine());
int n = Integer.parseInt(str.nextToken());
int m = Integer.parseInt(str.nextToken());
if (n + m == 0)
break;
matrix = new int[n + m + 2][n + m + 2];
list = new ArrayList[matrix.length];
for (int i = 1; i <= m; i++)
matrix[0][i] = 1;
str = new StringTokenizer(buf.readLine());
for (int i = 1; i <= n; i++) {
matrix[m + i][m + n + 1] = Integer.parseInt(str.nextToken());
}
for (int i = 1; i <= m; i++) {
str = new StringTokenizer(buf.readLine());
int x = Integer.parseInt(str.nextToken());
for (int j = 0; j < x; j++) {
int y = Integer.parseInt(str.nextToken());
matrix[i][m + y] = 1;
}
}
for (int i = 0; i < matrix.length; i++) {
list[i] = new ArrayList<Integer>();
for (int j = 0; j < matrix.length; j++)
if (matrix[i][j] > 0)
list[i].add(j);
}
int maxF = countPathes(matrix, 0, matrix.length - 1);
boolean check = true;
for (int i = 1; i <= n && check; i++) {
if (matrix[m + i][m + n + 1] != 0)
check = false;
}
if (!check)
ans.append("0\n");
else {
ans.append("1\n");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (matrix[m + i][j] == 1)
ans.append(j + " ");
ans.deleteCharAt(ans.length() - 1);
ans.append("\n");
}
}
}
System.out.print(ans);
}
private static int countPathes(int[][] matrix, int s, int t) {
int result = 0;
while (true) {
int x = bfs(matrix, s, t);
if (x == 0)
break;
result += x;
}
return result;
}
private static int bfs(int[][] matrix, int s, int t) {
Queue<Integer> q = new LinkedList<Integer>();
q.add(s);
boolean[] v = new boolean[matrix.length];
v[s] = true;
int[] parent = new int[v.length];
int x = 0;
while (!q.isEmpty()) {
x = q.poll();
if (x == t)
break;
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < list[x].size(); i++)
if (!set.contains(list[x].get(i))) {
set.add(list[x].get(i));
if (matrix[x][list[x].get(i)] > 0 && !v[list[x].get(i)]) {
v[list[x].get(i)] = true;
q.add(list[x].get(i));
parent[list[x].get(i)] = x;
}
}
}
if (x != t)
return 0;
int min = Integer.MAX_VALUE;
while (parent[x] != 0) {
int prev = parent[x];
min = Math.min(min, matrix[prev][x]);
x = prev;
}
x = t;
while (parent[x] != 0) {
int prev = parent[x];
matrix[prev][x] -= min;
matrix[x][prev] += min;
list[x].add(prev);
x = prev;
}
matrix[0][x] -= min;
matrix[x][0] += min;
list[x].add(0);
return min;
}
}
10271 – Chopsticks
Do not make the step unless you have 3*rem sticks
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Chopsticks {
private static final int MAX = Integer.MAX_VALUE;
private static long[] a;
private static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
int t = Integer.parseInt(buf.readLine());
StringBuilder ans = new StringBuilder("");
while (t-- > 0) {
StringTokenizer str = new StringTokenizer(buf.readLine());
int k = Integer.parseInt(str.nextToken());
int n = Integer.parseInt(str.nextToken());
a = new long[n];
str = new StringTokenizer(buf.readLine());
for (int i =0 ; i < n;i++)
a[i] = Integer.parseInt(str.nextToken());
dp = new long[n][k + 9];
for (int i = 0; i < dp.length; i++)
Arrays.fill(dp[i], -1);
long min = go(0, k + 8);
ans.append(min + "\n");
}
System.out.print(ans);
}
private static long go(int n, int k) {
if (k == 0)
return 0;
else if (a.length == n || a.length - 1 == n || k * 3 > a.length - n)
return MAX;
else if (dp[n][k] != -1)
return dp[n][k];
else {
long min = Math.min(go(n + 1, k), go(n + 2, k - 1)
+ (a[n] - a[n + 1]) * (a[n] - a[n + 1]));
return dp[n][k] = min;
}
}
}
1240 – ICPC Team Strategy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class ICPCTeamStrategy {
private static int[][][] dp;
private static int n;
private static int[][] a;
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader buf = new BufferedReader(
new InputStreamReader(System.in));
StringBuilder ans = new StringBuilder("");
int t = Integer.parseInt(buf.readLine().trim());
for (int tt = 1; tt <= t; tt++) {
n = Integer.parseInt(buf.readLine().trim());
a = new int[3][n];
StringTokenizer str;
for (int i = 0; i < 3; i++) {
str = new StringTokenizer(buf.readLine().trim());
for (int j = 0; j < n; j++)
a[i][j] = Integer.parseInt(str.nextToken());
}
dp = new int[4][281][1 << n];
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[0].length; j++)
Arrays.fill(dp[i][j], -1);
int max = go(0, 280, 0);
ans.append(max+"\n");
}
System.out.print(ans);
}
private static int go(int prev, int rem, int msk) {
if (msk == (1 << n) - 1)
return 0;
if (dp[prev][rem][msk] != -1)
return dp[prev][rem][msk];
else {
int max = 0;
for (int i = 0; i < n; i++)
if (((1 << i) & msk) == 0) {
// max = Math.max(max,go(prev, rem, msk | (1 << i)));
if (prev != 1 && rem - a[0][i] >= 0)
max = Math.max(max,
1 + go(1, rem - a[0][i], msk | (1 << i)));
if (prev != 2 && rem - a[1][i] >= 0)
max = Math.max(max,
1 + go(2, rem - a[1][i], msk | (1 << i)));
if (prev != 3 && rem - a[2][i] >= 0)
max = Math.max(max,
1 + go(3, rem - a[2][i], msk | (1 << i)));
}
return dp[prev][rem][msk] = max;
}
}
}
algorithmcafe 