[editorial] 10월 20일 연습 best submission

  • User Avatar
    hyunhwan

    주최자의 주관적인 기준으로 선발한 best submission
    A. Hanafuda Shuffle - by zizavino
    [code c++]
    #include
    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;
    }
    [/code]
    B. Red and Black - by undergirls
    [code c++]
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    const int inf = 987654321;
    const double eps = 1e-10;
    const double pi = acos(-1.0);
    typedef long long ll;
    typedef pair ii;
    typedef vector 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 string tostr(T x) { ostringstream ret; ret << x; return ret.str(); }
    template void setMax(T &a, T b) { if(a template 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;
    }
    }
    [/code]
    C. Unit Fraction Partition - by Ainu7
    [code c++]
    #include
    #include
    #include
    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;
    }
    [/code]
    D. Circle and Point - by fireduck
    * 대회 도중에는 풀리지 않았던 문제인데 fireduck님께서 후에 AC를 받으셔서 첨부합니다 :)
    [code c++]
    #include
    #include
    #include
    #include
    #include
    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);
    }
    [/code]
    E. Name the Crossing - by normit
    [code c++]
    #include
    #include
    #include
    #include
    #include
    #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 vi;
    typedef long long ll;
    int n,m;
    void solve()
    {
    char buf[40];
    int edge[201][201] = {0, };
    map dic;
    vector 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 > q;
    q.push(mp(strong,0));
    while(!q.empty() && !cnt) {
    pair 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;
    }
    [/code]
    F. playground - by zizavino
    [code c++]
    #include
    #include
    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;
    }
    [/code]
    G. The Embarassed Cryptographer - by Astein
    [code c++]
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    int pprime[1000001];
    vector 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 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");
    }
    }
    [/code]
    H. Crashing Robots - by normit
    [code c++]
    #include
    #include
    #define REP(i,n) for(int i=0; i < (n); ++i)
    #define mp make_pair
    #define pb push-back
    using namespace std;
    typedef vector 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;
    }
    [/code]

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    18년 전
9개의 댓글이 있습니다.
  • User Avatar
    JongMan

    오 베스트 서브미션 올린 사람들은 에디토리얼을 써라 써라 써라~!!


    18년 전 link
  • User Avatar
    legend12

    F번 문제를 완전히 안드로로 이해한건가 O


    18년 전 link
  • User Avatar
    JongMan

    고돌 TL 어디갓어


    18년 전 link
  • User Avatar
    soyoja

    G 번 해법 설명좀 부탁드립니다.. 그냥 BigInt 로 나누면서 체크했는데 TLE 났습니다..


    18년 전 link
  • User Avatar
    legend12

    TL 이 어디갔냐니 뭔 소리야?


    18년 전 link
  • User Avatar
    legend12

    G번은 잘보시면 BigInt 를 한자리씩 저장하는게 아니라 여러자리씩 묶어서 계산하는 것이 핵심!입니다.


    18년 전 link
  • User Avatar
    JongMan

    나도 그땐 의미를 갖고 썻는데 지금 보니 왠지 모르겟어 --;


    18년 전 link
  • User Avatar
    zolac

    F번 문제를 완전히 안드로로 이해한건가 O(TL) 인듯^


    18년 전 link
  • User Avatar
    JongMan

    아하!!!!!!


    18년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.