algospot.com :: ACM ICPC - 10월 20일 연습 best submission

ACM ICPC (International Collegiate Programming Contest) 는 세계 최대의 컴퓨터 학회인 ACM 에서 매년 대학생 대상으로 주최하는 프로그래밍 대회입니다.

10월 20일 연습 best submission

리베

2007.10.22 17:25:32

1135

http://algospot.com/zbxe/2445

주최자의 주관적인 기준으로 선발한 best submission

A. Hanafuda Shuffle - by zizavino

#include <cstdio>

using namespace std;

int data[50];
int temp[50];
int i, j, n, r, p, c;

int main() {
    while(true) {
        scanf("%d %d", &n, &r);
        if(n == 0) break;

        for(i = 0; i < 50; ++ i) {
            data[i] = n - i;
        }

        for(i = 0; i < r; ++ i) {
            scanf("%d %d", &p, &c);
            -- p;

            for(j = 0; j < c; ++ j) {
                temp[j] = data[p + j];
            }

            for(j = p - 1; j > -1; -- j) {
                data[j + c] = data[j];
            }

            for(j = 0; j < c; ++ j) {
                data[j] = temp[j];
            }
        }

        printf("%d\n", data[0]);
    }

    return 0;
}

B. Red and Black - by undergirls

#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
#include <utility>

using namespace std;

const int inf = 987654321;
const double eps = 1e-10;
const double pi = acos(-1.0);

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;

#define ITERLOOP(i,x) for(i=x.begin();i!=x.end();i++)

#define GETI(x) scanf("%d",&x)
#define PUTI(x) printf("%d\n",(x))
#define clr(x,v) memset(x,(v),sizeof(x))
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define sz size()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define REP(i,n) FOR(i,0,n)
#define REPD(i,n) FORD(i,n,0)
#define EXIST(s,x) (s.find(all(s),x)!=s.end())

template<typename T> string tostr(T x) { ostringstream ret; ret << x; return ret.str(); }
template<typename T> void setMax(T &a, T b) { if(a<b) a = b; }
template<typename T> void setMin(T &a, T b) { if(a>b) a = b; }

int N, M;
int sy, sx;
int cnt;
string map[30];

void solve(int r, int c) {
    if(r<0||r>=N) return;
    if(c<0||c>=M) return;
    if(map[r][c]!='.'&&map[r][c]!='@') return;
    ++cnt;
    map[r][c] = '!';
    solve(r+1,c);
    solve(r-1,c);
    solve(r,c-1);
    solve(r,c+1);
}
int main() {
    while(cin>>M>>N) {
        if(!M&&!N) break;
        REP(i,N) cin >> map[i];
        REP(i,N) REP(j,M) if(map[i][j]=='@') { sy = i; sx = j; }
        cnt = 0;
        solve(sy,sx);
        cout << cnt << endl;
    }
}

C. Unit Fraction Partition - by Ainu7

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

int p, q, a, n;
int cnt = 0;

void search(int mult, int up, int now, int starter, int last)
{
    int i;

    if (up*q == p*mult) cnt ++;
    if (up*q > p*mult) return;
    if ( now >= n ) return;
    if ((up+last*(n-now))*q < p*mult ) return;
    int limit = a / mult;
    for (i=starter; i<=limit; i++)
    {
        search(mult*i, up*i+mult, now+1, i, mult);
    }
    return;
}

int main()
{
    while (!feof(stdin))
    {
        // max answer = 103
        scanf("%d %d %d %d", &p, &q, &a, &n);
//        p=10; q=1; a = 12000; n= 7;
        if (p+q+a+n==0 || a==0 || n==0 || p==0 || q==0) break;
        if ( p<0 || q<0 || a<0 || a>12000 || n<0 || n>7 ) break;
        cnt = 0;
        search(1, 0, 0, 1, 1);
        printf("%d\n", cnt);
    }
    return 0;
}

D. Circle and Point - by fireduck
* 대회 도중에는 풀리지 않았던 문제인데 fireduck님께서 후에 AC를 받으셔서 첨부합니다 :)

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <ctime>

using namespace std;

#define MAXN 302
#define EPS 0.000000001

struct P
{
    double x, y;
};

bool operator < (const P& a, const P& b)
{
    return (a.x < b.x);
}

int answer;
int n;
P a[MAXN];

inline double dist2(const P& a, const P& b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy;
}

void update(const P& o, int ia, int ib)
{
    int count = 2;
    for (int i = ia - 1; i >= 0; i--)
    {
        if (o.x - a[i].x > 1.0 + EPS) break;
        if (dist2(o, a[i]) <= 1.0 + EPS)
        {
            count++;
        }
    }
    for (int i = ia + 1; i < ib; i++)
    {
        if (dist2(o, a[i]) <= 1.0 + EPS)
        {
            count++;
        }
    }
    for (int i = ib + 1; i < n; i++)
    {
        if (a[i].x  - o.x > 1.0 + EPS) break;
        if (dist2(o, a[i]) <= 1.0 + EPS)
        {
            count++;
        }
    }

    if (count > answer)
    {
        answer = count;
    }
}

