Codeforces Round #268 DIV1 A問題/DIV2 C問題 - 24 Game

Source

Codeforces Round #268 DIV1 A問題 (500pt)
Codeforces Round #268 DIV2 C問題 (1500pt)
Problem description

問題概要

最初，$1$ から $N$ までの整数が $1$ 個ずつある．
$2$ 個の整数 $a, b$ を選び，それらを取り除いて，$a+b,a-b,ab$ のどれかを追加する，という操作を繰り返す．
最終的に，$1$ 個の整数 $24$ だけにしたい．
そのような操作の列を $1$ つ求める問題．
存在しないならそれを指摘する．
途中で，$10^{18}$ を超える整数を作成してはいけない．

解法

色々あるが，以下の様な感じでやった．
$N \leq 3$ では不可能．
$4 \leq N \leq 47$ では，最初から順番に整数を使って行った場合に作れる整数をDPで求め，経路復元した．
ただし，最初から順番に使うのでは $N=5$ の場合は作れないので，手で作って埋め込んだ．
$N \geq 48$ では，$N-(N-1), (N-2)-(N-3), \ldots$ と $1$ を $\lceil N/2 \rceil$ 個作って，$24$ 個分足して，残りは掛けた．
これは，かなり上手くない方法で，他の方法は，例えば，$N-(N-1)$ で $1$ を作って，最後に $24$ とかけることにして，入力が $N-2$ の場合に帰着させる．
で，$N=4,5$ は手動で作る．
または，$N=4,5$ は手動で作り，$N=6$ の時に，$24$ および $0$ を作り，大きい整数は全部 $0$ と掛け算して消し，最後に $24$ と $0$ を足す，など．
時間計算量 $O(N)$．

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}

int N;
int dp[100][1000];
int sign[100];

int main(){
  int i, j, k;
  int cnt;

  reader(&N);

  if(N<=3){
    puts("NO");
    return 0;
  }
  puts("YES");

  if(N==5){
    puts("4 * 5 = 20");
    puts("20 + 3 = 23");
    puts("23 + 2 = 25");
    puts("25 - 1 = 24");
    return 0;
  }

  if(N >= 48){
    cnt = 0;
    for(i=N;i>=2;i-=2){
      printf("%d - %d = 1\n",i,i-1);
      cnt++;
    }
    if(i==1) cnt++;

    REP(i,1,24) printf("%d + 1 = %d\n",i,i+1);
    REP(i,24,cnt) puts("24 * 1 = 24");
    return 0;
  }

  dp[1][1] = 1;
  REP(i,1,N+1) rep(j,1000) if(dp[i-1][j]){
    if(j*i < 1000) dp[i][j*i] = 1;
    if(j+i < 1000) dp[i][j+i] = 1;
    if(j-i >= 0)   dp[i][j-i] = 1;
  }

  k = 24;
  for(i=N;i;i--){
    if(k%i==0) if(dp[i-1][k/i]){ sign[i] = -2; k /= i; continue; }
    
    if(dp[i-1][k+i]){ sign[i] = -1; k += i; }
    else            { sign[i] =  1; k -= i; }
  }

  k = 1;
  REP(i,2,N+1){
    if(sign[i]==-2)     printf("%d * %d = %d\n",k,i,k*i), k*=i;
    else if(sign[i]==1) printf("%d + %d = %d\n",k,i,k+i), k+=i;
    else                printf("%d - %d = %d\n",k,i,k-i), k-=i;
  }

  myed;
  return 0;
}

Current time: 2024年04月26日11時23分37秒
Last modified: 2014年09月24日06時15分49秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF268 CF_Div1_A CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：