## Tuesday, September 20, 2011

### SRM363

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

### Solution

Dynamic Programming. The cost[i] is the cost for i business men. The idea is like cutting the cake, any connection between two persons will divide the table into two parts, since any good handshake cannot cross. So, we can take businessman 0, iterate over all other businessmen and each time count recursively how many shakes are there for the rest.

The fomula is: f(n) = (sum for all 0 < i <= nf(i – 1) * f(n – i – 1)

### Source Code:

//Tue Sep 20 19:22:38 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class HandsShaking
{
public long cost[];

public long countPerfect(int n)
{
cost = new long[n+1];
for(int i=0; i<=n; i++){
cost[i] = new Long(-1);
}
solve(n);
return cost[n];
}

public void solve(int n){
if(n==0) cost[n] = 1;
if(n==2) cost[n] = 1;
if(cost[n] != -1return;
long ret = 0;
for(int i=1; i<n; i+=2){
solve(i-1);
solve(n-i-1);
ret += cost[i-1] * cost[n-i-1];
}
cost[n] = ret;
return;
}

}

### Solution

Straight - forward.

### Source Code:

//Tue Sep 20 20:53:28 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class MirroredClock
{
public String whatTimeIsIt(String time)
{
String[] t = time.split(":");
int m = (60 - Integer.parseInt(t)) % 60;
int h = (12 - Integer.parseInt(t) - (m>0?1:0)) % 12;
String ret = String.format("%02d:%02d", h, m);
return ret;
}
}

/***************************************************************************/
//2009/08/24 00:35:48
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class MirroredClock
{
public:
string whatTimeIsIt(string time)
{
int a, b;
char c;
sscanf(time.c_str(), "%d%c%d", &a,&c,&b);
int e = (60 - b) % 60;

int d = (12 - a - (e+b)/60 ) % 12;
char s;
sprintf(s, "%.2d%c%.2d", d,c,e);
return s;
}
};