Friday, June 17, 2011
Sunday, June 12, 2011
SRM181
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
Using priority queue in the library, but I have to redefine the < operator, since the priority queue in the library is implemented with max-heap. I use 1 << 15 to identify if the weapon is taken, or which means that boss has been killed.
Source Code:
//Sun Jun 12 16:13:59 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 weapons;
int shots;
bool operator < (const State &A) const {
return this->shots > A.shots;
}
};
class KiloManX {
public:
int leastShots(vector <string>, vector <int>);
bool visited[1<<15];
int N;
};
int KiloManX::leastShots(vector <string> damageChart, vector <int> bossHealth) {
memset(visited, false, sizeof(visited));
N = damageChart.size();
priority_queue<State> q;
State state = {0, 0};
q.push(state);
while(!q.empty()){
State s = q.top();
q.pop();
if(visited[s.weapons]) continue;
visited[s.weapons] = true;
if(s.weapons == (1<<damageChart.size())-1) return s.shots;
for(int i=0; i<damageChart.size(); i++){
if((s.weapons>>i) & 1) continue;
int best = bossHealth[i];
for(int j=0; j<damageChart.size(); j++){
if(i==j) continue;
if(((s.weapons>>j) & 1) && damageChart[j][i]!='0'){
int shotNeeded = (bossHealth[i] + damageChart[j][i] - '1') / (damageChart[j][i] - '0');
best = min(best, shotNeeded);
}
}
State tmp = {s.weapons | (1<<i), s.shots + best};
q.push(tmp);
}
}
return -1;
}
//Powered by [KawigiEdit] 2.0!
Division One - Level Two:
Solution
Source Code:
Division One - Level One:
Solution
Same with Div2, Lvl 2.
Source Code:
Division Two - Level Three:
Solution
Source Code:
Division Two - Level Two:
Solution
Source Code:
//2009/09/08 23:21:02
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
class CombinationLock
{
public:
double degreesTurned(vector <int> combo, int size, int start)
{
int N = combo.size(), L = N;
double ret = 0;
int at = start;
int dir = 1; //we're calling 1 counterclockwise and 1 clockwise
for (int i = 0; i < L; i++, N--)
{
int K;
if (dir == 1) K = combo[i] - at;
else K = at - combo[i];
if (K < 0) K += size;
ret += 360.0 * (N + 1.0*K/size);
at = combo[i];
dir = -dir;
}
return ret;
}
};
Division Two - Level One:
Solution
Source Code:
//2009/08/10 12:54:07
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
class KiloMan
{
public:
int hitsTaken(vector <int> pattern, string jumps)
{
int score = 0;
for(int i=0; i<pattern.size(); i++)
{
if(jumps[i] == 'J' && pattern[i] > 2)
score++;
if(jumps[i] == 'S' && pattern[i] <= 2)
score ++;
}
return score;
}
};
Friday, June 10, 2011
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();
}
};
TCCC2003 Semifinals #4
Div 1, Level 1
Div 1, Level 2
Div 1, Level 3
Tutorials:
Division One - Level Three:
Solution
Source Code:
Division One - Level Two:
Solution
Source Code:
Division One - Level One:
Solution
Actually, this is a pretty easy problem, just like The Problem on POJ1088, however, I misunderstood the meaning of the longest path, I thought I needed to count the # of hops needed. Actually, the longest path is the biggest cost. Just DFS it.
Source Code:
#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 Circuits {
public:
int grid[51][51];
int cost[51];
int N;
int howLong(vector <string>, vector <string>);
void dfs(int x){
if(cost[x] >=0) return ;
cost[x] = 0;
for(int i=0; i<N; i++){
if(grid[x][i] >= 0){
dfs(i);
cost[x] = max(cost[x], cost[i] + grid[x][i]);
}
}
}
};
int Circuits::howLong(vector <string> con, vector <string> costs) {
N = con.size();
memset(grid, -1, sizeof(grid));
memset(cost, -1, sizeof(cost));
for(int i=0; i<N; i++){
stringstream s1(con[i]), s2(costs[i]);
int id, c;
while(s1 >> id && s2 >> c){
grid[i][id] = c;
}
}
int ret = 0;
for(int i=0; i<N; i++){
if(cost[i] < 0){
dfs(i);
ret = max(ret, cost[i]);
}
cout << cost[i] << ", ";
}
cout << endl;
return ret;
}
//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
Thursday, June 9, 2011
TCO2003 Round 02
Div 1, Level 1
Div 1, Level 2
Div 1, Level 3
#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 Marketing {
public:
long long howMany(vector <string>);
bool dfs(int x, int);
bool grid[31][31];
int type[31];
int N;
};
bool Marketing::dfs(int x, int b){
if(type[x] >= 0) return type[x] == b;
type[x] = b;
for(int i=0; i<N; i++){
if(grid[x][i] && dfs(i, 1-b)==false)
return false;
}
return true;
}
long long Marketing::howMany(vector <string> compete) {
memset(grid, false, sizeof(grid));
memset(type, -1, sizeof(type));
N = compete.size();
for(int i=0; i<N; i++){
stringstream s(compete[i]);
int num;
while(s >> num){
grid[i][num] = true;
grid[num][i] = true;
}
}
long long ret = 1LL;
for(int i=0; i<N; i++){
if(type[i] < 0){
// type[i] = 0;
ret <<= 1;
if(dfs(i, 0)==false) return -1;
}
}
return ret;
}
//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
Div 1, Level 3
Tutorials:
Division One - Level Three:
Solution
Source Code:
Division One - Level Two:
Solution
Using dfs to find all possible elements for one set of two classes.
Source Code:
//Fri Jun 10 01:27:14 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 Marketing {
public:
long long howMany(vector <string>);
bool dfs(int x, int);
bool grid[31][31];
int type[31];
int N;
};
bool Marketing::dfs(int x, int b){
if(type[x] >= 0) return type[x] == b;
type[x] = b;
for(int i=0; i<N; i++){
if(grid[x][i] && dfs(i, 1-b)==false)
return false;
}
return true;
}
long long Marketing::howMany(vector <string> compete) {
memset(grid, false, sizeof(grid));
memset(type, -1, sizeof(type));
N = compete.size();
for(int i=0; i<N; i++){
stringstream s(compete[i]);
int num;
while(s >> num){
grid[i][num] = true;
grid[num][i] = true;
}
}
long long ret = 1LL;
for(int i=0; i<N; i++){
if(type[i] < 0){
// type[i] = 0;
ret <<= 1;
if(dfs(i, 0)==false) return -1;
}
}
return ret;
}
//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
Division One - Level One:
Solution
Source Code:
Bases Conversion:
Convert a number in base b (2 <= b <= 10) to a decimal number:
int toDecimal(int n, int b)
{
int result=0;
int multiplier=1;
while(n>0)
{
result+=n%10*multiplier;
multiplier*=b;
n/=10;
}
return result;
}
Convert a decimal to a number in base b (2 <= b <= 10):int fromDecimal(int n, int b)
{
int result=0;
int multiplier=1;
while(n>0)
{
result+=n%b*multiplier;
multiplier*=10;
n/=b;
}
return result;
}
GCD & LCM
GCD: Greatest Common Divisor:
int GCD(int a, int b)
{
if (b==0) return a;
return GCD(b,a%b);
}
int LCM(int a, int b)
{
return b*a/GCD(a,b);
}
Euclid's algorithm can be used to solve linear Diophantine equations. These equations have integer coefficients and are of the form:ax + by = c
Wednesday, June 8, 2011
SRM509
Summary:
Result
For this contest, I failed completely. First, I thought my 500 problem was challenged because of TLE, but it seems my code has more errors than I thought. Second, my programming background is still not good enough. I should type faster, more accuracy, and fewer lines.
Div 1, Level 1
Div 1, Level 2
Div 1, Level 3
Div 2, Level 1
Div 2, Level 2
Div 2, Level 3
Result
For this contest, I failed completely. First, I thought my 500 problem was challenged because of TLE, but it seems my code has more errors than I thought. Second, my programming background is still not good enough. I should type faster, more accuracy, and fewer lines.Tutorials:
Division One - Level Three:
Solution
Source Code:
Division One - Level Two:
Solution
This is probably the hardest Dynamic programming problem I have done by now.
1st, need to add extra "Empty" element to deal with "add" and "erase" operation. (changeCost[i][j])
2nd, use Floyd-Warshall algorithms to optimize the cost for each operation of changing from one state to another. (matchCost[i][j])
3rd, using dynamic programming implemented with recursive to find the minimum cost from 0 to the last element. (dp[0][length of the array - 1]).
PS: take care of the basic cases when you deal with recursive. Here, the length could be odd or even, and also when length is even, you should think more about it. The grey marked part is pretty important for this solution.
Source Code:
//Wed Jun 15 17:02:55 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;
const int INF = 500000001;
const int EMPTY = 26;
class PalindromizationDiv1 {
public:
int changeCost[27][27];
int matchCost[27][27];
int dp[55][55];
string word;
int rec(int, int);
int getMinimumCost(string, vector <string>);
};
int PalindromizationDiv1::rec(int a, int b){
int &ret = dp[a][b];
if(ret != -1) return ret;
if(a == b){
ret = 0;
return ret;
}
int ca = word[a] - 'a';
int cb = word[b] - 'a';
if(a == b-1) return ret = min(matchCost[ca][cb], min(rec(a+1,b) + matchCost[ca][EMPTY], rec(a,b-1) + matchCost[cb][EMPTY]));
ret = INF;
int x, y;
x = matchCost[ca][cb];
y = rec(a+1, b-1);
if(x < ret - y) ret = min(INF, x + y);
x = min(matchCost[ca][EMPTY], matchCost[EMPTY][ca]);
y = rec(a+1, b);
if(x < ret - y) ret = min(INF, x + y);
x = min(matchCost[cb][EMPTY], matchCost[EMPTY][cb]);
y = rec(a, b-1);
if(x < ret - y) ret = min(INF, x + y);
return ret;
}
int PalindromizationDiv1::getMinimumCost(string w, vector <string> op) {
memset(dp, -1, sizeof(dp));
this->word = w;
for(int i=0; i<27; i++){
for(int j=0; j<27; j++){
changeCost[i][j] = INF;
matchCost[i][j] = INF;
}
}
for(int i=0; i<27; i++){
changeCost[i][i] = 0;
}
for(int i=0; i<op.size(); i++){
stringstream s(op[i]);
string str;
char ca, cb;
s >> str >> ca;
// cout << str << "," << ca << endl;
if(str == "add") s >> changeCost[EMPTY][ca-'a'];
else if(str == "erase") s >> changeCost[ca-'a'][EMPTY];
else {
s >> cb;
s >> changeCost[ca-'a'][cb-'a'];
}
}
for(int k=0; k<27; k++){
for(int i=0; i<27; i++){
for(int j=0; j<27; j++){
int x = changeCost[i][k];
int y = changeCost[k][j];
int &z = changeCost[i][j];
if(x < z - y) z = min(INF, x+y);
}
}
}
// for(int i=0; i<27; i++){
// for(int j=0; j<27; j++){
// cout << changeCost[i][j] << ", ";
// }
// cout << endl;
// }
for(int i=0; i<27; i++){
for(int j=0; j<27; j++){
for(int k=0; k<27; k++){
int x = changeCost[i][k];
int y = changeCost[j][k];
int &z = matchCost[i][j];
if(x < z - y) z = min(INF, x+y);
}
}
}
// for(int i=0; i<27; i++){
// for(int j=0; j<27; j++){
// cout << changeCost[i][j] << ", ";
// }
// cout << endl;
// }
int N = word.size();
int x = rec(0, N-1);
// for(int i=0; i<N; i++) {
// for(int j=0; j<N; j++) cout << dp[i][j] << ", ";
// cout << endl;
// }
return ((x>=INF)? -1 : (int)x);
}
//Powered by [KawigiEdit] 2.0!
Division One - Level One:
Solution
Same as Div2, Lvl 2 problem.
Source Code:
Division Two - Level Three:
Solution
This is a obvious BFS problem, the problem like this one will ask you the fewest steps or moves to reach some goal or point. No other tech required here.
grid[x][y][k], means the moves used to reach point(x, y) with k choices could be made left.
PS:
For this problem, the details cost me a lot of time. Minor spell errors killed my time to submit this one. Also, take care of the range of each dimension for your DP storage, which could resulted with error.
Source Code:
#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;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
class NumberLabyrinthDiv2 {
public:
int getMinimumNumberOfMoves(vector <string>, int, int, int, int, int);
bool checkBound(int x, int y);
int grid[51][51][51];
int M;
int N;
};
int NumberLabyrinthDiv2::getMinimumNumberOfMoves(vector <string> board, int r1, int c1, int r2, int c2, int K) {
M = board.size();
N = board[0].size();
memset(grid, -1, sizeof(grid));
deque<pair<pair<int, int>, int> > q;
q.push_back(make_pair(make_pair(r1, c1), K));
grid[r1][c1][K] = 0;
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int k = q.front().second;
q.pop_front();
if(r2 == x && c2 == y) continue;
if(board[x][y] == '.' ){
if(k>0)
for(int i=0; i<4; i++){
for(int j=1; j<=9; j++){
int xx = x + dx[i] * j;
int yy = y + dy[i] * j;
if(checkBound(xx, yy) && grid[xx][yy][k-1] == -1){
grid[xx][yy][k-1] = grid[x][y][k] + 1; //j;
q.push_back(make_pair(make_pair(xx, yy), k-1));
}
}
}
}
else{
int j = board[x][y] - '0';
if(j > 0)
for(int i=0; i<4; i++){
int xx = x + dx[i] * j;
int yy = y + dy[i] * j;
if(checkBound(xx, yy) && grid[xx][yy][k] == -1){
grid[xx][yy][k] = grid[x][y][k] + 1; //(board[x][y] - '0');
q.push_back(make_pair(make_pair(xx, yy), k));
}
}
}
}
int ret = -1;
for(int i=0; i<=K; i++){
if( grid[r2][c2][i]!=-1){
if(ret == -1 || grid[r2][c2][i] < ret){
ret = grid[r2][c2][i];
}
}
}
return ret;
}
bool NumberLabyrinthDiv2::checkBound(int x, int y){
return x>=0 && x<M && y>=0 && y<N;
}
//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
Division Two - Level Two:
Solution
Actually this is a math problem, the rem after divide by 9 is the rem of the sum of digits divide by 9, which means number % 9 == sumOfDigits(number) % 9, where sumOfDigits is the function to calculate the sum of each digits for a integer. Another property for this problem is each digit could be chosen 2^N-1 times, where N is the length of the string formatted integer, since each digit could be chosen or not chosen. Third, type conversion is also important, 1<<N is very different from 1LL<<N, the second one could convert the number to long long integer even if N is greater than 32. My code is challenged by this error.Source Code:
#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 <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class LuckyRemainder {
public:
int getLuckyRemainder(string);
};
int LuckyRemainder::getLuckyRemainder(string x) {
int N = x.size();
long long sum = 0LL;
for(int j=0; j<N; j++){
sum += (1LL<<N-1) * (x[j] - '0');
sum %= 9;
}
return sum;
}
//Powered by [KawigiEdit] 2.0!
Division Two - Level One:
Solution
Palindrome problems are always my favorites. For this problem, iterate from the smallest i until you find the number from subtraction is a palindrome number;
PS: another way to check the palindrome property is to check the reverse string's equality with the original one.
Source Code:
#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 <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class PalindromizationDiv2 {
public:
int getMinimumCost(int);
bool isP(string);
};
int PalindromizationDiv2::getMinimumCost(int X) {
for(int i = 0; ; i++){
stringstream s1;
stringstream s2;
s1 << (X+i);
s2 << (X-i);
if(isP(s1.str())){
return i;
}
if(X-i >=0 && isP(s2.str())){
return i;
}
}
return 0;
}
bool PalindromizationDiv2::isP(string s){
int i, j;
for(i=0, j=s.size()-1; i<j; i++, j--){
if(s[i] != s[j])
return false;
}
return true;
}
//Powered by [KawigiEdit] 2.0!
Subscribe to:
Posts
(
Atom
)