void check(int i, int j)
{
    P& pa = a[i];
    P& pb = a[j];
    if (dist2(pa, pb) > 4.0) return; 
    P m, o;
    m.x = (pa.x + pb.x) / 2.0;
    m.y = (pa.y + pb.y) / 2.0;
    double len1 = sqrt(1.0 - dist2(m, pa));
    double dx = pa.x - pb.x, dy = pa.y - pb.y;
    double len2 = sqrt(dx * dx + dy * dy);
    double ratio = len1 / len2;

    o.x = m.x + dy * ratio;
    o.y = m.y - dx * ratio;
    // printf("%.8lf %.8lf\n", dist2(o, pa), dist2(o, pb));
    update(o, i, j);
    o.x = m.x - dy * ratio;
    o.y = m.y + dx * ratio;
    // printf("%.8lf %.8lf\n", dist2(o, pa), dist2(o, pb));
    update(o, i, j);
}

void process()
{
    answer = 1;
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            check(i, j);
        }
    } 
} 

int main()
{
    // double t = clock();
    while(1)
    {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 0; i < n; i++)
        {
            scanf("%lf %lf", &(a[i].x), &(a[i].y));
        }
        answer = 1;
        process();
        cout << answer << endl;
    }
    // printf("%.4lf\n", (clock() - t) / 1000.0);
}

E. Name the Crossing - by normit

#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <queue>

#define REP(i,n) for(int i=0; i < (n); ++i)
#define mp make_pair
#define pb push_back
#define sz size()

using namespace std;

typedef vector<int> vi;
typedef long long ll;

int n,m;

void solve()
{
    char buf[40];
    int edge[201][201] = {0, };
    map<string,int> dic;
    vector<int> links[201];

    int diccount = 0;
    REP(i,n) {
        int strong,weak;
        scanf("%s",buf);
        for(int j=0; buf[j] != 0; ++j) {
            if(buf[j] != '-') continue;
            buf[j] = 0;
            strong = dic[buf];
            if(strong == 0) { strong = dic[buf] = ++diccount; }
            weak = dic[buf+j+1];
            if(weak == 0) { weak = dic[buf+j+1] = ++diccount; }
            edge[strong][weak] = 1;
            edge[weak][strong] = -1;
            links[strong].pb(weak);
            break;
        }
    }
    for(int i=1; i < diccount; ++i) {
        for(int j=i+1; j <= diccount; ++j) {
            if(edge[i][j] != 0) continue;
            for(int k=1; k <= diccount; ++k) {
                if(i == k || j == k) continue;
                if(edge[i][k] == edge[k][j] && (edge[i][k] == 1 || edge[i][k] == -1)) {
                    edge[i][j] = 4;
                    edge[j][i] = 4;
                    break;
                }
                if(edge[i][j] == 2) continue;    
                if(edge[i][k] == edge[j][k] && (edge[i][k] == 1 || edge[i][k] == -1)) {
                    edge[i][j] = edge[j][i] = 2;
                    links[i].pb(j);
                    links[j].pb(i); 
                    continue;
                }
            }
        }
    }
    printf("%d\n",diccount);
    scanf("%d",&m);
    REP(i,m) {
        int strong,weak;
        scanf("%s",buf);
        for(int j=0; buf[j] != 0; ++j) {
            if(buf[j] != '-') continue;
            buf[j] = 0;
            strong = dic[buf];
            weak = dic[buf+j+1];
            break;
        }
        if(strong == 0 || weak == 0) {
            printf("NO\n"); continue; }

        int cnt = 0;
        bool visited[201] = {false,};
        queue<pair<int, int> > q;
        q.push(mp(strong,0));
        while(!q.empty() && !cnt) {
            pair<int,int> t = q.front();
            q.pop();
            REP(j, links[t.first].sz) {
                int next = links[t.first][j];
                if(visited[next] || edge[t.first][next] > 2) continue;
                visited[next] = true;
                if(next == weak) {
                    cnt = edge[t.first][next]+t.second;
                    break;
                }
                q.push(mp(next,t.second+edge[t.first][next]));
            }
        }
        if(cnt % 2 == 0) printf("NO\n");
        else printf("YES\n");
    }
}

int main()
{
    while(scanf("%d",&n) == 1) {
        if(0 == n) break;
        solve();
    }
    return 0;
}

F. playground - by zizavino

#include <cstdio>
#include <algorithm>

