Codes for Recursion and Depth-First Search

bteams.cpp

#include <fstream>
using namespace std;

ifstream fin("bteams.in");
ofstream fout("bteams.out");

int skill[12], used[4], team[4], res = 1000000000;

void gen(int depth){
  if(depth == 12){
    int strong = 0, weak = 1000000000;
    for(int i = 0; i < 4; i++){
      strong = max(strong, team[i]);
      weak = min(weak, team[i]);
    }
    res = min(res, strong - weak);
  } else {
    for(int i = 0; i < 4; i++){
      if(used[i] == 3) continue;
      used[i]++;
      team[i] += skill[depth];
      gen(depth + 1);
      used[i]--;
      team[i] -= skill[depth];
    }
  }
}

int main(){
  for(int i = 0; i < 12; i++) fin >> skill[i];
  gen(0);
  fout << res << '\n';
}

bteams.java

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

public class bteams{

  static int res = 1000000000;

  static void gen(int depth, int[] skill, int[] used, int[] team){
    if(depth == 12){
      int strong = 0, weak = 1000000000;
      for(int i = 0; i < 4; i++){
        strong = Math.max(strong, team[i]);
        weak = Math.min(weak, team[i]);
      }
      res = Math.min(res, strong - weak);
    } else {
      for(int i = 0; i < 4; i++){
        if(used[i] == 3) continue;
        used[i]++;
        team[i] += skill[depth];
        gen(depth + 1, skill, used, team);
        used[i]--;
        team[i] -= skill[depth];
      }
    }
  }

  public static void main(String args[]) throws IOException {
    int[] skill = new int[12];
    int[] used = new int[4];
    int[] team = new int[4];
    Scanner sc = new Scanner(new File("bteams.in"));
    for(int i = 0; i < 12; i++) skill[i] = sc.nextInt();
    gen(0, skill, used, team);
    PrintWriter pw = new PrintWriter(new File("bteams.out"));
    pw.println(res);
    pw.close();
  }

}

Codes for Recursion and Depth-First Search.md

Recursion and Depth-First Search

These are the sample codes for each of the problems in the Recursion and Depth-First Search handout. (Available here.)

TODO: Mother's Milk (Java)

digits.cpp

#include <bits/stdc++.h>
using namespace std;

void print_all(string prefix){
  if(prefix.size() == 10) cout << prefix << '\n';
  else {
    print_all(prefix + '0');
    print_all(prefix + '1');
  }
}

int main(){
  print_all("");
}

digits.java

public class digits{

  static void digits(String prefix){
    if(prefix.length() == 10) System.out.println(prefix);
    else {
      digits(prefix + "0");
      digits(prefix + "1");
    }
  }

  public static void main(String args[]){
    digits("");
  }

}

factorial.cpp

#include <bits/stdc++.h>
using namespace std;

int factorial(int n){
  if(n == 0) return 1;
  return n * factorial(n - 1);
}

int main(){
  cout << factorial(5) << '\n';
}

factorial.java

public class factorial{
  
  static int factorial(int n){
    if(n == 0) return 1;
    return n * factorial(n - 1);
  }
  
  public static void main(String args[]){
    System.out.println(factorial(5));
  }

}

fibonacci.cpp

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n){
  if(n == 0) return 1;
  if(n == 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(){
  cout << fibonacci(5) << '\n';
}

fibonacci.java

public class fibonacci{

  static int fibonacci(int n){
    if(n == 0) return 1;
    if(n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
  }

  public static void main(String args[]){
    System.out.println(fibonacci(5));
  }

}

milk3.cpp

#include <fstream>
using namespace std;

struct state{
  int a[3];
  state(int x, int y, int z){
    a[0] = x, a[1] = y, a[2] = z;
  }
};

ifstream fin("milk3.in");
ofstream fout("milk3.out");

int A[3], ok[21], last = -1;
bool vis[21][21][21];

state pour(state s, int i, int j){
  int diff = min(A[j] - s.a[j], s.a[i]);
  s.a[i] -= diff, s.a[j] += diff;
  return s;
}

void dfs(state s){
  if(vis[s.a[0]][s.a[1]][s.a[2]]) return;
  vis[s.a[0]][s.a[1]][s.a[2]] = 1;
  if(s.a[0] == 0) ok[s.a[2]] = 1;
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      dfs(pour(s, i, j));
    }
  }
}

int main(){
  fin >> A[0] >> A[1] >> A[2];
  dfs(state(0, 0, A[2]));
  for(int i = 0; i <= A[2]; i++){
    if(ok[i]){
      if(last >= 0) fout << last << ' ';
      last = i;
    }
  }
  fout << last << '\n';
}

permutations.cpp

#include <bits/stdc++.h>
using namespace std;

void permutations(string prefix, bool used[]){
  if(prefix.size() == 4) cout << prefix << '\n';
  else {
    for(int i = 0; i < 4; i++){
      if(used[i]) continue;
      used[i] = true;
      permutations(prefix + char('1' + i), used);
      used[i] = false;
    }
  }
}

int main(){
  bool used[4] = {};
  permutations("", used);
}

permutations.java

public class permutations{

  static void permutations(String prefix, boolean[] used){
    if(prefix.length() == 4) System.out.println(prefix);
    else {
      for(int i = 0; i < 4; i++){
        if(used[i]) continue;
        used[i] = true;
        permutations(prefix + (char)('1' + i), used);
        used[i] = false;
      }
    }
  }

  public static void main(String args[]){
    permutations("", new boolean[4]);
  }

}