Wednesday, March 6, 2013

Topcoder SRM 566 DIV 2, L2 : PenguinPals

// Topcoder SRM 566 DIV 2, L2 : PenguinPals

import java.util.*;
import java.math.*;

public class PenguinPals {
    public static void main(String[] args) {
        System.out.println(
                //
                new PenguinPals().findMaximumMatching(
                        "RBRBRBRBRBR"
                        ));
    }

    public int findMaximumMatching(String colors) {
        int npair = 0;
        int np = colors.length();
        while (true) {
            np = colors.length();
            if (np < 2)
                break;
            if (np == 2 && colors.charAt(0) != colors.charAt(1))
                break;
            boolean adjacentfound = false;
            for (int i = 0; i < np; i++) {
                int inext = (i + 1) % np;
                if (colors.charAt(i) == colors.charAt(inext)) {
                    adjacentfound = true;
                    String newcolors;
                    if (i == 0)
                        newcolors = colors.substring(2);
                    else if (i == np - 2)
                        newcolors = colors.substring(0, np - 2);
                    else if (i == np - 1)
                        newcolors = colors.substring(1, np - 1);
                    else
                        newcolors = colors.substring(0, i) +
                                colors.substring(i + 2);
                    colors = newcolors;
                    npair++;
                    break;
                }
            }
            if (!adjacentfound && np > 2) {
                for (int i = 0; i < np; i++) {
                    npair++;
                    String newcolors = colors.substring(3);
                    colors = newcolors;
                    break;
                }
            }
        }
        return npair;
    }
}

No comments:

Post a Comment