원 경기 1013(A number game)
Time Limit:1000MS Memory Limit:65536K Total Submit:69 Accepted:7
Description
You've designed a computer and implemented all the common arithmetic operators: addition, subtraction, multiplication and integer division. However, your budget was very limited, so you could only afford to place a single register in the computer. The register can store any non-negative integer value. Since there is only one register, there is no need to identify the store location or the operands of each operation or its result. The programming language has four instructions: '+', '-', '*' and '/'. Each instruction performs the corresponding operation using the value in the register as both its parameters. It then stores the result in the same register, overwriting the previous content. A program for your computer is a sequential list of zero or more instructions. You want to show that, even with its limitations, your newly constructed computer is powerful. You will be given two ints s and t. Return the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-("(quotes for clarity) instead.
Input
There are at most 100 cases,each case one line contain 2 space seperated integers S and T. (1 <= S,T <= 10^9)
Output
Output the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-("(quotes for clarity) instead.
Sample Input
7 392 7 256 4 256 7 9
Sample Output
+*+/+*** ** :-(
Source
코드는 RE를 수차 없이 간소화할 수 있는 곳이 많고, MLEn 수차...내가 여기서 A
CODE:
/*BFS*/
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
bool mark[1000];// ， 1*1=1 ， MLE
struct px
{
char path[1000];//
__int64 v;
int l;
};
struct px s;
__int64 A,B;
char ans1[1005],ans2[1005];//
queue<px>Q;
int flag=0,len;
void bfs()
{
struct px t,p;
while(!Q.empty())
Q.pop();
Q.push(s);
while(!Q.empty())
{
t=Q.front();
Q.pop();
if(t.v==B)
{
flag=1;
if(t.l<len)
{strcpy(ans1,t.path);len=t.l;}
else if(t.l==len)
{
if(strcmp(t.path,ans1)<0)
strcpy(ans1,t.path);
}
//puts(t.path);
break;
}
if((t.v*t.v)<=B)// * ，
{
if((t.v*t.v)<900)
{
if(!mark[t.v*t.v])
{
mark[t.v*t.v]=true;
p=t;
p.path[p.l++]='*';
p.path[p.l]='/0';
p.v*=p.v;
Q.push(p);
}
}
else
{
//mark[t.v*t.v]=true;
p=t;
p.path[p.l++]='*';
p.path[p.l]='/0';
p.v*=p.v;
Q.push(p);
}
}
if(t.v+t.v<=B)
{
if((t.v+t.v)<900)// ，
{
if(!mark[t.v+t.v])
{
mark[t.v+t.v]=true;
p=t;
p.path[p.l++]='+';
p.path[p.l]='/0';
p.v+=p.v;
Q.push(p);
}
}
else
{
//mark[t.v+t.v]=true;
p=t;
p.path[p.l++]='+';
p.path[p.l]='/0';
p.v+=p.v;
Q.push(p);
}
}
}
return;
}
int main()
{
while(scanf("%I64d%I64d",&A,&B)!=EOF)
{
if(B==1)
{printf("//n");continue;}
memset(mark,false,sizeof(mark));
ans1[0]='/0';
ans2[0]='/0';
flag=0;
len=99999999;//
if(A>B)
{
mark[1]=true;
s.v=1;
s.l=1;
s.path[0]='/';
s.path[1]='/0';
bfs();
if(!flag)
printf(":-(/n");
else
printf("%s/n",ans1);
}
else
{
flag=0;
s.v=A;
if(A<900)
mark[A]=true;
s.path[0]='/0';
s.l=0;
bfs();
if(flag)
strcpy(ans2,ans1);
memset(mark,false,sizeof(mark));
flag=0;
mark[1]=true;
s.v=1;
s.l=1;
s.path[0]='/';
s.path[1]='/0';
bfs();
if(flag)// ，WA ，
{
if(ans2[0]!='/0')
{
if(strlen(ans1)<strlen(ans2))
printf("%s/n",ans1);
else if(strlen(ans1)>strlen(ans2))
printf("%s/n",ans2);
else
{
if(strcmp(ans1,ans2)<0)
printf("%s/n",ans1);
else
printf("%s/n",ans2);
}
}
else
printf("%s/n",ans1);
}
else
{
if(ans2[0]!='/0')
printf("%s/n",ans1);
else
printf(":-(/n");
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
