The 2013 ACM-ICPC Asia Changsha Regional Contest(2013地域戦練習)
4638 ワード
リンク:http://acm.zju.edu.cn/onlinejudge/showProblems.do?contestId=1&pageNumber=28
試合はA,C,G,H,J,Kを過ぎた.
A,J,Kは小さい仲间に秒されて、K题の比较的に面倒な捜索
H問題は2点でよい,層数がFであることに注意する
C問題の幾何学の問題、私のAので、WAは2発、もとは1種の情況が少なくなって、またチームメートに検査を手伝ってもらって、本心は弱くて、高校は直角三角形の問題を解きます
G題はまずhavelアルゴリズムで1つの解を構築し,次に4つの異なる点i,j,k,uを列挙し,を満たす辺にが存在しないことを列挙し,を辺に置き換えると別の組の解が現れ,試合の時にランダム数でhavelを何度も繰り返した.
D,I問題はできるようだ.
C,Gのコードを貼ってください
C
試合はA,C,G,H,J,Kを過ぎた.
A,J,Kは小さい仲间に秒されて、K题の比较的に面倒な捜索
H問題は2点でよい,層数がFであることに注意する
C問題の幾何学の問題、私のAので、WAは2発、もとは1種の情況が少なくなって、またチームメートに検査を手伝ってもらって、本心は弱くて、高校は直角三角形の問題を解きます
G題はまずhavelアルゴリズムで1つの解を構築し,次に4つの異なる点i,j,k,uを列挙し,
D,I問題はできるようだ.
C,Gのコードを貼ってください
C
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const double eps = 1e-8;
struct Point {
double x, y;
Point(double x, double y):
x(x), y(y){}
Point(){}
double len() {
return sqrt(x*x+y*y);
}
Point operator+(const Point t) {
return Point(x+t.x, y+t.y);
}
Point operator-(const Point t) {
return Point (x-t.x, y-t.y);
}
Point operator*(const double t) {
return Point(x*t, y*t);
}
Point operator/(const double t) {
return Point(x/t, y/t);
}
void in() {
scanf("%lf%lf", &x, &y);
}
}o, v, tp;
double cross(Point a, Point b) {
return a.x*b.y-a.y*b.x;
}
double dot(Point a, Point b) {
return a.x*b.x+a.y*b.y;
}
double r1, r2, r3;
int main() {
int i, j;
while( ~scanf("%lf%lf%lf", &r1, &r2, &r3)) {
o.in(); v.in();
double d = fabs(cross(v, o))/v.len();
if(dot(v*(-1), o) < eps ||d-r2-r3 > eps) {
printf("%.6f
", 0.0);
continue;
}
if(d-r1-r3 > eps) {
double d1 = r2+r3;
double sum = sqrt(d1*d1-d*d);
printf("%.6f
", sum*2/v.len());
continue;
}
double d1 = r2+r3, d2 = r1+r3;
double sum = sqrt(d1*d1-d*d)-sqrt(d2*d2-d*d);
printf("%.6f
", sum*2/v.len());
}
return 0;
}
/*
5 20 1 0 100 0 -1
5 20 1 30 15 -1 0
1 2 2 10 0 0 10
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
struct node {
int d, v;
bool operator<(const node &t) const {
return d > t.d || (d==t.d && v > t.v);
}
node(int d, int v) :
d(d), v(v) {
}
node() {
}
} p[104];
int d[104];
bool g[104][104];
int n;
bool havel() {
int i, j;
for(i = 1; i <= n; i++)
p[i] = node(d[i], i);
for(i = 1; i <= n; i++) {
sort(p + i, p + n + 1);
j = i + 1;
while(p[i].d > 0 && j <= n) {
if(p[j].d > 0&&p[i].d>0) {
int u=p[i].v;
int v=p[j].v;
g[u][v] = g[v][u] = true;
p[i].d--;
p[j].d--;
j++;
}
else return 0;
}
if(p[i].d > 0) return 0;
}
return 1;
}
int sum;
void out(bool g[][104]) {
vector<pair<int, int> > v;
int i, j;
for(i = 1 ;i <= n; i++)
for(j = i+1; j <= n; j++) if(g[i][j])
v.push_back(make_pair(i, j));
printf("%d %d
", n, sum);
for(i = 0; i < v.size(); i++) {
if(i) printf(" ");
printf("%d", v[i].first);
}
puts("");
for(i = 0; i < v.size(); i++) {
if(i) printf(" ");
printf("%d", v[i].second);
}
puts("");
}
int main() {
int i, j, k, u;
while(~scanf("%d", &n)) {
sum = 0;
for(i = 1; i <= n; i++) {
scanf("%d", &d[i]);
sum += d[i];
}
sum>>=1;
memset(g, false, sizeof(g));
bool flag = havel();
if(!flag) {
puts("IMPOSSIBLE");
continue;
}
int ii = -1, jj, kk, uu;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++) if(g[i][j] && i != j)
for(k = 1; k <= n; k++) if(!g[j][k] && k != i && k != j)
for(u = 1; u <= n; u++) if(!g[i][u] && g[k][u] && u != i && u != j && u != k) {
ii = i, jj = j, kk = k, uu = u;
}
if(ii == -1) {
puts("UNIQUE");
out(g);
continue;
}
else {
puts("MULTIPLE");
out(g);
//cerr << ii <<" " << jj << " " << kk << " "<< uu << "~~~~" << endl;
g[ii][jj] = g[jj][ii] = false;
g[kk][uu] = g[uu][kk] = false;
g[ii][uu] = g[uu][ii] = true;
g[jj][kk] = g[kk][jj] = true;
out(g);
}
}
return 0;
}