Magic Bitstrings

Magic Bitstrings

时间: 1ms        内存:128M

描述:

A bitstring, whose length is one less than a prime, might be magic. 1001 is one such string. In order to see the magic in the string let us append a non-bit x to it, regard the new thingy as a cyclic string, and make this square matrix of bits

 

each bit   1001  
every 2nd bit   0110  
every 3rd bit   0110  
every 4th bit   1001  

This matrix has the same number of rows as the length of the original bitstring. The m-th row of the matrix has every m-th bit of the original string starting with the m-th bit. Because the enlarged thingy has prime length, the appended x never gets used.

If each row of the matrix is either the original bitstring or its complement, the original bitstring is magic.

Each line of input (except last) contains a prime number p ≤ 100000. The last line contains 0 and this line should not be processed. For each prime number from the input produce one line of output containing the lexicographically smallest, non-constant magic bitstring of length p-1, if such a string exists, otherwise output Impossible.

输入:

输出:

示例输入:

5
3
17
47
2
79
0

示例输出:

0110
01
0010111001110100
0000100001101010001101100100111010100111101111
Impossible
001001100001011010000001001111001110101010100011000011011111101001011110011011

提示:

参考答案(内存最优[836]):

#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <stdlib.h>

#define MAX 1000

typedef struct { double x, y; } Point;
Point poly[MAX+10], ipoint[MAX+10];
Point a,b;
#define EPS 1e-8
#define SQR(x) ((x)*(x))

double dist2d(Point a, Point b) {
  return sqrt(SQR(a.x-b.x) + SQR(a.y-b.y));
}

int pt_in_poly(Point *p, int n, Point a) {
  int i, j, c = 0;
  for (i = 0, j = n-1; i < n; j = i++) {
    if (dist2d(p[i],a)+dist2d(p[j],a)-dist2d(p[i],p[j]) < EPS)
      return 1;
    if ((((p[i].y<=a.y) && (a.y<p[j].y)) ||
         ((p[j].y<=a.y) && (a.y<p[i].y))) &&
        (a.x < (p[j].x-p[i].x) * (a.y - p[i].y) 
               / (p[j].y-p[i].y) + p[i].x)) c = !c;
  }
  return c;
}

double dist_iline(Point a, Point b, Point p){
  return fabs(((a.y-p.y)*(b.x-a.x)-
               (a.x-p.x)*(b.y-a.y))
              /dist2d(a,b));
}

int isect_iline(Point a, Point b, Point c, Point d, Point *p){
  double r, denom, num1;
  if (dist_iline(c,d,a) < EPS && dist_iline(c,d,b) < EPS) return -1;
  num1  = (a.y - c.y) * (d.x - c.x) - (a.x - c.x) * (d.y - c.y);
  denom = (b.x - a.x) * (d.y - c.y) - (b.y - a.y) * (d.x - c.x);
  if (fabs(denom) >= EPS) {
    r = num1 / denom;
    p->x = a.x + r*(b.x - a.x);
    p->y = a.y + r*(b.y - a.y);
    return ((p->x-a.x)*(p->x-b.x) < 0 ||
	    (p->y-a.y)*(p->y-b.y) < 0 ||
	    fabs((p->x-a.x)*(p->x-b.x)) < EPS) ? 1 : 0; // in segment a,b
  } 
  if (fabs(num1) >= EPS) return 0;
  return -1;
}

int cmp( const void *a, const void *b) {
  const Point *ap = (Point *)a, *bp = (Point *)b;
  if (fabs(ap->x-bp->x) < EPS) {
    if (fabs(ap->y-bp->y) < EPS) return 0;
    if (ap->y < bp->y)   return -1;
    return 1;
  }
  if (ap->x < bp->x)     return -1;
  return 1;
}

void addifnew(Point c, int& cnt) {
  for (int i=0;i<cnt;i++) 
    if (dist2d(ipoint[i],c) < EPS) return;
  ipoint[cnt++]=c;
}

int main () {
  while (1) {
    int n, m;
    scanf("%d%d",&n, &m);
    if (!n) break;
    assert(2 < n && n <= MAX);
    for (int i=0;i<n;i++) scanf("%lf %lf", &poly[i].x, &poly[i].y);
    poly[n] = poly[0];
    for (;m;m--) {
      scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
      int ip = 0;
      Point p;
      for (int i=0;i<n;i++) {
	switch (isect_iline(poly[i], poly[i+1],a,b, &p)) {
	case 0: break;
	case 1: addifnew(p,ip); break;
	case -1: addifnew(poly[i],ip); addifnew(poly[i+1],ip); break;
	default: assert(0);
	}
      }
      qsort(ipoint,ip,sizeof(Point),cmp);
      double dist = 0.0;
      for(int i=0;i+1<ip;i++) {
	Point m;
	m.x = (ipoint[i].x+ipoint[i+1].x)/2;
	m.y = (ipoint[i].y+ipoint[i+1].y)/2;
	if (pt_in_poly(poly, n, m)) dist += dist2d(ipoint[i],ipoint[i+1]);
      }
      printf("%.3f\n",dist);
    }
  }
}

参考答案(时间最优[96]):

// PR, May 14, 2005

// 1 2
// 2 4  6
//   6  9 12
//     12 16 20
//        20 25 30
//           30 36 42
//              42 49 56

// Set 1 to 0, whatever is 2 then 4 has to be 0 because of the first
// two raws. 4 and 9 have to be the same bacause of raws 2 and 3
// and so on for all squares.

// find smallest binary magic string of lenght p-1 where p is prime 
// Set the diagonal of the magic square to 0's the rest to 1's.
// Indices that are quadratic residues mod p appear on the diagonal
// and p has the same number od residues and non-residues unless
// p is 2.
// there are 4 magic strings of any length except 2.

// The string must be a palindrom or its reverse is its complement.

#include <stdio.h>
#include <assert.h>
#include <math.h>

#define MAXP 100000

int isPrime(int a) {
  if (a < 2) return 0;
  for (int i = 2; i <= sqrt((double)a); i++) if (!(a%i)) return 0;
  return 1;
}

char A[MAXP+10];

int main () {
  while (1) {
    int p;
    scanf("%d",&p);
    if (!p) break;
    assert(isPrime(p) && p <= MAXP);
    if (p == 2) { printf("Impossible\n"); continue; }
    for (int i=1;i<p;i++) A[i] = '1';
    for (unsigned long long i=1;i<p;i++) 
      A[(i*i)%p]='0';
    for (int i=1;i<p;i++)
      printf("%c",A[i]);
    printf("\n");
  }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注