NOJ-1641誤ったアルゴリズム
2790 ワード
[1641]誤ったアルゴリズム時間制限:5000 msメモリ制限:65535 K 問題の説明あるテーマはこうです.
n行m列メッシュを入力し、その行と列のすべての格子の数の和が最大になるように格子を探します.答えが一意でない場合は,任意の解を出力すればよい.例えば、以下の例では、第1行と第3列の交点(行は上から下へ1~n、列は左から右へ1~m)であり、全ての7つの数の和は35である(1,3).
まず、行r(1<=r<=n)を1行探して、その行のすべての数の和を最大にし、その後、列c(1<=c<=m)を1列探して、その列のすべての数の和を最大にし、最後に直接出力する(r,c).条件を満たすrが複数ある場合、最小のrを出力する.cについても同様に処理する.
明らかに、このアルゴリズムは間違っていますが、ほとんどのテストデータに合格しました.このエラーアルゴリズムに正しい結果をもたらす「弱い」データを見つけて、審判たちがこれらのデータを改善することができますか?
入力100を超えないデータを入力します.各データの第1の動作の2つの整数n,m(1<=n<=500,1<=m<=500),すなわち行数および列数.以下のn行は、行毎にm個1~100の整数を含む.入力した総サイズは2 MBを超えない.
出力各グループのデータについて、エラーアルゴリズムが正しい結果を得ることができれば、「Weak」を出力し、そうでなければ「Strong」を出力する.
サンプル入力
サンプル出力
昨晩は12時までやって、CYW大神の辛抱強い教え(いいでしょう私はやはり理解していません)を経て、それから寝る時またしばらく考えて、大神の言う正しい解を要求してはいけない意味(正しい解の対応するSUMを求めるだけでいい)を知った.不注意で問題の条件解を無視して複数にすることができます.したがって,問題中の審判アルゴリズムが与えた解は運の成分にすぎず,たまたま正しいことを証明するだけである.ニマは朝起きてノートを開けてコードを変えたが、やはりACだった.俺の丸薬だ
1、問題で与えられた条件で審判が求める解を算出する.
2、最適解同士が合致するその行列SUM値の最大とMAXを正確なアルゴリズムで算出する.
3、SUMを計算する公式を審判の解で代入し、誤りがあれば審判の解を説明する(Strong).そうでなければWeakです.
ACコード:
n行m列メッシュを入力し、その行と列のすべての格子の数の和が最大になるように格子を探します.答えが一意でない場合は,任意の解を出力すればよい.例えば、以下の例では、第1行と第3列の交点(行は上から下へ1~n、列は左から右へ1~m)であり、全ての7つの数の和は35である(1,3).
, :
まず、行r(1<=r<=n)を1行探して、その行のすべての数の和を最大にし、その後、列c(1<=c<=m)を1列探して、その列のすべての数の和を最大にし、最後に直接出力する(r,c).条件を満たすrが複数ある場合、最小のrを出力する.cについても同様に処理する.
明らかに、このアルゴリズムは間違っていますが、ほとんどのテストデータに合格しました.このエラーアルゴリズムに正しい結果をもたらす「弱い」データを見つけて、審判たちがこれらのデータを改善することができますか?
入力100を超えないデータを入力します.各データの第1の動作の2つの整数n,m(1<=n<=500,1<=m<=500),すなわち行数および列数.以下のn行は、行毎にm個1~100の整数を含む.入力した総サイズは2 MBを超えない.
出力各グループのデータについて、エラーアルゴリズムが正しい結果を得ることができれば、「Weak」を出力し、そうでなければ「Strong」を出力する.
サンプル入力
4 4
5 5 5 5
1 1 5 1
1 1 5 1
1 1 5 1
5 4
2 5 1 1
1 1 9 1
1 1 1 1
1 1 1 1
1 1 1 1
サンプル出力
Case 1: Weak
Case 2: Strong
昨晩は12時までやって、CYW大神の辛抱強い教え(いいでしょう私はやはり理解していません)を経て、それから寝る時またしばらく考えて、大神の言う正しい解を要求してはいけない意味(正しい解の対応するSUMを求めるだけでいい)を知った.不注意で問題の条件解を無視して複数にすることができます.したがって,問題中の審判アルゴリズムが与えた解は運の成分にすぎず,たまたま正しいことを証明するだけである.ニマは朝起きてノートを開けてコードを変えたが、やはりACだった.俺の丸薬だ
1、問題で与えられた条件で審判が求める解を算出する.
2、最適解同士が合致するその行列SUM値の最大とMAXを正確なアルゴリズムで算出する.
3、SUMを計算する公式を審判の解で代入し、誤りがあれば審判の解を説明する(Strong).そうでなければWeakです.
ACコード:
#include<iostream>
#include<stdio.h>
using namespace std;
int list[510][510];
int hang,lie;
int sum1(int x,int y)
{
int i,j,sum=0;
for(i=x-1;i>=1;i--)
{
sum+=list[i][y];
}
for(i=x+1;i<=hang;i++)
{
sum+=list[i][y];
}
for(i=y-1;i>=1;i--)
{
sum+=list[x][i];
}
for(i=y+1;i<=lie;i++)
{
sum+=list[x][i];
}
return (sum+list[x][y]);
}
int main(void)
{
int i,j,ar,ac,sum,inr,inc,max,co=0,tsum,rc;
while(cin>>hang>>lie)
{
co++;
for (i=1 ;i<=hang ;i++)
{
for (j=1; j<=lie; j++)
cin>>list[i][j];
}
max=0;
inr=1;
for (i=1 ;i<=hang ;i++)
{
sum=0;
for (j=1; j<=lie; j++)
{
sum+=list[i][j];
}
if(sum>max)
{
max=sum;
inr=i;
}
}
max=0;
inc=1;
for (j=1 ;j<=lie ;j++)
{
sum=0;
for (i=1; i<=hang; i++)
{
sum+=list[i][j];
}
if(sum>max)
{
max=sum;
inc=j;
}
}
max=0;
for(i=1;i<=hang;i++)
{
for(j=1;j<=lie;j++)
{
tsum=sum1(i,j);
if(tsum>max)
{
max=tsum;
}
}
}
if(sum1(inr,inc)==max)
{
printf("Case %d: Weak
",co);
}
else
{
printf("Case %d: Strong
",co);
}
memset(list,0,sizeof(list));
}
return 0;
}