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:


Division One - Level Three:

Solution

Source Code:


Division One - Level Two:

Solution

Source Code:


Division One - Level One:

Solution

The same with Div2 - 500 pts

Source Code:


Sivision Two - Level Three:

Solution

Source Code:


Division Two - Level Two:

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;
    }
 
 
}
//Powered by [KawigiEdit] 2.0!


Division Two - Level One:

Solution

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;
    }
};

No comments :