Codeforces #98(div2)

ProblemA.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class ProblemA {


	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String line = s.readLine();
		int n = line.length();
		int ans = 0;
		
		char prev = ' ';
		int cnt = 0;
		for (int i = 0 ; i < n ; i++) {
			if (line.charAt(i) != prev) {
				if (cnt >= 1) {
					ans += (cnt - 1) / 5 + 1;
				}
				prev = line.charAt(i);
				cnt = 1;
			} else {
				cnt++;
				prev = line.charAt(i);
			}
		}
		if (cnt >= 1) {
			ans += (cnt - 1) / 5 + 1;
		}
		
		System.out.println(ans);
	}
}

ProblemB.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class ProblemB {


	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(s.readLine());
		int[] an = new int[n];
		String[] data = s.readLine().split(" ");
		
		boolean[] used = new boolean[100001];
		for (int i = 0 ; i < n ; i++) {
			an[i] = Integer.valueOf(data[i]);
		}
		
		
		int ans = 0;
		
		for (int i = 0 ; i < n ; i++) {
			if (an[i] >= 1 && an[i] <= n) {
				if (!used[an[i]]) {
					used[an[i]] = true;
				} else {
					ans++;
				}
			} else {
				ans++;
			}
		}
		
		System.out.println(ans);
	}
}

ProblemC.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ProblemC {

	public static class Event {
		int from;
		int to;
		int id;
		Event(int f, int t) {
			from = f;
			to = t;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(s.readLine());
		List<Event> events = new ArrayList<Event>();
		boolean[] included = new boolean[n];
		for (int i = 0 ; i < n ; i++) {
			String[] data = s.readLine().split(" ");
			events.add(new Event(Integer.valueOf(data[0]), Integer.valueOf(data[1])));
		}
		Collections.sort(events, new Comparator<Event>() {
			public int compare(Event a, Event b) {
				if (a.from - b.from == 0) {
					return a.to - b.to;
				}
				return a.from - b.from;
			}
		});
		if (n == 1) {
			System.out.println(0);
			return;
		}
		for (int i = 0 ; i < events.size() ; i++) {
			events.get(i).id = i;
		}
		
		int ans = 0;
		for (int j = 0 ; j < events.size() ; j++) {
			Event se = events.get(j);
			if (included[se.id]) {
				continue;
			}
			int bf = se.from;
			int bt = se.to;
			for (int i = se.id+1 ; i < events.size() ; i++) {
				if (included[i]) {
					continue;
				}
				Event e = events.get(i);
				if (e.from > bt) {
					break;
				}
				if (bf < e.from && e.to < bt) {
					included[i] = true;
					ans++;
				}
			}
		}
		
		
		
		System.out.println(ans);
	}
}

ProblemD.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ProblemD {
	public static String _line;
	public static int len;
	
	public static int INVALID = 99999999;

	public static int[][] memo = new int[501][501];
	public static int[][] mxarg = new int[501][501];
	public static int[][] precomp_needs = new int[501][501];
	public static String[][] precomp_pd = new String[501][501];
	
	public static int dfs(int k, int from) {
		if (k <= -1) {
			return INVALID;
		}
		if (memo[k][from] != -1){
			return memo[k][from];
		}
		
		int min = precomp_needs[from][len];
		mxarg[k][from] = len;
		for (int t = from + 1 ; t < len ; t++) {
			int val = precomp_needs[from][t] + dfs(k-1, t);
			if (val < min) {
				min = val;
				mxarg[k][from] = t;
			}
		}
		
		memo[k][from] = min;
				
		return min;
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String line = s.readLine();
		int num = Integer.valueOf(s.readLine());
		_line = line;
		
		len = line.length();
		
		for (int i = 0 ; i <= 500 ; i++) {
			for (int j = 0 ; j <= 500 ; j++) {
				memo[i][j] = -1;
				precomp_needs[i][j] = -1;
			}			
		}
		
		
		for (int from = 0 ; from < len ; from++) {
			for (int to = from ; to <= Math.min(len, from+1) ; to++) {
				precomp_needs[from][to] = 0;
				precomp_pd[from][to] = line.substring(from, to);
				int left = from;
				int right = to-1;
				while(true) {
					int nl = left - 1;
					int nr = right + 1;
					if (nl < 0 || nr >= len) {
						break;
					}

					char nc = line.charAt(nl);
					precomp_needs[nl][nr+1] = precomp_needs[left][right+1];
					if (line.charAt(nl) != line.charAt(nr)) {
						precomp_needs[nl][nr+1] += 1; 
					}
					precomp_pd[nl][nr+1] = nc + precomp_pd[left][right+1] + nc;
					left = nl;
					right = nr;
				}
			}
		}
		

		int x = dfs(num-1, 0);
		System.out.println(x);
		
		int f = 0;
		String ans = "";
		int k = num-1;
		while (f < len && k >= 0) {
			int t = mxarg[k][f];  
			ans = ans + "+" + precomp_pd[f][t];
			f = t;
			k--;
		}
		
		System.out.println(ans.substring(1));

	}
}