using namespace std;

int n, i;
double data[20];
double sum;

int main() {
    while(true) {
        scanf("%d", &n);
        if(n == 0) break;

        for(i = 0; i < n; ++ i) {
            scanf("%lf", &data[i]);
        }

        sort(data, data + n);

        for(sum = 0.0, i = 1; i < n; ++ i) {
            sum += data[i - 1];

            if(sum >= data[i]) {
                break;
            }
        }

        if(i == n) {
            printf("NO\n");
        }
        else {
            printf("YES\n");
        }
    }

    return 0;
}

G. The Embarassed Cryptographer - by Astein

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

using namespace std;

int pprime[1000001];
vector<int> prime;

int main() {
    long long a[10];
    int l;
    
    for (int i = 2; i <= 1000; i++) {
        if (pprime[i] == 0) {
            prime.push_back(i);
            for (int j = i * i; j <= 1000000; j += i)
                pprime[j] = 1;
        }
    }
    for (int i = 1001; i <= 1000000; i++) 
        if (pprime[i] == 0) prime.push_back(i);

    string s;
    while (true) {
        cin >> s >> l;
        if (s == "0" && l == 0) break;
        bool sw = false;

        s = string(12 - (s.size() % 12), '0') + s;
        
        vector <long long> aa;
        for (int i = 0; i < s.size(); i += 12) {
            long long tmp;
            sscanf(s.substr(i, 12).c_str(), "%I64d", &tmp);
            aa.push_back(tmp);
        }
        for (int i = 0; i < prime.size(); i++) {
            if (prime[i] >= l) break;
            long long num = 0;
            for (int j = 0; j < aa.size(); j++) {
                num = num * 1000000000000LL + aa[j];
                num %= prime[i];
            }
            if (num == 0) {
                printf("BAD %d\n", prime[i]);
                sw = true;
                break;
            }
        }
        if (!sw) printf("GOOD\n");
    }
}

H. Crashing Robots - by normit

#include <stdio.h>
#include <vector>

#define REP(i,n) for(int i=0; i < (n); ++i)
#define mp make_pair
#define pb push-back

using namespace std;

typedef vector<int> vi;
typedef long long ll;

// W, S, E, N
int dirx[4] = {-1,0,1,0};
int diry[4] = {0,-1,0,1};

void solve()
{
    int a,b;
    int n,m;
    int map[101][101] = {0, };
    int robots[101][3] = {0, };
    scanf("%d %d",&a,&b);
    scanf("%d %d",&n,&m);
    REP(i,n) {
        int x,y;
        char d;
        scanf("%d %d %c",&x,&y,&d);
        map[y][x] = i+1;
        robots[i][0] = y;
        robots[i][1] = x;
        switch(d) {
            case 'N':
                robots[i][2] = 3;
                break;
            case 'W':
                robots[i][2] = 0;
                break;
            case 'S':
                robots[i][2] = 1;
                break;
            case 'E':
                robots[i][2] = 2;
                break;
        }
    }
    bool crashed = false;
    REP(i,m) {
        int j,r;
        char act;
        REP(ii,b+1) {
            REP(jj,a+1) {
//                printf("%d ",map[ii][jj]);
            }
//            printf("\n");
        }

        scanf("%d %c %d",&j,&act,&r);
        if(crashed) continue;
        if(act == 'L') { r %= 4; robots[j-1][2] = (robots[j-1][2] + r) % 4; }
        else if(act == 'R') { r %= 4; robots[j-1][2] = (robots[j-1][2] - r + 4) % 4; }
        else if(act == 'F') {
            REP(k,r) {
                int ny = robots[j-1][0]+diry[robots[j-1][2]]*(k+1);
                int nx = robots[j-1][1]+dirx[robots[j-1][2]]*(k+1);
//                printf("%d %d\n",ny,nx);
                if(nx <= 0 || ny <= 0 || nx > a || ny > b) {
                    printf("Robot %d crashes into the wall\n",j);
                    crashed = true;
                    break;
                }
                if(map[ny][nx] != 0) {
                    printf("Robot %d crashes into robot %d\n",j,map[ny][nx]);
                    crashed = true;
                    break;
                }
            }
            if(crashed) continue;
            int ny = robots[j-1][0]+diry[robots[j-1][2]]*r;
            int nx = robots[j-1][1]+dirx[robots[j-1][2]]*r;        
            map[ny][nx] = j;
            map[robots[j-1][0]][robots[j-1][1]] = 0;
            robots[j-1][0] = ny;
            robots[j-1][1] = nx;
        }
    }
    if(crashed) return;
    printf("OK\n");
}

int main()
{
    int kase;
    scanf("%d",&kase);
    REP(i,kase) solve();
    return 0;
}

이 게시물을..