Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1735-1d325e53
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #41 C問題 - Safe cracking (この記事を編集する[管理者用])

Source

Codeforces Beta Round #41 C問題
Problem description
Beta Round #41の自分の参加記録

問題概要

4つの10億以下の正整数が円状に並んでいる.
隣り合う2つの要素を選んで以下の2つの操作のどちらかができる.
 両方に1を足す
 両方とも偶数なら,両方を2で割る
全部1にする手順を1つ求める問題.最小手順である必要はないが1000手以下でなければならない.
できないならそれを指摘する.

解法

Adhoc.不可能な場合はない.
偶数同士を見つけたら割る.奇数同士(両方1でない)なら1を足して割る.
そういうペアがないなら,2回足して,+1 +2 +1という風にするなど.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n;
  int a[4], cmd=0;

  scanf("%d%d%d%d",a,a+1,a+2,a+3);
  for(;;){
/*    printf("%d : %d %d %d %d\n",cmd,a[0],a[1],a[2],a[3]);*/
    if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1) break;

    cmd++;
    
    rep(i,4) if(a[i]%2==0 && a[(i+1)%4]%2==0) break;
    if(i<4){
      a[i]/=2; a[(i+1)%4]/=2;
      printf("/%d\n",i+1);
      continue;
    }

    rep(i,4) if(a[i]+a[(i+1)%4]!=2 && a[i]%2==1 && a[(i+1)%4]%2==1) break;
    if(i<4){
      a[i]++; a[(i+1)%4]++;
      printf("+%d\n",i+1);
      continue;
    }

    m=0;
    rep(i,4) if(m<a[i]+a[(i+1)%4]) m=a[i]+a[(i+1)%4], k=i;
    a[k]++; a[(k+1)%4]++;
    printf("+%d\n",k+1);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1735-1d325e53
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。