Codeforces 1130 E.Wrong Answer 构造

题目要求构造一组数据使得题目给出代码的anwser和正确答案恰好相差k,我们记题目给出代码的输出为ans1,正确答案为ans2。

我们假设已经有总和为s的p个正数,使得此时的ans1=ans2=s*p,然后我们在左端添加一串长度为q,并且总和为-1的数,此时ans1=s*p,ans2=(s-1)*(p+q).

此时我们让ans2-ans1=k,于是我们推到得出s*(q-1)=k+p。

那么我们就可以通过枚举p,然后求k+p的因子,来判断是否存在合法方案。

显然p+q<=2000,并且由于p个数的总和应该达到k,所以p*1e6<=k ,然后另外的q个数和应该为-1,这个显然q为任意数都能构造出合法方案。

以下为具体代码。

#include<bits/stdc++.h>
using namespace std;
int i,i0,n,m;
int main()
{
scanf("%d",&n);
for(int p=1;p<=2000;p++)
{
for(i=1;i*i<=n+p;i++)
{
if((n+p)%i==0)
{
int q,k;
q=i,k=(n+p)/q+1;
if(q+p<=2000&&k<=(long long)1000000*p)
{
printf("%d\n",p+q);
for(i=1;i<q;i++)printf("0 ");
printf("-1");
for(i=1;i<=p;i++)
{
if(k>=1000000)printf(" 1000000"),k-=1000000;
else printf(" %d",k),k=0;
}
return 0;
}
q=(n+p)/i,k=i+1;
if(q+p<=2000&&k<=(long long)1000000*p)
{
printf("%d\n",p+q);
for(i=1;i<q;i++)printf("0 ");
printf("-1");
for(i=1;i<=p;i++)
{
if(k>=1000000)printf(" 1000000"),k-=1000000;
else printf(" %d",k),k=0;
}
return 0;
}
}
}
}
printf("-1\n");
return 0;
}
上一篇:7 python 模块间相互导入


下一篇:sax xpath读取xml字符串