## Wednesday, September 21, 2011

### SRM366

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

## Tutorials:

### Solution

The same with Div2 - 500 pts

### Solution

Dynamic Programming, using mark[i][j] represents maximum level can be reached by using first i elements, with the maximum level j.

### Source Code:

//Wed Sep 21 09:02:50 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ChangingSounds
{
public int[] list;
public int mmax;
public Integer[][] mark;
public int maxFinal(int[] changeIntervals, int beginLevel, int maxLevel)
{
mmax = maxLevel;
list = changeIntervals;
mark = new Integer[list.length+2][mmax+1];
return solve(0, beginLevel);
}

public int solve(int index, int level){
if(level > mmax) return -1;
if(level < 0return -1;
if(index == list.length) return level;
if(mark[index][level] != nullreturn mark[index][level];
int ret = -1;
ret = Math.max(ret, solve(index+1, level + list[index]));
ret = Math.max(ret, solve(index+1, level - list[index]));
return mark[index][level] = ret;
}

}

### Source Code:

//2009/08/24 13:28:43
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class SerialNumbers
{
public:
vector <string> sortSerials(vector <string> serialNumbers)
{
vector<string> ret(serialNumbers);
for (int i=0; i<ret.size(); i++)
for (int j=0;j<ret.size();j++)
{
if (i!=j && cmp(ret[i], ret[j]) < 0)
{
cout << ret[i] << " " << ret[j] << endl;
string temp = ret[j];
ret[j] = ret[i];
ret[i] = temp;
cout << ret[i] << " " << ret[j] << endl;
}
}
return ret;
}
private:
int cmp(string a, string b)
{
int s1 = sum_of_digits(a);
int s2 = sum_of_digits(b);
//cout << "Sum: " << s1 << " " << s2 << endl;
if (a.size() != b.size()) return a.size() - b.size();
else if (s1 != s2) return s1 - s2;
else return a.compare(b);
}
int sum_of_digits(string a)
{
int sum = 0;
for (int i=0; i<a.size(); i++)
if (isdigit(a[i]))
sum += a[i] - '0';
return sum;
}
};