SRM352

	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

It's the same with Div2-500pts.

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Two solutions are provided here, the first one (in Java) is implemented with dynamic programming, while the second one (in C++) calls the function recursively, which count the printed number for '0's and '1's.

Source Code:

//Tue Sep 20 15:54:05 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class NumberofFiboCalls
{
    public int cost[][];
    public int[] fiboCallsMade(int n)
    {
        cost = new int[2][n+1];
        for(int i=0; i<=n; i++){
            cost[0][i] = -1;
            cost[1][i] = -1;
        }
        solve(n);
        int[] ret = new int[2];
        ret[0] = cost[0][n];
        ret[1] = cost[1][n];

        return ret;
    }

    public void solve(int x){
        if(x == 0){
            cost[0][0] = 1;
            cost[1][0] = 0;
        }
        if(x == 1){
            cost[0][1] = 0;
            cost[1][1] = 1;
        }
        if(cost[0][x] != -1 && cost[1][x] != -1)
            return;
        solve(x-1);
        solve(x-2);
        cost[0][x] = cost[0][x-1] + cost[0][x-2];
        cost[1][x] = cost[1][x-1] + cost[1][x-2];
        return;
    }


}
//Powered by [KawigiEdit] 2.0!

//Monday, October 26 2009
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class NumberofFiboCalls
{
public:
    vector <int> fiboCallsMade(int n)
    {
        count1 = 0;
        count2 = 0;
        fabonacci(n);
        vector<int> v;
        v.push_back(count1);
        v.push_back(count2);
        return v;
    }
    int fabonacci(int n)
    {
        if(n == 0)
        {
            count1++;
            return 0;
        }
        if(n == 1)
        {
            count2++;
            return 1;
        }
        return fabonacci(n-1) + fabonacci(n-2);
    }
    int count1;
    int count2;
};

---

Division Two - Level One:

Solution

Source Code:

//2009/08/22 22:34:24
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class AttendanceShort
{
public:
    vector <string> shortList(vector <string> names, vector <string> attendance)
    {
        vector<string> v;
        for (int i=0; i<names.size(); i++)
        {
            //v.push_back(names[i]);
            int cnt = 0;
            int pst = 0;
            for (int j=0; j<attendance[i].size(); j++)
            {
                if (attendance[i][j] == 'M') continue;
                if (attendance[i][j] == 'P')
                {
                    cnt ++;
                    pst ++;
                }
                else
                    cnt ++;
            }
            double temp = 100.0 * pst / cnt;
            if (temp < 75.0)
                v.push_back(names[i]);
        }
        return v;
    }
};