当前位置: 代码迷 >> 综合 >> [bzoj3957][构造]To Add or to Multiply
  详细解决方案

[bzoj3957][构造]To Add or to Multiply

热度:51   发布时间:2023-12-19 04:43:40.0

Description

工业计算机处理器公司为顾客量身定做了非常快速、用于专门目的的处理单元。a-C-m系列的处理器(比如1-C-2和5-C-3)的指令集只有两种操作:
  ? A 数值加a   ? M 数值乘m
  处理器接收一个整数,执行一个A和M的指令序列(即程序)来修改输入,然后输出结果。举个例子,1-C-2处理器执行程序AAAM处理输入2返回输出10(计算过程是2→3→4→5→10),然而5-C-3处理器用相同的程序和输入返回51(2→7→12→17→51)。
  你是一个被指定做一个顶级秘密项目的a-C-m程序员。这意味着你不会被告知你的程序执行的精确输入。但会得到四个特别的值p,q,r,s,以及下列条件
  1、输入保证是一个在p、q之间的数   2、输出必须是一个在r,s之间的数。
  给你一个a-C-m处理器和p,q,r,s这四个数。你的工作是构想最短的a-C-m程序,使得任意任意x保证p≤x≤q,返回一个输出y使得r≤y≤s。如果有多个最短的程序,选择字典序最小的,而一个程序即是由A和M组成的字符串。

Input

输入包含多组数据。每组数据在一行中给你6个整数a,m,p,q,r,s,每个就像上面描述的一样。 末行输入6个0作为结束。

Output

对于每组数据,在你的程序前输出数据的编号,程序即像上面描述的一样。输出单词“empty”,如果最好的程序没有操作。输出单词“impossible”如果没有程序满足具体要求。
输出一个用空格分隔的字符串序列,任两个相邻的字符串形式分别为“nA”和“nM”,n>0。前者表示n个连续的操作A,后者表示n个连续的操作M。

Sample Input

1 2 2 3 10 20

1 3 2 3 22 33

3 2 2 3 4 5

5 3 2 3 2 3

0 0 0 0 0 0

Sample Output

Case 1: 1A 2M

Case 2: 1M 2A 1M

Case 3: impossible

Case 4: empty

HINT

所有的的a,m,p,q,r,s∈[1,1000000000],且p≤q,r≤s。

题解

感觉我已经变得奇奇妙妙了…
菜的真实
首先你可以知道,对于任意输入一个数 x x x,最终一定可以变为这样的形式
x ? m k + a ? ( t k ? m k + t k ? 1 ? m k ? 1 . . . + t 0 ? m 0 ) x*m^k+a*(t_k*m^k+t_{k-1}*m^{k-1}...+t_0*m^0) x?mk+a?(tk??mk+tk?1??mk?1...+t0??m0)
主要是我没有把这个形式后面写成系数允许为0的形式然后就挂了
你可以发现,在 m m m不等于 1 1 1的情况下这个 k k k最多只有 30 30 30,然而 m = 1 m=1 m=1的情况下只会用加 a a a的情况,这个判掉就可以了…
所以枚举一下这个 k k k,我们只需要让 x = p x=p x=p时满足上式大于等于 r r r x = q x=q x=q时上式小于等于 s s s即可
我们可以得到他们的差分别是 s 1 s1 s1 s 2 s2 s2,不妨设后面的式子为 p 1 p1 p1 p 2 p2 p2
我们发现 p 1 , p 2 p1,p2 p1,p2均是由 a a a组成的,所以可以把 s 1 = ? s 1 a ? s1=\lceil\frac{s1}{a}\rceil s1=?as1?? s 2 = ? s 2 a ? s2=\lfloor\frac{s2}{a}\rfloor s2=?as2??,然后构造后面的多项式
发现其实这是一个 m m m进制的数,我们把 s 1 , s 2 s1,s2 s1,s2写成 m m m进制,类似数位dp一下就可以了…
大概就是如果前面不顶两个界,直接填0就可以了
如果顶着下界,看看这个位能不能填一个大于下界的数,让后面的位置全部填0
否则的话按下界填就可以了
OZY天下第一!!!!!!!!!!!

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(LL x){
    write(x);putchar('\n');}
