Pagini recente » Cod sursa (job #3223439) | Cod sursa (job #699392) | Cod sursa (job #1807175) | Cod sursa (job #1408042) | Cod sursa (job #815114)
Cod sursa(job #815114)
#include<stdio.h>
#include<bitset>
#define maxn 45000
#define maxm 700000
#define maxmod 1005
using namespace std;
FILE*f=fopen("robotei.in","r");
FILE*g=fopen("robotei.out","w");
const int inf = (1<<29);
int n,m,xs,ys,modx,mody,offsetx,offsety;
int nextx[maxn],nexty[maxn],catix[maxmod],catiy[maxmod],dist[maxmod][maxmod],C[2][maxmod*maxmod];
int acum[maxmod][maxmod],sol[maxm];
bitset<maxmod>viz[maxmod];
inline void solve () {
if ( xs >= n || ys >= n ){
fprintf(g,"%d %d\n",0,1);
return ;
}
for ( int i = 0 ; i < modx ; ++i ){
for ( int j = 0 ; j < mody ; ++j ){
if ( viz[i][j] || (i == xs && j == ys) ) continue ;
int left = 1,right = 0; viz[i][j] = 1; acum[i][j] = 1;
++right; C[0][right] = i,C[1][right] = j;
while ( left <= right ){
int xv = nextx[C[0][left]],yv = nexty[C[1][left]];
if ( !viz[xv][yv] ){
++right;
C[0][right] = xv,C[1][right] = yv;
viz[xv][yv] = 1; acum[xv][yv] = right;
}
else{
if ( acum[xv][yv] ){
//ciclu
if ( !acum[xs][ys] ){
for ( int i = 1 ; i <= right ; ++i ){
dist[C[0][i]][C[1][i]] = inf;
}
}
else{
int p = acum[xs][ys];
for ( int i = 1 ; i < p ; ++i ){
dist[C[0][i]][C[1][i]] = p-i;
}
if ( acum[xv][yv] > p ){
for ( int i = p+1 ; i <= right ; ++i ){
dist[C[0][1]][C[1][i]] = inf;
}
}
else{
for ( int i = p+1 ; i <= right ; ++i ){
dist[C[0][i]][C[1][i]] = right-p+1 + p-acum[xv][yv];
}
}
}
}
else{
//deja calculat
int distanta = 0;
for ( int index = right ; index >= 1 ; --index ){
++distanta;
dist[C[0][index]][C[1][index]] = dist[xv][yv] + distanta;
if ( dist[C[0][index]][C[1][index]] >= inf ) dist[C[0][index]][C[1][index]] = inf;
}
}
break ;
}
++left;
}
for ( int index = 1 ; index <= right ; ++index ){
acum[C[0][index]][C[1][index]] = 0;
C[0][index] = C[1][index] = 0;
}
}
}
int cycle = 0,X = xs,Y = ys;
do{
++cycle;
X = nextx[X]; Y = nexty[Y];
}while( (X != xs || Y != ys) && cycle <= modx*mody+2);
if ( cycle == modx*mody+3 ){
cycle = m+1;
}
--m;
for ( int i = 0 ; i < modx ; ++i ){
for ( int j = 0 ; j < mody ; ++j ){
int turns = 0;
if ( dist[i][j] <= m ){
turns = 1 + (m-dist[i][j])/cycle;
}
sol[turns] += catix[i]*catiy[j];
}
}
++m;
--sol[m/cycle]; ++sol[1+m/cycle];
for ( int i = 0 ; i <= m ; ++i ){
if ( sol[i] ){
fprintf(g,"%d %d\n",i,sol[i]);
}
}
}
int main () {
fscanf(f,"%d %d %d %d %d %d %d %d",&n,&m,&xs,&ys,&modx,&mody,&offsetx,&offsety);
for ( int i = 0 ; i < n ; ++i ){
nextx[i] = (i*i+offsetx)%modx;
nexty[i] = (i*i+offsety)%mody;
++catix[nextx[i]]; ++catiy[nexty[i]];
}
solve();
fclose(f);
fclose(g);
return 0;
}