Esta obra foi licenciada com uma Licença
Creative Commons - Atribuição - Uso Não-Comercial - Obras Derivadas Proibidas 3.0 Não Adaptada.
Hora de início: 2011-01-31 09:11:00 -0200 Hora de término: 2011-01-31 13:11:00 -0200
| POS | Competidor | Resultado | Pontuação | A | B | C | D | E | F | G | H | I | J | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | hackermath | 8 (1112) | 33 | +1 | +0 | +3 | +0 | +7 | +0 | +2 | +1 | |||
| 2 | [IME-USP] Isso é tudo pessoal | 7 (762) | 31 | +0 | +3 | +0 | +0 | -25 | +1 | +0 | +3 | |||
| 3 | aWARush/ | 7 (851) | 29 | +0 | +0 | +3 | +0 | +2 | +0 | +1 | -5 | |||
| 4 | Garotos da OBI | 7 (961) | 27 | +1 | +1 | +1 | +2 | +0 | +5 | +0 | ||||
| 5 | [ITA] Carteado | 7 (1133) | 25 | +2 | +0 | +3 | +1 | +3 | +1 | +5 | ||||
| 6 | SUDO | 5 (635) | 23 | +0 | +2 | +1 | +1 | +0 | -2 | |||||
| 7 | Depois a gente diz! | 5 (701) | 21 | +1 | +0 | +2 | +0 | +1 | ||||||
| 8 | Grito da Trypanosoma | 5 (917) | 19 | +3 | +0 | +0 | +4 | -3 | +2 | |||||
| 9 | Convex Null | 4 (437) | 17 | -1 | +0 | +0 | +1 | +0 | ||||||
| 10 | Unicamp Alpha | 4 (455) | 15 | +0 | +1 | +1 | -4 | -4 | +1 | -1 | ||||
| 11 | AUHAUAH Balões Mano | 4 (473) | 13 | +0 | +0 | -2 | +0 | +2 | ||||||
| 12 | Razao Cruzada | 4 (640) | 11 | +2 | +2 | +1 | +0 | |||||||
| 13 | Estação PrIMEira da XurupITA | 3 (286) | 9 | +2 | +1 | -5 | +0 | |||||||
| 14 | RGA | 3 (412) | 7 | -4 | +1 | -1 | +3 | +0 | ||||||
| 15 | ACM-1PT | 2 (298) | 5 | +2 | +0 | |||||||||
| 16 | dalhebugre | 1 (76) | 3 | -6 | +1 | |||||||||
| 17 | Senta A Pua! | 1 (273) | 1 | -1 | +3 | -1 | </div> |
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
#define MAX 1000001
int v[MAX];
int testa(int N) {
for(int i = 2; i < N; i++) {
int at = v[i];
if(at < v[i+1] && at > v[i-1]) return 0;
if(at > v[i+1] && at < v[i-1]) return 0;
}
int opa[MAX];
memset(opa, 0, sizeof(opa));
int at = 1;
int cnt = 0;
while(!opa[at]) {
opa[at] = 1;
cnt++;
at = v[at];
}
if(cnt < N) return 0;
return 1;
}
void roda(int N) {
int M = (N+1) / 2;
vector<int> impar_cima, impar_baixo, par_cima, par_baixo;
for(int i = 5; i <= M; i += 2) {
impar_baixo.push_back(i);
}
for(int i = 4; i <= M; i += 2) {
par_baixo.push_back(i);
}
for(int i = M+1; i <= N; i++) {
if(i <= 3) continue;
if(i&1) impar_cima.push_back(i);
else par_cima.push_back(i);
}
v[3] = 1;
int at = 1;
for(vector<int>::iterator it = impar_baixo.begin(); it != impar_baixo.end(); it++) {
v[at] = *it;
at = *it;
}
v[at] = 2;
at = 2;
for(vector<int>::iterator it = par_cima.begin(); it != par_cima.end(); it++) {
// printf("COLOCA %d em %d\n", *it, at);
v[at] = *it;
at = *it;
}
reverse(impar_cima.begin(), impar_cima.end());
reverse(par_baixo.begin(), par_baixo.end());
while(impar_cima.size() + par_baixo.size()) {
int last = impar_cima[ impar_cima.size() - 1 ];
v[at] = last;
// printf("%d em %d, xx\n", last, at);
at = last;
impar_cima.pop_back();
if(par_baixo.empty()) break;
last = par_baixo[ par_baixo.size() - 1 ];
v[at] = last;
// printf("%d em %d, x\n", last, at);
at = last;
par_baixo.pop_back();
}
// printf("FIM em %d\n", at);
v[at] = 3;
printf("%d", v[1]);
for(int i = 2; i <= N; i++) {
printf(" %d", v[i]);
}
printf("\n");
}
int main() {
int N;
while(scanf("%d", &N) == 1 && N) {
roda(N);
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
using namespace std;
#define INF 0x3f3f3f3f
long long table[20][1024], table_nlz[20][1024];
int main() {
int t;
memset(table[0],0,sizeof(table[0]));
memset(table_nlz[0],0,sizeof(table_nlz[0]));
table[0][0] = table_nlz[0][0] = 1;
for (int i=1; i < 20; i++) {
for (int mask=1023; mask >= 0; mask--) {
table[i][mask] = 0;
table_nlz[i][mask] = 0;
for (int k=0; k < 10; k++) {
table[i][mask] += table[i-1][mask^(1<<k)];
table_nlz[i][mask] += table_nlz[i-1][mask^(1<<k)];
}
}
table_nlz[1][1] = 0;
}
cin >> t;
while (t--) {
long long n;
int len;
cin >> n;
for (len=2; n-table_nlz[len][0] > 0; len+=2) {
n -= table_nlz[len][0];
}
string ans = "";
int mask = 0;
for (int i=0; i < len; i++) {
int k;
for (k=!i; n-table[len-i-1][mask^(1<<k)] > 0; k++) {
n -= table[len-i-1][mask^(1<<k)];
}
ans += (char)(k + '0');
mask ^= 1 << k;
}
cout << ans << endl;
}
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
using namespace std;
#define SMAX 1048576
typedef long long lld;
char st[SMAX];
lld m, n;
lld strtonumber(char *s) {
int sz = strlen(s);
lld row = 0, col = 0;
for (int i = 0; i < sz; i++) {
if ('A' <= s[i] && s[i] <= 'Z') {
col*= 26;
col+= s[i] - 'A' + 1;
} else {
row*= 10;
row+= s[i] - '0';
}
}
return (row - 1ll) * n + col;
}
string numbertostr(lld x) {
x--;
lld row = x / n;
lld col = x % n;
string s = "";
s = 'A' + (col % 26);
col/= 26;
while (col > 0) {
s+= 'A' + ((col - 1) % 26);
col--;
col/= 26;
}
reverse(s.begin(), s.end());
char t[64];
sprintf(t, "%lld", row+1);
s+= t;
return s;
}
int main() {
scanf("%lld %lld", &m, &n);
int tests;
scanf("%d", &tests);
while (tests--) {
scanf("%s", st);
if ('A' <= st[0] && st[0] <= 'Z') {
printf("%lld\n", strtonumber(st));
} else {
printf("%s\n", numbertostr(atoll(st)).c_str());
}
}
return 0;
}
#include<cstdio>
#include<cstring>
#define MAX 256
char v[MAX];
int pdset[MAX][MAX];
int pdlist[MAX][MAX];
int set(int a,int b);
int atom(int a) {
return v[a] == '{' || v[a] == '}' || v[a] == ',';
}
int element(int a,int b) {
if(a+1 == b && atom(a)) {
return 1;
}
return set(a,b);
}
int list(int a,int b) {
if(pdlist[a][b] != -1) return pdlist[a][b];
if(element(a,b)) return 1;
for(int i = a;i < b; i++) {
if(v[i] == ',') {
if(element(a,i) && list(i+1, b)) {
return pdlist[a][b] = 1;
}
}
}
return pdlist[a][b] = 0;
}
int element_list(int a,int b) {
if(a >= b) return 1;
return list(a,b);
}
int set(int a,int b) {
if(a + 1 >= b) return 0;
if(pdset[a][b] != -1) return pdset[a][b];
if(v[a] == '{' && v[b-1] == '}' && element_list(a+1, b-1)) {
return pdset[a][b] = 1;
} else {
return pdset[a][b] = 0;
}
}
int main() {
int T;
scanf("%d", &T);
for(int i = 0;i < T;i++) {
scanf("%s", v);
printf("Word #%d: ", i+1);
memset(pdset, -1, sizeof(pdset));
memset(pdlist, -1, sizeof(pdlist));
if(set(0, strlen(v))) {
printf("Set\n");
} else {
printf("No Set\n");
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <vector>
#include <string>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <numeric>
using namespace std;
inline int cmp(double a, double b, double eps = 1e-09){
return a + eps < b ? -1 : a - eps > b ? 1 : 0;
}
struct point{
double x, y;
point(double a = 0, double b = 0): x(a), y(b){}
point rotate(double angle){
double c = cos(angle), s = sin(angle);
return point(x * c - y * s, x * s + y * c);
}
point operator *(double k){return point(x * k, y * k);}
point operator /(double k){return point(x / k, y / k);}
point operator -(const point& q){return point(x - q.x, y - q.y);}
inline double mod(){return hypot(x, y);}
double angle(){return atan2(x, y);}
};
point cent[2000], tangp[3000];
vector<pair<double, double> > part[2000];
double rad[2000];
double pi = acos(-1);
vector<pair<double, double> > parte(point& a, point& b){
double t1 = a.angle(), t2 = b.angle();
vector<pair<double, double> > res;
//cout << t1 << " " << t2 << endl;
if(t2 < 0 && t1 > 0) res.push_back(make_pair(-pi, t2)), res.push_back(make_pair(t1, pi));
else res.push_back(make_pair(t1, t2));
/*if(t1 < 0) t1 += 2 * pi;
if(t2 < 0) t2 += 2 * pi;
if(t1 > t2) swap(t1, t2);
if(t2 - t1 > pi) res.push_back(make_pair(t2, 2 * pi)), res.push_back(make_pair(0, t1));
else res.push_back(make_pair(t1, t2));
*/return res;
}
bool used[2000];
bool can[2000];
pair<double, double> final[3000];
struct tri{
double first, second; int who;
tri(double x = 0, double y = 0, int i = 0): first(x), second(y), who(i){}
bool operator <(const tri& B) const{
if(first != B.first) return first < B.first;
return second < B.second;
}
};
tri angulos[3000];
int main(){
int n;
while(scanf("%d", &n) && n){
for(int i = 0; i < n; i++) scanf("%lf %lf %lf", ¢[i].x,¢[i].y, &rad[i]);
double best = 0;
int sz = 0;
for(int i = 0; i < n; i++){
point u = cent[i];
double a = sqrt(u.x*u.x + u.y*u.y - rad[i] * rad[i]);
double theta = acos(a / u.mod());
point p = u.rotate(theta) / u.mod() * a;
point q = u.rotate(-theta) / u.mod() * a;
tangp[i * 2] = p;
tangp[i * 2 + 1] = q;
part[i] = parte(p, q);
for(int j = 0; j < part[i].size(); j++) angulos[sz++] = tri(part[i][j].first, part[i][j].second, i);
}
sort(angulos, angulos + sz);
for(int pivot = 0; pivot < n; pivot++){
double enclose = tangp[2 * pivot].mod();
can[pivot] = false;
for(int i = 0; i < n; i++) if(pivot != i)
if(cmp(tangp[i * 2].mod(), enclose) <= 0 || cmp(tangp[i * 2 + 1].mod(), enclose) <= 0)
can[i] = true;
else can[i] = false;
memset(used, 0, sizeof used);
int len = 0;
for(int i = 0; i < sz; i++) if(!used[i] && can[angulos[i].who]){
double le = angulos[i].first, ri = angulos[i].second;
for(int j = i; j < sz; j++)
if(cmp(angulos[j].first, ri) <= 0 && can[angulos[j].who]) ri = max(ri, angulos[j].second), used[j] = true;
else if(can[angulos[j].who]) break;
final[len++] = make_pair(le, ri);
}
vector<pair<double, double> > segs = part[pivot];
bool sirve = false;
for(int i = 0; i < segs.size(); i++){
bool contenido = false;
for(int j = 0; j < len; j++) if(cmp(final[j].first, segs[i].first) <= 0 && cmp(final[j].second, segs[i].second) >= 0) contenido = true;
if(!contenido) sirve = true;
}
if(sirve) best = max(best, cent[pivot].mod() - rad[pivot]);
}
printf("%.03f\n", best);
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, M;
int v[128];
int p[128], id[128], ja[128];
int main() {
n = 0;
int aux;
while(scanf("%d", &aux) == 1) {
v[n++] = aux;
}
int nn = n/2;
M = v[0];
for(int i = 0; i < nn; i++) {
p[i] = v[i];
M = min(M, v[i]);
}
for(int i = nn; i < n; i++) {
id[i-nn] = v[i];
}
n = nn;
int r = 0;
memset(ja, 0, sizeof(ja));
for(int i = 0; i < n; i++) {
if(!ja[i]) {
int soma = 0, menor = p[i], at = i, t =0;
while(!ja[at]) {
ja[at] = 1;
t++;
soma += p[at];
menor = min(menor, p[at]);
at = id[at];
}
int s = soma, m = menor;
int a = s - m + (t-1)*m;
int b = (s-m) + 2*(m+M) + (t-1)*M;
r += min(a,b);
}
}
printf("%d\n", r);
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <cmath>
using namespace std;
int T;
int X,Y,M;
int cmp(double a, double b) {
if(fabs(a-b)<=1e-8)
return 0;
if(a<b)
return -1;
return 1;
}
struct point {
double x,y;
point() {}
point(double a, double b) : x(a), y(b) {}
point operator+(const point& a) const {
return point(x+a.x,y+a.y);
}
point operator-(const point& a) const {
return point(x-a.x,y-a.y);
}
point operator/(double a) const {
return point(x/a,y/a);
}
};
double sqrdist(const point& a, const point &b) {
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
struct line {
double a,b,c;
line() {}
line(const point& a1,const point& a2) {
a=a1.y-a2.y;
b=a2.x-a1.x;
c=a1.x*a2.y-a2.x*a1.y;
}
line(double a, double b, double c) : a(a), b(b), c(c) {}
line(double ang) : a(-ang), b(1.0), c(0.0) { }
line passa_por(const point& p) const {
return line(a,b,-a*p.x-b*p.y);
}
line ortogonal() const {
return line(-b,a,c);
}
bool paralela(const line& l) const {
return cmp((-a*l.b),(-l.a*b))==0;
}
};
point intersection(const line& l, const line& l2) {
return point((l.b*l2.c-l.c*l2.b)/(l.a*l2.b-l2.a*l.b),(-l.a*l2.c+l.c*l2.a)/(l.a*l2.b-l2.a*l.b));;
}
point pontos[2000];
point polygon[2000];
int npolygon;
point polaux[2000];
int npolaux;
int main(void) {
scanf("%d",&T);
while(T--) {
scanf("%d %d %d",&X,&Y,&M);
for(int i=0;i<M;i++)
scanf("%lf %lf",&pontos[i].x,&pontos[i].y);
double ansd=-1;
point ans;
for(int i=0;i<M;i++) {
npolygon=4;
polygon[0]=point(0,0);
polygon[1]=point(0,Y);
polygon[2]=point(X,Y);
polygon[3]=point(X,0);
for(int j=0;j<M;j++) if(pontos[i].x!=pontos[j].x or pontos[i].y!=pontos[j].y) {
line biseccao = line(pontos[i],pontos[j]).ortogonal().passa_por((pontos[i]+pontos[j])/2.0);
int inter[8];
int ninter=0;
for(int k=0;k<npolygon;k++) {
int l=(k+1)%npolygon;
double l1=biseccao.a*polygon[k].x + biseccao.b*polygon[k].y + biseccao.c;
double l2=biseccao.a*polygon[l].x + biseccao.b*polygon[l].y + biseccao.c;
//considera que a ponta do comeco intersecta e a ponta do final nao intersecta
if( (cmp(l1,0.0)<=0 and cmp(l2,0.0)>0) or (cmp(l1,0.0)>=0 and cmp(l2,0.0)<0) ) {
inter[ninter++]=k;
}
}
assert(ninter<=2);
if(ninter==2) {
double lp=biseccao.a*pontos[i].x + biseccao.b*pontos[i].y + biseccao.c;
double lpol=biseccao.a*polygon[(inter[0]+1)%npolygon].x + biseccao.b*polygon[(inter[0]+1)%npolygon].y + biseccao.c;
//verifica se a ordem do loop precisa ser trocada
if( (cmp(lp,0)<0 and cmp(lpol,0)>0) or (cmp(lp,0)>0 and cmp(lpol,0)<0) )
swap(inter[0],inter[1]);
npolaux=0;
polaux[npolaux++]=intersection(biseccao,line(polygon[inter[0]],polygon[(inter[0]+1)%npolygon]));
for(int k=(inter[0]+1)%npolygon;k!=inter[1];k=(k+1)%npolygon) {
polaux[npolaux++]=polygon[k];
}
polaux[npolaux++]=polygon[inter[1]];
polaux[npolaux++]=intersection(biseccao,line(polygon[inter[1]],polygon[(inter[1]+1)%npolygon]));
//se os 2 ultimos pontos coincidirem
if(cmp(polaux[npolaux-1].x,polaux[npolaux-2].x)==0 and cmp(polaux[npolaux-1].y,polaux[npolaux-2].y)==0)
npolaux--;
memcpy(polygon,polaux,sizeof(polygon[0])*npolaux);
npolygon=npolaux;
}
}
for(int j=0;j<npolygon;j++)
if(sqrdist(pontos[i],polygon[j]) > ansd) {
ansd=sqrdist(pontos[i],polygon[j]);
ans=polygon[j];
}
}
printf("The safest point is (%.1lf, %.1lf).\n",ans.x,ans.y);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#define sz 601
#define bsz 32
#define mod 10000
using namespace std;
struct bigint {
int v[bsz];
bigint operator + (const bigint &b) const {
bigint p;
for (int i = 0; i < bsz; i++) {
p.v[i] = v[i] + b.v[i];
}
for (int i = 0; i+1 < bsz; i++) {
if (p.v[i] > mod) {
p.v[i+1]+= p.v[i] / mod;
p.v[i]%= mod;
}
}
if (p.v[bsz - 1] >= mod) {
printf("estoura\n");
exit(1);
}
return p;
}
bool operator < (const bigint &b) const {
for (int i = bsz - 1; i >= 0; i--) {
if (v[i] < b.v[i]) {
return 1;
} else if (v[i] > b.v[i]) {
return 0;
}
}
return 0;
}
};
bool is_zero(bigint b) {
for (int i = 0; i < bsz; i++) {
if (b.v[i] != 0) {
return 0;
}
}
return 1;
}
bigint *P, *Q;
int main() {
int n;
scanf("%d", &n);
P = (bigint *) malloc(sizeof(bigint) * sz);
Q = (bigint *) malloc(sizeof(bigint) * sz);
memset(P, 0, sizeof(bigint) * sz);
P[0].v[0] = 1;
for (int i = 1; i <= n; i++) {
memset(Q, 0, sizeof(bigint) * sz);
for (int j = 0; j < sz; j++) {
for (int k = 1; j+k < sz && k <= 6; k++) {
Q[j+k] = Q[j+k] + P[j];
}
}
swap(P, Q);
}
map < bigint, vector<int> > M;
for (int i = 0; i < sz; i++) {
if (!is_zero(P[i])) {
M[P[i]].push_back(i);
}
}
for (map< bigint, vector<int> >::reverse_iterator it = M.rbegin(); it != M.rend(); it++) {
for (int j = 0; j < it->second.size(); j++) {
printf("%d\n", it->second[j]);
}
}
return 0;
}
#include<cstdio>
#include<cstring>
int main() {
int casos;
scanf("%d", &casos);
while(casos--) {
int n;
scanf("%d", &n);
int x = 0;
int sohum = 1;
for(int i =0 ; i < n; i++) {
int aux;
scanf("%d", &aux);
if(aux != 1) sohum = 0;
x ^= aux;
}
if(sohum) {
x ^= 1;
}
if(!x) {
printf("Alla\n");
} else {
printf("Haluc\n");
}
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 64
#define inf (1<<30)
int N;
int X[MAX];
int Y[MAX];
int pd[MAX][MAX];
int left(int p, int a, int b) {
return (X[a] - X[p]) * (Y[b] - Y[p]) - (Y[a] - Y[p]) * (X[b] - X[p]);
}
int f(int a,int b) {
if(b - a < 2) return 0;
if(pd[a][b] != -1) return pd[a][b];
int otimo = inf;
for(int x = a+1; x < b; x++) {
int l = left(b,a,x);
if(l > 0) {
int M = max(f(a, x), f(x, b));
otimo = min(otimo, max(M, left(b, a, x)));
}
}
return pd[a][b] = otimo;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d", &N);
long long a = 0;
for(int i = 0;i < N; i++) {
scanf("%d %d", X + i, Y + i);
}
for(int i = 0 ; i < N; i++) {
a += left(0, i, (i+1)%N);
}
if(a < 0) {
reverse(X, X+N);
reverse(Y, Y+N);
}
memset(pd,-1,sizeof(pd));
printf("%.1f\n", f(0, N-1)/2.0);
}
return 0;
}