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)$.
#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月27日09時01分09秒
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)