SRM156
Div 1, Level 1
Div 1, Level 2
Div 1, Level 3
Div 2, Level 1
Div 2, Level 2
Div 2, Level 3
Tutorials:
Division One - Level Three:
Solution
Source Code:
//Fri Jun 10 22:01:28 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class State{
public:
int x1, y1, x2, y2;
int steps;
State(int a, int b, int c, int d, int s){
x1 = a;
y1 = b;
x2 = c;
y2 = d;
steps = s;
}
};
class PathFinding {
public:
int M;
int N;
bool checkBound(int x, int y){
return x>=0 && x< M && y>=0 && y<N;
}
int minTurns(vector <string>);
};
bool visited[20][20][20][20];
int PathFinding::minTurns(vector <string> board) {
M = board.size();
N = board[0].size();
memset(visited, false, sizeof(visited));
int ax, bx, ay, by;
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
if(board[i][j]=='A') {ax = i; ay = j;}
if(board[i][j]=='B') {bx = i; by = j;}
}
}
State start(ax, ay, bx, by, 0);
deque<State> q;
q.push_back(start);
while(!q.empty()){
int p1 = q.front().x1;
int q1 = q.front().y1;
int p2 = q.front().x2;
int q2 = q.front().y2;
int stp = q.front().steps;
q.pop_front();
if(p1==p2 && q1==q2) continue;
if(p1==bx && q1==by && p2==ax && q2==ay) return stp;
if(visited[p1][q1][p2][q2]) continue;
visited[p1][q1][p2][q2] = true;
for(int dx1 = -1; dx1<=1; dx1++){
for(int dy1=-1; dy1<=1; dy1++){
for(int dx2=-1; dx2<=1; dx2++){
for(int dy2=-1; dy2<=1; dy2++){
int xx1 = p1 + dx1;
int yy1 = q1 + dy1;
int xx2 = p2 + dx2;
int yy2 = q2 + dy2;
if(xx1==p2 && yy1==q2 && xx2==p1 && yy2==q1) continue;
if(checkBound(xx1, yy1) && checkBound(xx2, yy2)){
if(board[xx1][yy1]=='X' || board[xx2][yy2]=='X') continue;
State tmp(xx1, yy1, xx2, yy2, stp+1);
q.push_back(tmp);
}
}
}
}
}
}
return -1;
}
//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
Division One - Level Two:
Solution
Source Code:
Division One - Level One:
Solution
Source Code:
//2009/08/01 18:13:47
#include <vector>
#include <string>
using namespace std;
class BombSweeper
{
public:
double winPercentage(vector <string> board)
{
int wins =0;
int loss = 0;
for(int i=0; i<board.size(); i++)
{
for(int j=0; j<board[0].size(); j++)
{
if(board[i][j] == 'B')
{
loss++;
continue;
}
if(check(i,j,board))
wins++;
}
}
return (double)(wins*1.0 /(wins+loss))*100.0; // Take care of the difference between wins and wins*1.0;
}
private:
bool check(int m, int n, vector<string> b)
{
if(m>0)
{
if(n>0 && b[m-1][n-1] != '.')
return false;
else if(b[m-1][n] != '.')
return false;
else if(n+1 <b[0].size() && b[m-1][n+1]!='.')
return false;
}
if(n>0 && b[m][n-1]!='.')
return false;
if(n+1 < b[0].size() && b[m][n+1]!='.')
return false;
if(m+1 < b.size())
{
if(n>0 && b[m+1][n-1]!='.')
return false;
if(b[m+1][n]!='.')
return false;
if(n+1<b[0].size() && b[m+1][n+1]!='.')
return false;
}
return true;
}
};
Division Two - Level Three:
Solution
Source Code:
//2009/08/01 20:36:39
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
class WordParts
{
public:
int partCount(string original, string compound)
{
int n = original.size();
int m = compound.size();
int l;
for(int i=1; i<=n; i++)
s.insert(original.substr(0, i));
for(int i=1; i<=n; i++)
s.insert(original.substr(n-i, i));
vector<int> mem(m+1, 1000);
mem[m] = 0;
for(int i=m-1; i>=0; i--)
{
for(__typeof(s.begin()) j=s.begin(); j!=s.end(); j++)
{
if(i+(l=(*j).size()) <= m && compound.substr(i,l) == *j)
mem[i] = min(mem[i], mem[i+l] + 1);
}
}
return mem[0]==1000 ? -1 : mem[0];
}
private:
set<string> s;
};
Division Two - Level Two:
Solution
Source Code:
//2009/08/01 18:13:47
#include <vector>
#include <string>
using namespace std;
class BombSweeper
{
public:
double winPercentage(vector <string> board)
{
int wins =0;
int loss = 0;
for(int i=0; i<board.size(); i++)
{
for(int j=0; j<board[0].size(); j++)
{
if(board[i][j] == 'B')
{
loss++;
continue;
}
if(check(i,j,board))
wins++;
}
}
return (double)(wins*1.0 /(wins+loss))*100.0; // Take care of the difference between wins and wins*1.0;
}
private:
bool check(int m, int n, vector<string> b)
{
if(m>0)
{
if(n>0 && b[m-1][n-1] != '.')
return false;
else if(b[m-1][n] != '.')
return false;
else if(n+1 <b[0].size() && b[m-1][n+1]!='.')
return false;
}
if(n>0 && b[m][n-1]!='.')
return false;
if(n+1 < b[0].size() && b[m][n+1]!='.')
return false;
if(m+1 < b.size())
{
if(n>0 && b[m+1][n-1]!='.')
return false;
if(b[m+1][n]!='.')
return false;
if(n+1<b[0].size() && b[m+1][n+1]!='.')
return false;
}
return true;
}
};
Division Two - Level One:
Solution
Source Code:
//2009/08/01 17:49:23
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class DiskSpace
{
public:
int minDrives(vector <int> used, vector <int> total)
{
int use = 0;
for(int i=0; i<used.size(); i++)
{
use += used[i];
}
sort(total.begin(), total.end()); //For Greedy, don't forget sort first.
for(int i=total.size()-1; i>=0; i--)
{
if(total[i] - use >= 0)
return (total.size() - i);
use -= total[i];
}
return total.size();
}
};
No comments :
Post a Comment