// link: http://cerberus.delos.com:790/usacoprob2?a=bcquvHYkCVC&S=runround
/*
ID: himuhas1
TASK: runround
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
using namespace std;
typedef unsigned long type;
int ara[10];
int main()
{
#ifndef hasibpc
freopen("runround.in", "r", stdin);
freopen("runround.out", "w", stdout);
#endif // hasibpc
type num, temp;
int k;
int mask;
int cntDigit;
int pos;
cin>>num;
bool isRunAround;
while(1)
{
num++;
isRunAround = 1;
mask = 0;
temp = num;
cntDigit = 0;
while(temp)
{
k = temp % 10;
ara[cntDigit] = k;
if(mask & (1<<k))
{
isRunAround = 0;
break;
}
mask = mask | (1<<k);
temp /= 10;
cntDigit++;
}
if(isRunAround)
{
reverse(ara, ara+cntDigit);
mask = 0;
pos = 0;
while(1)
{
//cout<<"pos " << pos<<endl;
mask = mask | (1<<pos);
pos = (pos + ara[pos]) % cntDigit;
if(mask & (1<<pos))
{
if(pos != 0 || (1<<cntDigit)-1 != mask)
{
isRunAround = 0;
}
break;
}
}
}
//cout<<num<<endl;
if(isRunAround) break;
}
cout<<num<<endl;
return 0;
}
Category Archives: BitMask
(LightOj) 1018 – Brush (IV)
0
/*
user: php
link: http://lightoj.com/volume_showproblem.php?problem=1018
time: 0.772 sec
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
using namespace std;
#define ll long long
#define MAXX 17
#define check(mask, i) (mask & (1<<i))
#define set(mask, i) (mask | (1<<i))
struct DATA{
int x, y;
};
DATA places[MAXX];
int number_of_dust;
ll dp[1<<MAXX];
bool sameTriangle(int i, int j, int k)
{
return (places[j].y - places[i].y) * (places[k].x - places[i].x) == (places[j].x - places[i].x) * (places[k].y - places[i].y);
}
ll rec(int used)
{
/*
cout<<"calling ";
loop(i, number_of_dust)
{
if(check(used, i) == 0) cout<<0;
else cout<<1;
}
cout<<endl;
*/
ll &ret = dp[used];
if(ret != -1) return ret;
int cnt = 0;
loop(i, number_of_dust)
{
if(check(used, i) == 0) cnt++;
}
if(cnt == 1) return 1;
ret = INF;
loop(i, number_of_dust)
{
if(check(used, i) == 0)
{
int temp = (used | (1<<i));
FOR(j, i+1, number_of_dust)
{
int bt = (used | (1<<i));
if(check(temp, j) == 0)
{
temp = temp | (1<<j);
bt = bt | (1<<j);
loop(k, number_of_dust)
{
if(check(temp, k) == 0 && sameTriangle(i, j, k))
{
temp = temp | (1<<k);
bt = bt | (1<<k);
}
}
ret = min(ret, 1 + rec(bt));
}
}
break;
}
}
return ret;
}
int main()
{
int kases, kaseno = 0;
getint(kases);
while(kases--)
{
getint(number_of_dust);
loop(i, number_of_dust)
{
getint(places[i].x); getint(places[i].y);
}
mem(dp, -1);
dp[ (1<<number_of_dust) - 1 ] = 0;
pf("Case %d: %lld\n", ++kaseno, rec(0));
}
}
(UVa) 11553 – Grid Game
0The following two expression is NOT same.
1<<N - 1
(1<<N) - 1
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2548
time: 0.068 sec
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 10
int grid[MAXX][MAXX];
int dp[1<<MAXX][1<<MAXX];
int N;
int rec(int alice, int bob)
{
int &ret = dp[alice][bob];
if(ret != -1) return ret;
ret = -INF;
int temp;
loop(i, N)
{
if( (alice & (1<<i)) == 0 )
{
temp = INF;
loop(j, N)
{
if( (bob & (1<<j)) == 0 )
{
temp = min(temp, grid[i][j] + rec((alice | (1<<i)), (bob | (1<<j))) );
}
}
ret = max(ret, temp);
}
}
return ret;
}
int main()
{
//read();
int kases;
getint(kases);
while(kases--)
{
getint(N);
loop(i, N)
{
loop(j, N)
{
getint(grid[i][j]);
}
}
mem(dp, -1);
dp[(1<<N)-1][(1<<N)-1] = 0;
pf("%d\n", rec(0, 0));
}
return 0;
}
(UVa) 10032 – Tug of War
10
/*
user: php
time: 0.216 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 45000+2
int cnt, totalsum, half;
ll dp[MAXX];
int weight[101];
ll bit;
int main()
{
//read();
bool blank = false;
int kases;
getint(kases);
while(kases--)
{
getint(cnt);
totalsum = 0;
loop(i, cnt)
{
getint(weight[i]);
totalsum += weight[i];
}
mem(dp, 0);
dp[0] = 1<<0;
loop(i, cnt)
{
for(int j=totalsum; j>-1; j--)
{
if(dp[j])
{
dp[j + weight[i] ] |= (dp[j]<<1);
}
}
}
half = totalsum/2;
bit = cnt/2;
bit = 1LL<<bit;
int aa;
for(int i=half, j = half; i>-1 && j<=totalsum; i--, j++)
{
if((dp[i] & bit) )
{
aa = i;
break;
}
if((dp[j] & bit))
{
aa = j;
break;
}
}
if(blank) pf("\n");
blank = true;
pf("%d %d\n", min(aa, totalsum-aa), max(aa, totalsum-aa));
}
return 0;
}
(UVa) 624 – CD
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=565
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 10000
bool dp[MAXX];
int cdused[MAXX];
int tracklen[22];
int total;
int cnt;
int coinchange()
{
mem(dp, 0);
mem(cdused, 0);
dp[0] = 1;
int k;
loop(i, cnt)
{
for(int j=total-1; j>-1; j--)
{
k = j + tracklen[i];
if(dp[j] == true && dp[k] == false)
{
dp[k] = true;
cdused[k] = ((1<<i) | cdused[j]);
}
}
}
for(int i=total; i>-1; i--)
{
if(dp[i])
{
return i;
}
}
}
int main()
{
int maxposs;
while(sf("%d", &total) == 1)
{
getint(cnt);
loop(i, cnt)
{
getint(tracklen[i]);
}
maxposs = coinchange();
loop(i, cnt)
{
if( (cdused[maxposs] & 1<<i) )
{
pf("%d ", tracklen[i]);
}
}
pf("sum:%d\n", maxposs);
}
return 0;
}
(UVa) 12462 – Rectangle
0
/*
user: php
time: 0.112 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3905
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
using namespace std;
#define MAXX 100003
#define XOR(a, b) ((a) | (b) )
int histogram, totalcolors;
int colors[MAXX], heights[MAXX];
ll area[MAXX];
void leftToRight()
{
stack<int>sk;
sk.push(0);
for(int i=1; i<= histogram; i++)
{
while( heights[sk.top()] >= heights[i] )
{
colors[i] = XOR(colors[i], colors[sk.top()]);
sk.pop();
}
area[i] = ((ll)(i - sk.top())) * (ll)(heights[i]);
sk.push(i);
}
}
void rightToLeft()
{
stack<int>sk;
sk.push(histogram+1);
for(int i=histogram; i > 0; i--)
{
while( heights[sk.top()] >= heights[i] )
{
colors[i] = XOR(colors[i], colors[sk.top()]);
sk.pop();
}
area[i] += ((ll)(sk.top() - i)) * (ll)(heights[i]);
sk.push(i);
}
}
int main()
{
ll maxarea;
int tocolor;
while(true)
{
getint(histogram); getint(totalcolors);
if(histogram == 0 && totalcolors == 0) break;
heights[0] = 0;
colors[0] = 0;
for(int i=1; i <= histogram; i++)
{
getint(heights[i]);
}
for(int i=1; i <= histogram; i++)
{
getint(colors[i]);
colors[i] = (1<<colors[i]);
}
heights[histogram + 1] = 0;
colors[histogram + 1] = 0;
leftToRight();
rightToLeft();
for(int i=1; i<=histogram; i++)
area[i] -= heights[i];
maxarea = 0;
tocolor = (1<<totalcolors) - 1;
for(int i=1; i<=histogram; i++)
{
if(colors[i] == tocolor )
maxarea = max(maxarea, area[i]);
}
pf("%lld\n", maxarea);
}
return 0;
}
UnLucky Codes 