Desafios de Programação no Verão de 2011 - Prova 15 - Equipe

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Auxiliary Question of the Universe (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

char *s, *t;

static inline int is_num(char c) {
	return '0' <= c && c <= '9';
}

int main() {
	s = (char *) malloc(8192);
	t = (char *) malloc(8192);
	while (scanf("%s", s) != EOF) {
		int n = strlen(s), m;
		int ok = 1;
		while (ok) {
			m = ok = 0;
			for (int i = 0; i < n; i++) {
				if (i == 0 && s[i] == ')') {
					t[m++] = '('; t[m++] = '0'; t[m++] = ')'; ok = 1;
				} else if (i == 0 && s[i] == '+') {
					t[m++] = '0'; t[m++] = '+'; ok = 1;
				} else if (i+1 < n && s[i] == '(' && s[i+1] == ')') {
					t[m++] = '('; t[m++] = '0'; t[m++] = ')'; ok = 1; i++;
				} else if (i+1 < n && s[i] == ')' && s[i+1] == '(') {
					t[m++] = ')'; t[m++] = '+'; t[m++] = '('; ok = 1; i++;
				} else if (i+1 < n && is_num(s[i]) && s[i+1] == '(') {
					t[m++] = s[i]; t[m++] = '+'; t[m++] = '('; ok = 1; i++;
				} else if (i+1 < n && s[i] == ')' && is_num(s[i+1])) {
					t[m++] = ')'; t[m++] = '+'; t[m++] = s[i+1]; ok = 1; i++;
				} else if (i+1 < n && s[i] == '+' && s[i+1] == ')') {
					t[m++] = '+'; t[m++] = '0'; t[m++] = ')'; ok = 1; i++;
				} else if (i+1 < n && s[i] == '(' && s[i+1] == '+') {
					t[m++] = '('; t[m++] = '0'; t[m++] = '+'; ok = 1; i++;
				} else if (i+1 < n && s[i] == '+' && s[i+1] == '+') {
					t[m++] = '+'; t[m++] = '0'; t[m++] = '+'; ok = 1; i++;
				} else if (i == n-1 && s[i] == '(') {
					t[m++] = '('; t[m++] = '0'; t[m++] = ')'; ok = 1;
				} else if (i == n-1 && s[i] == '+') {
					t[m++] = '+'; t[m++] = '0'; ok = 1;
				} else {
					t[m++] = s[i];
				}
			}
			t[m] = '\0';
			swap(s, t);
			swap(n, m);
		}
		int c = 0;
		int abrir = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == '(') {
				c++;
			} else if (s[i] == ')') {
				c--;
			}
			if (c < 0) {
				abrir++;
				c++;
			}
		}
		for (int i = 0; i < abrir; i++) {
			printf("(");
		}
		printf("%s", s);
		for (int i = 0; i < c; i++) {
			printf(")");
		}
		printf("\n");
	}
	return 0;
}

