Problem 500
int bottom;
int area[1001];
int point[1001];
vector<string> split(const string& str, const string& delimiter) {
string item(str);
for(unsigned pos = item.find(delimiter); pos != string::npos; pos = item.find(delimiter, pos)) {
item.replace(pos, delimiter.size(), " ");
}
stringstream buf(item);
vector<string> result;
while(buf >> item) {
result.push_back(item);
}
return result;
}
class Inequalities {
public:
int maximumSubset(vector <string> inequalities) {
for(int i=0 ; i<= 1000 ; i++){
area[i] = point[i] = 0;
}
bottom = 0;
for(int i=0 ; i<inequalities.size() ; i++){
vector<string> vs = split( inequalities[i], ",");
int p = atoi(vs[2].c_str());
if( vs[1] == "=" ){
point[p]++;
}
else if( vs[1] == ">=" ){
for(int j=p ; j<=1000 ; j++){
point[j]++;
area[j]++;
}
}
else if( vs[1] == "<=" ){
bottom+=1;
point[p]++;
for(int j=p-1 ; j>=0 ; j--){
point[j]++;
area[j]++;
}
}
else if( vs[1] == ">"){
area[p]++;
for(int j=p+1 ; j<=1000 ; j++){
point[j]++;
area[j]++;
}
}
else{
bottom++;
for(int j=p-1 ; j>=0 ; j--){
point[j]++;
area[j]++;
}
}
}
int maxp=0;
for(int i=0 ; i<=1000 ; i++){
maxp = max( maxp, max( point[i], area[i] ));
}
return max( maxp, bottom );
}
};
Problem 1000
double dpa[51][51];
double dpb[51][51];
int num1[51];
class ParkAmusement {
public:
double getProbability(vector <string> landings, int startLanding, int K) {
double result;
for(int i=0 ; i<51 ; i++){
for(int j=0 ; j<51 ; j++){
dpa[i][j] = dpb[i][j] = 0;
}
}
for(int i=0 ; i<landings.size() ; i++) dpa[0][i] = 1;
dpb[0][startLanding] = 1;
for(int i=0 ; i<landings.size() ; i++){
int a=0;
for(int j=0 ; j<landings.size() ; j++){
if( landings[i][j] == '1') a++;
}
num1[i] = a;
}
for(int i=0 ; i<K ; i++){
for(int j=0 ; j<landings.size() ; j++){
if( num1[j] == 0 ) continue;
for(int k=0 ; k<landings.size() ; k++){
if(landings[j][k] == '1'){
dpa[i+1][k] += dpa[i][j]/num1[j];
dpb[i+1][k] += dpb[i][j]/num1[j];
}
}
}
}
double numerator = 0, denominator = 0;
for(int i=0 ; i<landings.size() ; i++){
if( landings[i][i] == 'E' ){
numerator += dpb[K][i];
denominator += dpa[K][i];
}
}
return numerator/denominator;
}
};