EvbCFfp1XB

problem and my answer.

April 2013

problem TopCoder SRM577 DIV1 EllysRoomAssignmentsDiv1

how to solve This problem is easy, right?

source code

import java.util.Arrays;

public class EllysRoomAssignmentsDiv1 {
public double getAverage(String[] ratings) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < ratings.length; i++) {
sb.append(ratings[i]);
}
String[] split = sb.toString().split(" ");
int[] rating = new int[split.length];
for (int i = 0; i < rating.length; i++) {
rating[i] = Integer.parseInt(split[i]);
}
return getAverage(rating);
}

private double getAverage(int[] rating) {
int N = rating.length;
int R = N % 20 == 0 ? N / 20 : N / 20 + 1;
if (R == 1) {
return average(rating, 0, N - 1);
}
int elly = rating[0];
Arrays.sort(rating);
int index = Arrays.binarySearch(rating, elly);
double average = 0;
double M = 0;
for (int i = rating.length - 1; i >= 0; i -= R) {
if (i - (R - 1) <= index && index <= i) {
average += elly;
M++;
} else {
if (i - (R - 1) < 0) {
double a = average / M;
double b = (average + average(rating, 0, i)) / (M + 1);
double p = (double) (i - (0 - 1)) / R;
return a * (1d - p) + b * p;
} else {
average += average(rating, i - (R - 1), i);
M++;
}
}
}
return average / M;
}

private double average(int[] rating, int start, int end) {
double sum = 0;
for (int i = start; i <= end; i++) {
sum += rating[i];
}
return sum / ((end + 1) - start);
}
}

problem TopCoder SRM577 DIV2 EllysCoprimesDiv2

how to solve There is plenty of time to do full search.

source code

import java.util.Arrays;

public class EllysCoprimesDiv2 {
public int getCount(int[] numbers) {
Arrays.sort(numbers);
int count = 0;
for (int i = 1; i < numbers.length; i++) {
int a = numbers[i - 1];
int b = numbers[i];
if (!isCoPrime(a, b)) {
count += minCount(a, b);
}
}
return count;
}

private int minCount(int a, int b) {
for (int n = a + 1; n < b; n++) {
if (isCoPrime(a, n) && isCoPrime(n, b)) {
return 1;
}
}
int min = (int) 1e7;
for (int n = a + 1; n < b; n++) {
if (isCoPrime(a, n)) {
min = Math.min(min, 1 + minCount(n, b));
}
}
return min;
}

private static int gcd(int a, int b) {
for (;;) {
if (b == 0) {
return a;
}
a %= b;
if (a == 0) {
return b;
}
b %= a;
}
}

private static boolean isCoPrime(int a, int b) {
return gcd(a, b) == 1;
}
}

problem TopCoder SRM577 DIV2 EllysRoomAssignmentsDiv2

how to solve In the contest, I missed this problem. I didn't think a case that Elly's rating is the highest.

source code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class EllysRoomAssignmentsDiv2 {
public double getProbability(String[] ratings) {
ArrayList<Integer> rating = new ArrayList<Integer>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < ratings.length; i++) {
sb.append(ratings[i]);
}
String[] s = sb.toString().split(" +");
for (int j = 0; j < s.length; j++) {
rating.add(Integer.parseInt(s[j]));
}
int N = rating.size();
if (N <= 20) {
return 1;
}
int elly = rating.get(0);
Collections.sort(rating);
int R = (N % 20 == 0) ? (N / 20) : ((N / 20) + 1);
int index = N - rating.indexOf(elly);
if (index == 1) {
return 1;
}
if (index <= R) {
return 0;
}
return 1d / R;
}
}

problem TopCoder SRM577 DIV2 EllysNewNickname

how to solve This problem is easy, right?

source code

public class EllysNewNickname {
public int getLength(String nickname) {
int count = 1;
for (int i = 1; i < nickname.length(); i++) {
if (!isVowel(nickname, i) || !isVowel(nickname, i - 1)) {
count++;
}
}
return count;
}

private boolean isVowel(String nickname, int i) {
return "aeiouy".contains("" + nickname.charAt(i));
}
}

このページのトップヘ