2014年09月14日13時20分48秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int X, Y;
int main(){
int i, j, k;
while(scanf("%d%d",&X,&Y)==2){
for(i=2;;i++){
if(X*i <= Y*(i-1)) break;
}
printf("%d\n",i);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int P, N;
int main(){
int i, j, k;
int res;
while(scanf("%d",&P)==1){
N = P/2;
res = 0;
i = 1;
for(;;){
if(i <= N) i = i * 2;
else i = (i-N) * 2 - 1;
res++;
if(i==1) break;
}
printf("%d\n",res);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
int N, M;
int A[555], B[555], C[555], D[555];
int X, Y, Z;
ull val[100001];
ull hs[1000];
int main(){
int i, j, k;
int res, now;
ll lef;
hs[0] = 873;
REP(i,1,1000) hs[i] = hs[i-1] * 107371;
while(scanf("%d%d",&M,&N)==2){
rep(i,M){
reader(A+i, B+i);
reader(C+i, D+i);
}
rep(i,N){
reader(&X, &Y, &Z);
val[i] = 0;
rep(j,M){
lef = (ll)X * A[j] + (ll)Y * B[j] + (ll)Z * C[j] - D[j];
if(lef > 0) val[i] += hs[j];
}
}
sort(val, val+N);
now = res = 0;
rep(i,N){
if(i && val[i]==val[i-1]) now++;
else now = 1;
res = max(res, now);
}
writer(res,'\n');
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
typedef struct struct_kdyenbxjdhd{
int node, nodeMemory;
int *edgeSize, *edgeMemory;
int **edge;
}ListGraph;
ListGraph NewListGraph(int maxNode,int maxDegree){
int i; ListGraph res;
res.node=0; res.nodeMemory=maxNode;
res.edgeSize = (int*)malloc(maxNode*sizeof(int));
res.edgeMemory = (int*)malloc(maxNode*sizeof(int));
res.edge = (int**)malloc(maxNode*sizeof(int*));
rep(i,maxNode) res.edgeMemory[i]=maxDegree;
if(maxDegree) rep(i,maxNode) res.edge[i]=(int*)malloc(maxDegree*sizeof(int));
return res;
}
void DeleteListGraph(ListGraph g){
int i;
rep(i,g.nodeMemory) if(g.edgeMemory[i]) free(g.edge[i]);
free(g.edgeSize); free(g.edgeMemory); free(g.edge);
}
void ListGraphSetEmpty(ListGraph *g,int node){
int i;
g->node = node;
rep(i,node) g->edgeSize[i]=0;
}
void ListGraphAddEdge(ListGraph *g,int node1,int node2){
int s=g->edgeSize[node1]++;
g->edge[node1][s]=node2;
}
void ListGraphAddBidirectedEdge(ListGraph *g,int node1,int node2){
int s1,s2;
if(node1==node2){
s1=g->edgeSize[node1]++;
g->edge[node1][s1]=node2;
} else {
s1=g->edgeSize[node1]++, s2=g->edgeSize[node2]++;
g->edge[node1][s1]=node2; g->edge[node2][s2]=node1;
}
}
/* edgeMemory[k]=sizeに変更する.中身のデータは破壊される. */
/* fg=1 ならば,すでにedgeMemory[k]>=sizeの場合は何もしない */
void ListGraphOneEdgeReallocEasy(ListGraph *g,int k,int size,int fg){
if(fg==1 && g->edgeMemory[k]>=size) return;
if(g->edgeMemory[k]==size) return;
if(g->edgeMemory[k]) free(g->edge[k]);
g->edgeMemory[k]=size;
g->edge[k] = (int*)malloc(size*sizeof(int));
}
/* g.nodeは既に設定済み,edgeのメモリが足りてない場合は適当にメモリ確保するぜ */
void ListGraphSetDirectEdges(ListGraph *g,int from[],int to[],int size){
int i,n=g->node;
rep(i,n) g->edgeSize[i]=0;
rep(i,size) g->edgeSize[from[i]]++;
rep(i,n) {ListGraphOneEdgeReallocEasy(g,i,g->edgeSize[i],1); g->edgeSize[i]=0;}
rep(i,size) ListGraphAddEdge(g,from[i],to[i]);
}
void ListGraphSetBidirectEdges(ListGraph *g,int from[],int to[],int size){
int i,n=g->node;
rep(i,n) g->edgeSize[i]=0;
rep(i,size) g->edgeSize[from[i]]++, g->edgeSize[to[i]]++;
rep(i,n) {ListGraphOneEdgeReallocEasy(g,i,g->edgeSize[i],1); g->edgeSize[i]=0;}
rep(i,size) ListGraphAddBidirectedEdge(g,from[i],to[i]);
}
void ListGraphBridgeVisit(ListGraph *g, int v, int u, int res[], int roots[], int *roots_size, int S[], int *S_size, int inS[], int num[], int tm, int br1[], int br2[], int *br_size){
int i, k;
num[v] = ++tm;
S[(*S_size)++] = v; inS[v] = 1;
roots[(*roots_size)++] = v;
rep(i, g->edgeSize[v]){
int w = g->edge[v][i];
if(num[w] == 0){
ListGraphBridgeVisit(g, w, v, res, roots, roots_size, S, S_size, inS, num, tm, br1, br2, br_size);
} else if(u != w && inS[w]){
while(num[roots[(*roots_size)-1]] > num[w]) (*roots_size)--;
}
}
if(v == roots[(*roots_size)-1]){
br1[*br_size] = u;
br2[*br_size] = v;
(*br_size)++;
k = S[(*S_size)-1];
for(;;){
int w = S[--(*S_size)];
inS[w] = 0;
res[w] = k;
if(v==w) break;
}
(*roots_size)--;
}
}
/* 二重頂点連結成分 (無向グラフ) */
/* res[i]=res[j]ならノードiとノードjは同じ連結成分 */
/* 橋の数が戻り値,br1, br2に橋が入る (始点ノード,終点ノード) */
int ListGraphBridge(ListGraph *g, int res[], int br1[], int br2[], void *WorkMemory){
int i,j,k;
int n = g->node;
int tm;
int *roots, *S, *num, *inS;
int roots_size = 0, S_size = 0, br_size = 0;
num = (int*) WorkMemory; WorkMemory = (void*)(num + n);
roots = (int*) WorkMemory; WorkMemory = (void*)(roots + n);
S = (int*) WorkMemory; WorkMemory = (void*)(S + n);
inS = (int*) WorkMemory; WorkMemory = (void*)(inS + n);
rep(i,n) num[i] = 0, inS[i] = 0;
rep(i,n) if(num[i]==0){
ListGraphBridgeVisit(g, i, n, res, roots, &roots_size, S, &S_size, inS, num, tm, br1, br2, &br_size);
br_size--;
}
return br_size;
}
template <class T>
struct DijkstraHeap {
int *hp, *place, size; char *visited; T *val;
void malloc(int N){hp=(int*)std::malloc(N*sizeof(int));place=(int*)std::malloc(N*sizeof(int));visited=(char*)std::malloc(N*sizeof(char));val=(T*)std::malloc(N*sizeof(T));}
void free(){free(hp);free(place);free(visited);free(val);}
void* malloc(int N, void *workMemory){hp=(int*)workMemory;place=(int*)(hp+N);visited=(char*)(place+N);val=(T*)(visited+N);workMemory=(void*)(val+N);return workMemory;}
void init(int N){int i;size=0;rep(i,N)place[i]=-1,visited[i]=0;}
void up(int n){int m;while(n){m=(n-1)/2;if(val[hp[m]]<=val[hp[n]])break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
void down(int n){int m;for(;;){m=2*n+1;if(m>=size)break;if(m+1<size&&val[hp[m]]>val[hp[m+1]])m++;if(val[hp[m]]>=val[hp[n]]) break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
void change(int n, T v){if(visited[n]||(place[n]>=0&&val[n]<=v))return;val[n]=v;if(place[n]==-1)place[n]=size,hp[size++]=n,up(place[n]);else up(place[n]);}
int pop(void){int res=hp[0];place[res]=-1;size--;if(size)hp[0]=hp[size],place[hp[0]]=0,down(0);visited[res]=1;return res;}
};
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
int N, M;
int A[22222], B[22222], C[22222];
vector<int> edge[11000], cost[11000];
int Q, st, len;
int b1[100000], b2[100000], cyc[100000];
int clen[100000];
#define INF 1000000000
int main(){
int i, j, k, t;
ListGraph g = NewListGraph(11000, 0);
void *mem = malloc(10000000);
DijkstraHeap<int> hp;
int res, dis;
hp.malloc(20000);
while(scanf("%d%d",&N,&M)==2){
rep(i,N) edge[i].clear(), cost[i].clear();
rep(t,M){
reader(&i,&j,&k); i--; j--;
edge[i].push_back(j); cost[i].push_back(k);
edge[j].push_back(i); cost[j].push_back(k);
A[t] = i; B[t] = j; C[t] = k;
}
g.node = N;
ListGraphSetBidirectEdges(&g, A, B, M);
ListGraphBridge(&g, cyc, b1, b2, mem);
rep(i,N) clen[i] = 0;
rep(i,M) if(cyc[A[i]]==cyc[B[i]]) clen[cyc[A[i]]] += C[i];
reader(&Q);
while(Q--){
reader(&st,&len); st--;
res = INF;
hp.init(N);
hp.change(st, 0);
while(hp.size){
i = hp.pop();
dis = hp.val[i];
if(clen[cyc[i]] >= len) res = min(res, dis+dis+clen[cyc[i]]);
rep(j,edge[i].size()){
k = edge[i][j];
hp.change(k, dis + cost[i][j]);
}
}
if(res==INF) res = -1;
writer(res, '\n');
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
template<class T>
struct ullHash{
ull *key; T *val; unsigned memory, size, mask;
void clear(){memset(val,0,size*sizeof(T));}
void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
int function(ull a){return (a*97531)&mask;}
T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};
template<class T1, class T2> void sort(int N, T1 a[], T2 b[], void *mem){int i;pair<T1,T2> *r=(pair<T1, T2>*)mem;rep(i,N)r[i].first=a[i],r[i].second=b[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second;}
ullHash<int> hash;
int polyX[11][50000][11], polyY[11][50000][11], sz[11];
ull geths(int len, int x[], int y[]){
int i;
ull hs = 42;
rep(i,len) hs = hs * 19874891 + 1074178147781ULL + x[i];
rep(i,len) hs = hs * 19874891 + 1074178147781ULL + y[i];
return hs;
}
int N, M;
int mp[111][111];
int main(){
int i, j, k, len, ii, jj, kk, tmp;
int x[11], y[11], nx[11], ny[11];
int d, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int mmx, mmy;
int res;
ull hs;
void *mem = malloc(1000000);
hash.init(5000000, 5000000);
sz[1] = 1;
polyX[1][0][0] = polyY[1][0][0] = 0;
hs = geths(1, polyX[1][0], polyY[1][0]);
hash.increase(hs);
REP(len,2,11){
rep(k,sz[len-1]){
rep(i,len-1) x[i] = polyX[len-1][k][i], y[i] = polyY[len-1][k][i];
rep(i,len-1) rep(d,4){
x[len-1] = x[i] + dx[d];
y[len-1] = y[i] + dy[d];
rep(j,len) nx[j] = x[j], ny[j] = y[j];
sort(len, nx, ny, mem);
REP(j,1,len) if(nx[j]==nx[j-1] && ny[j]==ny[j-1]) break;
if(j < len) continue;
mmx = mmy = 1000000000;
rep(j,len) mmx = min(mmx, nx[j]), mmy = min(mmy, ny[j]);
rep(j,len) nx[j] -= mmx, ny[j] -= mmy;
hs = geths(len, nx, ny);
if(hash.increase(hs) == 1){
rep(j,len) polyX[len][sz[len]][j] = nx[j], polyY[len][sz[len]][j] = ny[j];
sz[len]++;
}
}
}
}
while(scanf("%d%d",&N,&M)==2){
rep(i,N) rep(j,N) reader(mp[i]+j);
res = 0;
rep(i,N) rep(j,N) rep(k,sz[M]){
tmp = 0;
rep(kk,M){
ii = i + polyX[M][k][kk];
jj = j + polyY[M][k][kk];
if(ii < 0 || jj < 0 || ii >= N || jj >= N){ tmp = 0; break; }
tmp += mp[ii][jj];
}
res = max(res, tmp);
}
writer(res, '\n');
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
#define MD 10000
struct llModMatrix{
int r, c, mod; ll limit; ll **data;
void malloc(int r, int c, int mod){int i;this->r=r;this->c=c;this->mod=mod;limit=((1ULL<<63)-1)-(ull)(mod-1)*(mod-1);data=(ll**)std::malloc(sizeof(ll*)*r);data[0]=(ll*)std::malloc(sizeof(ll)*r*c);REP(i,1,r)data[i]=data[i-1]+c;}
void* malloc(int r, int c, int mod, void *workMemory){int i;this->r=r;this->c=c;this->mod=mod;limit=((1ULL<<63)-1)-(ull)(mod-1)*(mod-1);data=(ll**)workMemory;data[0]=(ll*)(data+r);REP(i,1,r)data[i]=data[i-1]+c;return (void*)(data[0]+r*c);}
void free(void){std::free(data[0]);std::free(data);}
void setIdentity(){int i,j;rep(i,r)rep(j,c){data[i][j]=0;if(i==j)data[i][j]=1;}}
void setZero(){int i,j;rep(i,r)rep(j,c)data[i][j]=0;}
void operator=(llModMatrix &a){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c)data[i][j]=a.data[i][j];}
void operator+=(llModMatrix &a){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c){data[i][j]+=a.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
void operator-=(llModMatrix &a){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c){data[i][j]-=a.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
void mixed(void){int i,j;rep(i,r)rep(j,c){if(data[i][j]<0)data[i][j]+=mod;if(data[i][j]&&rand()%2)data[i][j]-=mod;}}
void add(llModMatrix &a, llModMatrix &b){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c){data[i][j]=a.data[i][j]+b.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
void sub(llModMatrix &a, llModMatrix &b){int i,j;r=a.r;c=a.c;rep(i,r)rep(j,c){data[i][j]=a.data[i][j]-b.data[i][j];if(data[i][j]>=mod)data[i][j]-=mod;if(data[i][j]<=-mod)data[i][j]+=mod;}}
void mul(llModMatrix &a, llModMatrix &b){int i,j,k;r=a.r;c=b.c;setZero();rep(i,r)rep(k,a.c)if(a.data[i][k])rep(j,c){data[i][j]+=a.data[i][k]*b.data[k][j];if(data[i][j]>=limit||data[i][j]<=-limit)data[i][j]%=mod;}rep(i,r)rep(j,c)if(data[i][j]>=mod||data[i][j]<=-mod)data[i][j]%=mod;}
void pow(llModMatrix &a, ull b, void *workMemory){llModMatrix t1,t2;r=c=a.r;workMemory=t1.malloc(r,c,mod,workMemory);workMemory=t2.malloc(r,c,mod,workMemory);setIdentity();t1=a;while(b){if(b%2){t2=*this;this->mul(t2,t1);}t2.mul(t1,t1);t1=t2;b/=2;}}
};
int N, L, st, ed;
int main(){
int i, j, k, res;
llModMatrix mt, pw;
void *mem = malloc(100000000);
mt.malloc(100, 100, MD);
pw.malloc(100, 100, MD);
while(scanf("%d%d",&N,&L)==2){
reader(&st, &ed); st--; ed--;
mt.r = mt.c = N;
mt.setZero();
rep(i,N) rep(j,N) mt.data[i][j] = 0;
rep(i,N) rep(j,4){
reader(&k);
mt.data[i][k-1]++;
}
pw.pow(mt, L, mem);
res = pw.data[st][ed] % MD;
if(res < 0) res += MD;
writer(res,'\n');
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
#define INF 1000000000
int N;
char mp[222][222];
int q[22222], q_st, q_size;
int dist[222][222];
int res;
int is_ok(char c, int mask){
int i;
if('A' <= c && c <= 'Z'){
i = c - 'A';
if(mask & 1<<i) return 0;
} else {
i = c - 'a';
if(!(mask & 1<<i)) return 0;
}
return 1;
}
int main(){
int i, j, k, mask;
int si, sj, ni, nj, di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1}, d;
while(scanf("%d",&N)==1){
rep(i,N) reader(mp[i]);
res = INF;
rep(mask, 1<<10){
if(is_ok(mp[0][0], mask)==0) continue;
if(is_ok(mp[N-1][N-1], mask)==0) continue;
rep(i,N) rep(j,N) dist[i][j] = -1;
dist[0][0] = 1;
q[0] = 0; q_st = 0; q_size = 1;
while(q_size){
k = q[q_st++]; q_size--;
si = k / N;
sj = k % N;
rep(d,4){
ni = si + di[d];
nj = sj + dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
if(is_ok(mp[ni][nj], mask)==0) continue;
if(dist[ni][nj] >= 0) continue;
dist[ni][nj] = dist[si][sj] + 1;
q[q_st+q_size++] = ni * N + nj;
}
}
if(dist[N-1][N-1] >= 0) res = min(res, dist[N-1][N-1]);
}
if(res == INF) res = -1;
writer(res, '\n');
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
int N, M;
int res;
int main(){
int i, j, k;
while(scanf("%d%d",&N,&M)==2){
res = 0;
while(N--){
k = 1;
rep(i,M){
reader(&j);
if(j==0) k = 0;
}
res += k;
}
writer(res,'\n');
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;
r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
while(r1>0){
q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1;
r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
}
*c=r0; *a=a0; *b=b0;
}
ll get_inv(ll n, ll p){
ll a,b,c;
extended_euclid(n,p,&c,&a,&b);
if(a<p) a+=p;
return a%p;
}
ull pw(ull a, ull b, ull m){ull r=1;while(b){if(b&1)r=r*a%m;b>>=1;a=a*a%m;}return r;}
int N, E, C;
int main(){
int i, j, k;
int p, q, phi, d;
int res;
while(scanf("%d%d%d",&N,&E,&C)==3){
for(p=3;;p+=2) if(N%p==0) break;
q = N / p;
phi = (p-1) * (q-1);
d = get_inv(E, phi);
res = pw(C, d, N);
printf("%d\n",res);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
double getd(double dx,double dy){ return sqrt(dx*dx+dy*dy); }
double dp[222][222];
double dist[222][222];
int N;
double X[222], Y[222];
double solve(int a, int b){
int i, j, k;
double res = 1e100, tmp;
if(dp[a][b] > -1) return dp[a][b];
if((a+1)%N == b) return dp[a][b] = 0;
for(i=(a+1)%N;i!=b;i=(i+2)%N) for(j=(i+1)%N;j!=(b+1)%N;j=(j+2)%N){
tmp = 0;
if(i != (a+1)%N) tmp += dist[a][i];
if(j != (i+1)%N) tmp += dist[i][j];
if(b != (j+1)%N) tmp += dist[j][b];
if(res <= tmp) continue;
tmp += solve(a,i);
if(res <= tmp) continue;
tmp += solve(i,j);
if(res <= tmp) continue;
tmp += solve(j,b);
if(res <= tmp) continue;
res = tmp;
}
return dp[a][b] = res;
}
int main(){
int i, j, k;
double res;
while(scanf("%d",&N)==1){
N *= 2;
rep(i,N) scanf("%lf%lf",X+i,Y+i);
if(N==4){
puts("0.0000");
continue;
}
rep(i,N) dist[i][i] = 0;
rep(i,N) REP(j,i+1,N) dist[i][j] = dist[j][i] = getd(X[i]-X[j], Y[i]-Y[j]);
rep(i,N) rep(j,N) dp[i][j] = -2;
res = 1e100;
rep(i,N) res = min(res, solve(i,(i+N-1)%N));
printf("%.4f\n",res);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
#define EPS 1e-8
int C, N;
int A[100000];
int main(){
int i, j, k;
double mn, mx, per, tmp;
while(scanf("%d%d",&C,&N)==2){
rep(i,N) reader(A+i);
mn = -1e100; mx = 1e100;
per = C / (double) N;
rep(i,N){
mn = max(mn, A[i] - (i+1)*per);
mx = min(mx, A[i] - i*per);
}
if(mn < mx - EPS) writer("S\n"); else writer("N\n");
}
return 0;
}
Current time: 2024年05月03日20時09分06秒
Last modified: 2014年09月14日13時20分48秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)