Wednesday, March 27, 2013

Topcoder SRM 573 DIV 2 2 TeamContestEasy

//Topcoder SRM 573 DIV 2 2 TeamContestEasy

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

import javax.crypto.spec.PSource;

public class TeamContestEasy {
    public static void main(String[] args) {
        System.out.println(
                //
                new TeamContestEasy().worstRank(
                        new int[]
                        { 610297, 849870, 523999, 6557, 976530, 731458, 7404, 795100,
                                147040, 110947, 159692, 40785, 4949, 2903, 1688, 37278, 620703,
                                28156, 16823, 1159, 12132, 971379, 5916, 1159, 988589,
                                12215, 133, 1490, 911360, 920059, 544070, 40249, 514852, 852,
                                745070, 1105, 715897, 714696, 589133, 698317, 5683, 631612,
                                16453, 101000, 764881, 101, 2053, 754661 }
                        ));
    }

    public int worstRank(int[] strength) {
        int greater = 0;
        int myScore = strength[0] + strength[1] + strength[2];
        myScore -= Math.min(strength[0], Math.min(strength[1], strength[2]));
        if (strength.length == 3)
            return 1;
        Integer[] other = new Integer[strength.length - 3];
        for (int i = 0; i < other.length; i++) {
            other[i] = strength[i + 3];
        }
        Arrays.sort(other, Collections.reverseOrder());
        for (int i = 0; i < other.length / 3; i++) {
            if (other[i] == -1)
                continue;
            int m1 = other[i];
            other[i] = -1;
            int m2 = -1;
            int m3 = -1;
            for (int j = other.length - 1; j >= 0; j--) {
                if (other[j] == -1)
                    continue;
                if (m1 + other[j] > myScore) {
                    m2 = other[j];
                    other[j] = -1;
                    for (int j2 = other.length - 1; j2 >= 0; j2--) {
                        if (other[j2] == -1)
                            continue;
                        other[j2] = -1;
                        break;
                    }
                    greater++;
                    break;
                }
            }
        }

        int maxRank = 1 + greater;
        return maxRank;
    }
}

No comments:

Post a Comment