Brackets (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include<algorithm>
#include<vector>
using namespace std;

#define NMAX 301
#define K 10
char s[NMAX];
long long pd[NMAX][NMAX][K], zero[K];
int N;

#define BASE 100000000
#define TAM 8
typedef long long ll;

void soma(ll * a, ll * b) {
	for(int i = 0; i < K; i++) {
		a[i] += b[i];
	}
	for(int i = 0 ; i < K-1; i++) {
		if(a[i] >= BASE) {
			ll sobra = a[i] / BASE;
			a[i] %= BASE;
			a[i+1] += sobra;
		}
	}
}

void sub(ll * a, ll * b, ll * r) {
	for(int i = 0; i < K; i++) {
		r[i] -= b[i];
		r[i] += a[i];
	}
	for(int i = 0 ; i < K - 1; i++) {
		if(r[i] >= BASE) {
			ll sobra = r[i] / BASE;
			r[i] %= BASE;
			r[i+1] += sobra;
		} else if(r[i] < 0) {
			ll sobra = -((-r[i]+BASE-1) / BASE);
			r[i] %= BASE;
			r[i] += BASE;
			r[i+1] += sobra;
		}
	}
}

void mult(ll * a, ll * b, ll * c) {
	memset(c, 0, sizeof(c));
	for(int i = 0; i < K; i++) {
		for(int j = 0; i+j < K; j++) {
			c[i+j] += a[i]*b[j];
		}
	}
	for(int i = 0 ; i < K-1; i++) {
		if(c[i] >= BASE) {
			ll sobra = c[i] / BASE;
			c[i] %= BASE;
			c[i+1] += sobra;
		}
	}
}


ll * f(int at,int fim) {
	int prim = -1;
	if(pd[at][fim][0] != -1) return &pd[at][fim][0];
	memset(pd[at][fim], 0, sizeof(pd[at][fim]));
	pd[at][fim][0] = 1;
	ll * resp = &pd[at][fim][0];
	for(int i = at; i < fim && prim == -1;i++) {
		if(s[i] == '(') prim = i;
	}
	if(prim == -1) {
		return &pd[at][fim][0];
	}
	ll *a, *b, *esq = &zero[0];
	ll d[K], e[K];
	for(int i = prim; i < fim; i++) {
		if(s[i] == ')') {
			a = f(prim+1, i);
			b = f(i+1, fim);
			memset(d, 0, sizeof(d));
			sub(a,esq,d);
			memset(e, 0, sizeof(e));
			mult(d,b,e);
			soma(resp, e);
			esq = a;
		}
	}
	return &pd[at][fim][0];
}

int main() {
	memset(zero, 0, sizeof(zero));
	while(scanf("%s", s)==1) {
		N = strlen(s);
		memset(pd, -1, sizeof(pd));
		ll * x = f(0,N);

		int p = K-1;
		for( ; x[p] == 0; p--);

		printf("%lld", x[ p ]);
		for(int i = p-1; i >= 0; i--) {
			printf("%08lld", x[i]);
		}
		printf("\n");
	}
	return 0;
}

Circles on the screen (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

struct C {
	int x,y,r;
};

C c[100];
int w,h;
int n;

int busca2(int ini, int fim, int linha, const C & bola) {
	int meio;
	long long rr = (long long) bola.r * (long long) bola.r, dx, dy, dist;
	while(ini + 2 < fim) {
		meio = (ini+fim) / 2;
		dx = bola.y - linha;
		dy = bola.x - meio;
		long long dist = dx*dx + dy*dy;
		if(dist <= rr) {
			ini = meio;
		} else {
			fim = meio;
		}
	}
	for(meio = fim; meio >= ini; meio--) {
		dx = bola.y - linha;
		dy = bola.x - meio;
		long long dist = dx*dx + dy*dy;
		if(dist <= rr) return meio;
	}
	return 0;
}

int busca1(int ini, int fim, int linha, const C & bola) {
	int meio;
	long long rr = (long long) bola.r * (long long) bola.r, dx, dy, dist;
	while(ini + 2 < fim) {
		meio = (ini+fim) / 2;
		dx = bola.y - linha;
		dy = bola.x - meio;
		long long dist = dx*dx + dy*dy;
		if(dist > rr) {
			ini = meio;
		} else {
			fim = meio;
		}
	}
	for(meio = ini; meio <= fim; meio++) {
		dx = bola.y - linha;
		dy = bola.x - meio;
		long long dist = dx*dx + dy*dy;
		if(dist <= rr) return meio;
	}
	return 0;
}

pair<int,int> calcula(int linha, const C & bola) {
	if(abs( linha - bola.y )  > bola.r) return make_pair(-1,-1);

	int a = busca1( 0, bola.x, linha, bola);
	int b = busca2( bola.x, w, linha, bola);

	return make_pair(a, b);
}


int main() {
	while(scanf("%d %d %d", &w, &h, &n) == 3) {
		for(int i = 0; i < n; i++) {
			scanf("%d %d %d", &c[i].x, &c[i].y, &c[i].r);
		}
		long long resp = 0;
		for(int l = 0; l < h; l++) {
			vector< pair<int,int> > v;
			v.push_back( make_pair(0, w-1) );
			for(int i = 0; i < n; i++) {
				pair<int,int> inter = calcula(l, c[i]);
//				printf("l = %d, i = %d => (%d, %d)\n", l, i, inter.first, inter.second);
				if(inter.first == -1) continue;
				vector< pair<int,int> > aux;
				for(vector< pair<int,int> >::iterator it = v.begin(); it != v.end(); it++) {
					pair<int,int> novo;
					novo.first = max(it->first, inter.first);
					novo.second = min(it->second, inter.second);
					if(novo.first > novo.second) {
						aux.push_back(*it);
						continue;
					}
					pair<int,int> entra1 = make_pair( it->first, novo.first - 1 );
					pair<int,int> entra2 = make_pair( novo.second + 1, it->second );
					if(entra1.first <= entra1.second) aux.push_back(entra1);
					if(entra2.first <= entra2.second) aux.push_back(entra2);
				}
				v = aux;
			}
			for(vector< pair<int,int> >::iterator it = v.begin(); it != v.end(); it++) {
				resp += it->second - it->first + 1;
			}			
		}
		printf("%lld\n", resp);
	}
	return 0;
}

Enigmatic device (por Unicamp Alpha)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>

typedef long long int llint;

using namespace std;

int __seq[2050][15];
int __seqOff[2050];
int __seqLoop[2050];

void init_seq() {
  for (int i=0; i<2010; i++) {
    int v=i;
    int it=0;
    map<int, int> jaPassou;
    int c;
    for (c=0; jaPassou.find(v) == jaPassou.end(); c++, v=(v*v)%2010) {
      __seq[i][c] = v;
      jaPassou[v]=c;
    }
    __seqOff[i] = jaPassou[v];
    __seqLoop[i] = c-jaPassou[v];
    /*
    printf("  Offset:%i, Loop:%i, Total:%i\n", jaPassou[v], c-jaPassou[v], c);
    printf("\n");*/
  }
}

int seq(int a, int k) {
  if (k < __seqLoop[a]) return __seq[a][k];
  if (k>= __seqOff[a]) {
    if (__seqLoop[a] == 0) 
      k = __seqOff[a];
    else
      k = (k-__seqOff[a]) % __seqLoop[a] + __seqOff[a];
  }
  
  return __seq[a][k];
}

int seq2(int a, int k) {
  for (int i=0; i<k; i++) 
    a = (a*a) % 2010;
  return a;
}

class Node {
public:
  llint sum[13];
  int lazyCoef;
  int rangeMin, rangeMax;
  
  Node *leftChild, *rightChild;
  Node(int pos=0, int val=0) : rangeMin(pos), rangeMax(pos) {
    sum[0] = val;
    
    //fprintf(stderr, "%lli ", sum[0]);
    for (int i=1; i<=12; i++) {
      sum[i] = (sum[i-1]*sum[i-1]) % 2010;
      //fprintf(stderr, "%lli ", sum[i]);
    }
    //fprintf(stderr, "\n");
    lazyCoef=0;
    leftChild = rightChild = NULL;
  }
  
  Node(Node* leftChild, Node* rightChild) : leftChild(leftChild), rightChild(rightChild) {
    rangeMin = leftChild->rangeMin;
    rangeMax = rightChild->rangeMax;
    mergeChildren();
  }
  ~Node() {
    if (leftChild) delete leftChild;
    if (rightChild) delete rightChild;
  }
  
  void mergeChildren() {
    lazyCoef = 0;
    for (int i=0; i<=12; i++)
      sum[i] = leftChild->sum[i] + rightChild->sum[i];
  }
  
  llint getSum(int rangeMin, int rangeMax) {
    if ((rangeMax < this->rangeMin) || (rangeMin > this->rangeMax)) 
      return 0;
    
    //Eu tenho o intervalo inteiro
    if (rangeMin <=this->rangeMin && rangeMax >= this->rangeMax) {
      //printf("%lli + ", this->sum);
      return this->sum[0];
    }
    
    //Preciso fazer a conta em cada filho
    unlazy();
    return leftChild->getSum(rangeMin, rangeMax) + rightChild->getSum(rangeMin, rangeMax);
  }
  
  void unlazy() {
    if (lazyCoef && leftChild && rightChild) {
      leftChild ->op (this->rangeMin, this->rangeMax, lazyCoef);
      rightChild->op(this->rangeMin, this->rangeMax, lazyCoef);
      lazyCoef=0;
    }
  }
  
  void printSeq(bool EOL=true) {
    if (leftChild && rightChild) {
      leftChild ->printSeq(false);
      rightChild->printSeq(false);
    } else {
      printf("%4lli ", sum[0] );
    }
    
    if (EOL) printf("\n");
  }
  
  void printTree(int level=0) {
    for (int i=0; i<level; i++) printf("  ");
    printf("[%i..%i] - Sum=%lli", rangeMin, rangeMax, sum[0]);
    
    if (leftChild && rightChild) {
      leftChild->printTree(level+1);
      rightChild->printTree(level+1);
    } 
  }
  
  void op(int rangeMin, int rangeMax, int qto=1) {
    if ((rangeMax < this->rangeMin) || (rangeMin > this->rangeMax)) return;
    //Aplica a operação apenas na raiz, deixa pra fazer nos filhos preguiçosamente, se necessário
    if (rangeMin <=this->rangeMin && rangeMax >= this->rangeMax) {
      llint oldSum[13];
      memcpy(oldSum, sum, sizeof(oldSum));
      
      /*
      for (int it=0; it<qto; it++) {
        for (int i=0; i<12; i++) {
          sum[i] = sum[i+1];
        }
        sum[12] = sum[2];
      }*/
      /*
      printf("oldSum: [ ");
      for (int i=0; i<=12; i++)
        printf("%lli ", oldSum[i]);
      printf("].    new sum: [");
      for (int i=0; i<=12; i++)
        printf("%lli ", sum[i]);
      printf("]\n");
      */
      
      for (int i=0; i<=12; i++) {
        int j = i+qto;
        if (j>2) {
          j=(j-2) % 10 + 2;
        }
        sum[i] = oldSum[j];
      }
      lazyCoef+=qto;
      
    } else {
      unlazy();
      //Junta os resultados aqui
      leftChild ->op (rangeMin, rangeMax, qto);
      rightChild->op (rangeMin, rangeMax, qto);
      mergeChildren();
    }
  }
};


Node* tree[100000];

int main() {
  init_seq();
  while (true) {
    int N;
    if (scanf("%i", &N) == EOF) return 0;
    
    for (int i=0; i<N; i++) {
      int v;
      scanf("%i", &v);
      tree[i] = new Node(i+1, v);
    }

    //Monta a arvore de segmentos
    while (N > 1) {
      for (int i=0; i<N/2; i++) {
        tree[i] = new Node(tree[2*i], tree[2*i+1]);
        //printf("[%i, %i] ", tree[i]->rangeMin, tree[i]->rangeMax);
      }
      if (N%2==1) {
        tree[N/2] = tree[N-1];
        //printf("[%i, %i] ", tree[N/2]->rangeMin, tree[N/2]->rangeMax);
        N = N/2+1;
      } else {
        N = N/2;
      }
      //printf("\n");
    }
    Node* rootNode = tree[0];
    
    //Realiza as operações
    int nops;
    scanf("%i", &nops);
    for (int op=1; op<=nops; op++) {
      int op, a, b;
      scanf("%i%i%i", &op, &a, &b);
      if (op == 1) {
        rootNode->op(a,b);
        //rootNode->printSeq();
        //rootNode->printTree();
        //rootNode->unlazyAndPrint();
        //printf("\n");
      } else { 
        printf("%lli\n", rootNode->getSum(a,b));
      }
    }
    //printf("\n=========================\n"); 
    delete rootNode;
  }
}

Homo or hetero? (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#include<string>
#define MAX 100100
using namespace std;
string op[MAX];
int num[MAX];
int qt[MAX], Q;
int main() {
	scanf("%d", &Q);
	map<int,int> nums;
	int at = 0;
	for(int i = 0;i < Q;i++) {
		char buf[100];
		scanf("%s %d", buf, num + i);
		op[i] = buf;
		if(!nums.count(num[i])) {
			nums[num[i]] = at++;
			num[i] = at-1;
		} else {
			num[i] = nums[num[i]];
		}
	}
	memset(qt, 0, sizeof(qt));
	set<int> homo;
	set<int> hetero;
	for(int i = 0;i < Q; i++) {
		if(op[i] == "insert") {
			qt[num[i]]++;
			if(qt[num[i]] >= 2) {
				homo.insert(num[i]);

			}
			hetero.insert(num[i]);
		} else if(qt[num[i]]){
			qt[num[i]]--;
			if(qt[num[i]] == 1) {
				if(homo.count(num[i])) {
					homo.erase(num[i]);
				}
			} else if(qt[num[i]] == 0) {
				if(homo.count(num[i])) {
					homo.erase(num[i]);
				}
				if(hetero.count(num[i])) {
					hetero.erase(num[i]);
				}
			}
		}
		if(!(homo.size() >= 1) && !(hetero.size() >= 2)) {
			printf("neither\n");
		}
		if((homo.size() >= 1) && (hetero.size()>=2)) {
			printf("both\n");
		}
		if(!(homo.size()>=1) && (hetero.size()>=2)) {
			printf("hetero\n");
		}
		if((homo.size()>=1) && !(hetero.size()>=2)) {
			printf("homo\n");
		}
	}
	return 0;
}

Kripke model (por AUHAUAH Balões Mano)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <queue>

using namespace std;

#define MAXL 32
#define MAXN 10004

int n, m, k;
vector<int> adj[MAXN];
char label[MAXN][MAXL];

void ef (int val)
{
	queue<int> fila;
	
	for (int i = 0; i < n; i++)
	{
		if (!label[i][val])
		{
			fila.push(i);
			label[i][k] = 1;
		}
	}
	
	while (!fila.empty())
	{
		int i = fila.front();
		fila.pop();
		
		for (int j = 0; j < (int) adj[i].size(); j++)
		{
			if (!label[adj[i][j]][k])
			{
				fila.push(adj[i][j]);
				label[adj[i][j]][k] = 1;
			}
		}
	}
}

void eu (int val)
{
	queue<int> fila;
	
	for (int i = 0; i < n; i++)
	{
		if (!label[i][k])
		{
			fila.push(i);
			label[i][k+1] = 1;
		}
	}
	
	while (!fila.empty())
	{
		int i = fila.front();
		fila.pop();
		
		for (int j = 0; j < (int) adj[i].size(); j++)
		{
			if (label[adj[i][j]][val] && !label[adj[i][j]][k+1])
			{
				fila.push(adj[i][j]);
				label[adj[i][j]][k+1] = 1;
			}
		}
	}
}

int main (void)
{
	scanf ("%d %d %d", &n, &m, &k);
	
	for (int i = 0; i < n; i++)
	{
		int x;
		
		scanf ("%d", &x);
		
		memset(label[i], 0, sizeof(label[i]));
		
		for (int j = 0; j < x; j++)
		{
			char ch[4];
			scanf (" %s", ch);
			ch[0] -= 'a';
			
			label[i][(int) ch[0]] = 1;
		}
	}
	
	for (int i = 0; i < m; i++)
	{
		int x, y;
		scanf ("%d %d", &x, &y);
		x--; y--;
		
		adj[y].push_back(x);
	}

	for (int i = 0; i < n; i++)
		adj[i].push_back(i);
	
	char formula[128];
	scanf (" %s", formula);
	
	ef(formula[7] - 'a');	
	eu(formula[2] - 'a');
	
	int qt = 0;
	for (int i = 0; i < n; i++)
	{
		if (label[i][k+1]) qt++;
	}
	
	printf ("%d\n", qt);
	
	for (int i = 0; i < n; i++)
	{
		if (label[i][k+1]) printf ("%d\n", i+1);
	}
	
	return 0;
}

Longest common subsequence (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#define MAX 100100
using namespace std;

#define N 100000
int A, B, a[N], b[N], v[N], lcs[N], t, n;
map<int, int> ma, mb, leva;

int calc() {
	t = 0;
	for(int i = 0; i < n; i++) {
		if(!leva.count( v[i] )) continue;
		int val = leva[ v[i] ];
//		printf("VAL = %d\n", val);
		int pos = lower_bound(lcs, lcs + t, val) - lcs;
//		printf("CABE na pos %d\n", pos);
		lcs[pos] = val;
		if(pos == t) {
			t++;
		}
	}
	return t;
}

int main() {
	int repa = 0, repb = 0;
	ma.clear(); mb.clear();
	scanf("%d %d", &A, &B);
	for(int i = 0; i < A; i++) {
		scanf("%d", a+i);
		if(!ma.count(a[i])) {
			ma[a[i]] = i;
		} else {
			repa = 1;
		}
	}
	for(int i = 0; i < B; i++) {
		scanf("%d", b+i);
		if(!mb.count(b[i])) {
			mb[b[i]] = i;
		} else {
			repb = 1;
		}
	}

	if(!repb) {
		leva = mb;
		n = A;
		for(int i = 0; i < n; i++) v[i] = a[i];
	} else {
		leva = ma;
		n = B;
		for(int i = 0; i < n; i++) v[i] = b[i];
	}

	printf("%d\n", calc());

	return 0;
}

Match maker (por aWARush/)

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;
#define MM 101010
char s[MM], pattern[MM], t[MM];
int lens, lent, lenpat;
int prefix[MM];
// chequear patron *#

void COMPUTE_PREFIX()
{
	int q = -1;
	prefix[0] = -1;
	
	for( int i = 1 ; i < lenpat ; i ++ )
	{
		while( q >= 0 && pattern[i] != pattern[q+1] ) q = prefix[q];
		if( pattern[i] == pattern[q+1] ) q++;
		prefix[i] = q;
	}
}
/// kmp matching! generalized :P

int match(int positiont, int mod)
{
//	cout << positiont << "   MATCH   " << mod << endl;
	int q = -1;
	for( int i = positiont ; i < lent ; i ++ )
	{
		while( q >= 0 && t[i] != pattern[q+1] ) q = prefix[q];
		if( t[i] == pattern[q+1] ) q ++;
		if( q+1 == lenpat )
		{
			
			if( ((i+1)-positiont) % 2 == (mod+lenpat)%2 )
				return i;
			
			q = prefix[q];	
		}
	}
	return -1;
}


// * es par.... # es impar...
bool ok(int poss, int post)
{
	if( poss == lens )
	{
		if( post == lent ) return true;
		return false;
	}
	if( s[poss] != '*' && s[poss] != '#'  && post == lent ) return false;
	if( s[poss] == '*' )
	{
		// even...
		if( poss + 1 == lens )
		{
			return (lent-post) % 2 == 0;
		}
		poss++;
		lenpat = 0;
		while( poss < lens && s[poss] >= '0' && s[poss] <= '9' )
			pattern[lenpat++] = s[poss++];
		pattern[lenpat] = '\0';
			
		COMPUTE_PREFIX();
//		cout << poss << "  " << lens << endl;
		if( poss == lens )
		{
			int last = lent-lenpat;
//			cout << (last-post) << "   " << match(last, 0) << endl;
			if( match(last, 0) != -1 && (last - post) % 2 == 0 ) return true;
			return false;
		}

		int next = match(post, 0);
		if( next == -1 ) return false;
		return ok(poss, next+1);
	}else if( s[poss] == '#' )
	{
		if( poss + 1 == lens )
		{
			return (lent-post) % 2 == 1 ;
		}
		poss ++;
		lenpat = 0;
		while( poss < lens && s[poss] >= '0' && s[poss] <= '9' )
			pattern[lenpat++] = s[poss++];		
			
		COMPUTE_PREFIX();
		
		if( poss == lens )
		{
			int last = lent-lenpat;
			if( match(last, 0) != -1 && (last - post) % 2 == 1 ) return true;
			return false;
		}
		
		
		int next = match(post, 1);
		if( next == -1 ) return false;
		return ok(poss, next+1);
	}else
	{
		if( s[poss] != t[post] ) return false;
		return ok(poss+1, post+1);
	}
}


void stand()
{
	int ind = 0;
	int len = strlen(s);
	for( int i = 0 ; i < len ; i ++ )
	{
		if( !ind ) ind++;
		else if( s[i] == '*' )
		{
			if( s[ind-1] == '*' ) continue;
			else if( s[ind-1] == '#' ) continue;
			else s[ind++] = '*';
		}else if( s[i] == '#' )
		{
			if( s[ind-1] == '*' ) s[ind-1] = '#';
			else if( s[ind-1] == '#' ) s[ind-1] = '*';
			else s[ind++] = '#';
		}else s[ind++] = s[i];
	}
	s[ind] = '\0';
}


int main()
{
	int i,j ,k;
	int capitulo = 0;
	while( 1 ) 
	{
		capitulo ++;
		int inciso = 0;
		scanf("%s", s);
		stand();

		while( 1 )
		{
			inciso++;
			scanf("%s", t);
			if( strcmp(t, "END") == 0 ) break;
			if( strcmp(t, "QUIT" ) == 0 ) return 0;
			lens = strlen(s);
			lent = strlen(t);
			printf("%d.%d. ", capitulo, inciso);
			if(ok(0, 0))
				printf("match\n");
			else printf("not\n");
		}
	}
	return 0;
}

Rice (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <set>

using namespace std;

typedef long long lld;
typedef unsigned long long llu;
typedef long double ldouble;
lld n;

#define FMAX 128

lld F[FMAX];
int CF[FMAX];
int f;
set <lld> D;

void gen(int idx, lld act) {
	if (idx == f) {
		if (act != n - 1) {
			D.insert(act);
		}
	} else {
		lld pot = 1;
		for (int i = 0; i <= CF[idx]; i++) {
			gen(idx+1, act * pot);
			pot*= F[idx];
		}
	}
}

llu mul_mod(llu a, llu b, llu m) {
	llu y = (llu)((ldouble)a*(ldouble)b/m+(ldouble)1/2);
	y = y * m;
	llu x = a * b;
	llu r = x - y;
	if ((lld) r < 0) {
		r = r + m;
		y = y - 1;
	}
	return r;
}

lld exp(lld a, lld e, lld mod) {
	if (e == 0) {
		return 1;
	}
	lld tmp = exp(a, e / 2, mod);
	if (e % 2 == 0) {
		return mul_mod(tmp, tmp, mod);
	} else {
		return mul_mod(mul_mod(tmp, tmp, mod), a, mod);
	}
}

int main() {
	scanf("%lld", &n);
	if (n == 2) {
		printf("1\n");
		return 0;
	}
	lld N = n - 1;
	f = 0;
	for (lld i = 2; i*i <= N; i++) {
		if (N % i == 0) {
			CF[f] = 0;
			F[f] = i;
			while (N % i == 0) {
				CF[f]++;
				N/= i;
			}
			f++;
		}
	}
	if (N != 1) {
		F[f] = N;
		CF[f] = 1;
		f++;
	}
	gen(0, 1);
	for (lld t = 2; t < n; t++) {
		int ok = 1;
		for (set<lld>::iterator it = D.begin(); it != D.end() && ok; it++) {
			if (exp(t, *it, n) == 1) {
				ok = 0;
			}
		}
		if (ok) {
			printf("%d\n", t);
			return 0;
		}
	}
	return 0;
}