int a,m,p,q,r,s;
int sum;
int temp[2][35],ln[2],ans[35],lin[35];
void get(int x,int len,int opt)
{
    memset(temp[opt],0,sizeof(temp[opt]));LL base=1;ln[opt]=0;for(int i=1;i<=len;i++){
    temp[opt][++ln[opt]]=x%m;if(i==len)temp[opt][i]=x;x/=m;if(!x)return ;}
}int num1[110],num2[110],ln1;
int as1[110],as2[110],ln2;
void work(int mx)
{
    ln1=0;memset(num1,0,sizeof(num1));for(int i=1;i<=mx;i++){
    if(lin[i]){
    num1[++ln1]=lin[i];num2[ln1]=1;// if(i!=mx)ln1++;}if(!ln1)ln1=1;if(i!=mx)num1[ln1]++,num2[ln1]=2;}if(lin[mx])ln1--;
}
int main()
{
    
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);int tt=0;while(++tt){
    memset(num2,0,sizeof(num2));memset(as1,0,sizeof(as1));memset(as2,0,sizeof(as2));a=read();m=read();p=read();q=read();r=read();s=read();if(!a&&!m&&!p&&!q&&!r&&!s)break;printf("Case %d: ",tt);if(p>=r&&q<=s)puts("empty");else if(q>s)puts("impossible");else{
    if(m==1){
    int down=(r-p)/a;if((r-p)%a)down++;int up=(s-q)/a;if((s-q)%a)up++;if(p+1LL*down*a>s||q+1LL*up*a>s||down>up)puts("impossible");else printf("%dA\n",down);}else{
    bool tf=false;sum=(1<<31-1);LL base=1;int del=a;a=1;for(int i=0;i<=30;i++){
    memset(lin,0,sizeof(lin));if(i)base=base*m;if(base>s||1LL*p*base>s||1LL*q*base>s)break;int s1=r-p*base,s2=s-q*base;if(s1<0)s1=0;s1=(s1+del-1)/del;s2=s2/del;get(s1,i+1,0);get(s2,i+1,1);int tot=i,gg=0;bool yes=0,ok=1;for(int j=max(ln[0],ln[1]);j>=1;j--){
    if(!gg)//前面填的都是顶下界的 {
    if(a*((temp[0][j]+a-1)/a)>temp[1][j]){
    ok=0;break;}int num=a*((temp[0][j]+a-1)/a);if(num>temp[0][j])tot+=num/a,lin[j]=num/a,gg=1;else{
    if(num+a<=temp[1][j]||yes){
    bool bk=false;for(int k=j-1;k>=1;k--)if(temp[0][k]){
    bk=true;break;}if(bk)tot+=num/a+1,lin[j]=num/a+1,gg=1;else tot+=num/a,lin[j]=num/a;}else tot+=num/a,lin[j]=num/a;}}else lin[j]=0;if(temp[0][j]<temp[1][j])yes=1;}if(!ok)continue;tf=1;work(i+1);if(tot<sum){
    sum=tot;memcpy(as1,num1,sizeof(as1));memcpy(as2,num2,sizeof(as2));ln2=ln1;}else if(tot==sum){
    bool ok=true;for(int i=ln1,j=ln2;i>=1,j>=1;i--,j--){
    if(num2[i]>as2[j]){
    ok=false;break;}if(num2[i]<as2[j])break;if(num1[i]==as1[j])continue;else{
    if(num1[i]>as1[j]){
    if(num2[i]>as2[j-1]){
    ok=false;break;}else break;}else{
    if(as2[j]>num2[i-1]){
    ok=false;break;}else break;}}}if(ok){
    	memcpy(as1,num1,sizeof(as1));memcpy(as2,num2,sizeof(as2));ln2=ln1;}}}if(!tf)puts("impossible");else{
    for(int i=ln2;i>=1;i--){
    printf("%d",as1[i]);if(as2[i]==1)putchar('A');else putchar('M');if(i!=1)putchar(' ');}puts("");}}}}return 0;
}
  相关解决方案