CDOJ第7回ACM面白プログラム設計コンテスト第3回（正式試合）題解
5305 ワード
貴重な資源
テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1265
題意
平面上でn個の点（n<=1000）をあげて、面積の最小の正方形を探して、すべての点をすべて網羅します。
正方形の辺は軸と平行にしていなければなりません。
クイズ:
この問題に対して、まず題意を満たす矩形を探してもいいです。面積は一番小さい長方形です。
長方形の長さがLで、幅がWであると仮定すると、明らかに：
正方形が必要ですから、正方形の辺が長いです。
コードは以下の通りです
テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1263
題意
nチェーンをあげます。各チェーンの長さはa[i]です。
操作するたびにチェーンを選択してください。このチェーンの長さは1を減らして、二つのチェーンが一緒に連結されています。接続後の長さは1を加算します。
最小操作回数を問い合わせる。
クイズ:
欲張り
長さの減少した鎖を選択すると、必ずオプションであり、最小の長さのチェーンがあります。
私たちは連結されたチェーンを選択します。きっと現在の長さが一番大きい二つのチェーンです。
なぜですか
すべてのチェーンの長さが無限長であると仮定して、この問題の答えは間違いなくn-1です。
しかし、長さは無限ではないので、チェーン長-1のこの操作によって、いくつかのチェーンが除去され、答えがn-1より小さいです。
簡単に見られますが、私たちの前の貪欲な策略はできるだけ多くのチェーンを長さ-1の段階で消されます。
ですから、この問題はもう終わりました。
コード:
テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1264
題意
nをあげます。一番少ない数を見つけてください。そしてこれらの数は一回まで使います。
1−nのすべての数は、加算により構成され得る。
最低何個の数をお聞きしますか？
クイズ:
数学の問題
今の[1,K]の範囲内の数なら、あなたは全部得られます。
一つの数を加えると、一番大きな数ができますか？
答えは3 K＋1です
なぜですか
あなたが加入した数がAであるとすると、少なくともK＋1〜A−1の範囲内の数は、A−Xを通じて得られなければなりません。
A-K，A-1は、Aを最大にするために、A-K=K＋1を考慮して、連続するので、A=2 K+1とする。
A+K=3 K+1は最大で構成できます。
だから結論を得ることができます。1枚のお金は最大で1元で、2枚のお金は4元で、3枚は13元で、4枚は40元です。
ですから、この問題はもう終わりました。
コード
テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1266
題意
四元の数は実数によって、i，j，kの3つの要素を加えて構成されています。そして、それらは次のような関係があります。
i^2=j^2=k^2=−1
i×j=−j×i=k
j×k=−k×j=i
k×i=−i×k=j
明らかに、4元の数は交換法則を満たしていません。Nの長さを持つ4元の倍数式（i，j，kだけを含む）をあげます。結果を1に等しくするために、式の中の任意の2つの数を選んで交換しますが、交換回数はM回より大きくはできません。
結果を1にできるなら、交換の最低ステップ数を出力します。
さもないと、出力−1。
クイズ:
数学の問題
この問題の結論は次の通りです。
1.この列の最後の答えがi，j，kなら、直接-1を出力します。
2.この列の最後の答えが1なら、0を出力します。
3.この列の最後の答えが-1なら、特別な場合ではなく、1を出力します。
特殊な状況は以下の通りです。
1.m=0
2.この串はi、j、k.（交換と交換は同じです。
結論に関する証明
最初の結論証明：
明らかに成立しています。位置を変えるのは記号だけです。
第二の結論も明らかに成立した。
第三の結論：
まず意識しました。交換法則は満足していませんが、結合律は満足しています。
すなわちi jk=i(jk)
隣同士の違う文字を自由に交換すればいいです。答えを-1に乗せることができます。
コード
テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1262
題意
n本の薬があります。中には2本の薬があります。他の薬よりも0.1 g軽いです。
どの薬の中の薬に問題があっても、一度に測定して答えが出るような仕組みが必要です。
シナリオの辞書順が一番小さいことが要求されます。
クイズ:
暴力
1.まずfibが間違っています。
2.n=2なら、注意出力1,1
3.データ範囲は52.
もしあなたがデータをnとする案を作ったとしたら、私達は今もう一つの数を加えて入れます。この数はいくらですか？
直接暴力
子供から暴力まで、どの数と前のn個の数の和が現れたことがないことを見ます。
そしてこの問題は終わりです。
コード
テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1265
題意
平面上でn個の点（n<=1000）をあげて、面積の最小の正方形を探して、すべての点をすべて網羅します。
正方形の辺は軸と平行にしていなければなりません。
クイズ:
この問題に対して、まず題意を満たす矩形を探してもいいです。面積は一番小さい長方形です。
長方形の長さがLで、幅がWであると仮定すると、明らかに：
L = (MaxX - MinX)
W = (MaxY - MinY) 正方形が必要ですから、正方形の辺が長いです。
L max(L,W) 。コードは以下の通りです
#include
#include
using namespace std;
unsigned long long x1=99999999999LL,x2=0,y1=99999999999LL,y2=0;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
unsigned long long X ,Y;
cin>>X>>Y;
x1 = min(x1,X);
x2 = max(x2,X);
y1 = min(y1,Y);
y2 = max(y2,Y);
}
unsigned long long l = max(x2-x1,y2-y1);
cout< テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1263
題意
nチェーンをあげます。各チェーンの長さはa[i]です。
操作するたびにチェーンを選択してください。このチェーンの長さは1を減らして、二つのチェーンが一緒に連結されています。接続後の長さは1を加算します。
最小操作回数を問い合わせる。
クイズ:
欲張り
長さの減少した鎖を選択すると、必ずオプションであり、最小の長さのチェーンがあります。
私たちは連結されたチェーンを選択します。きっと現在の長さが一番大きい二つのチェーンです。
なぜですか
すべてのチェーンの長さが無限長であると仮定して、この問題の答えは間違いなくn-1です。
しかし、長さは無限ではないので、チェーン長-1のこの操作によって、いくつかのチェーンが除去され、答えがn-1より小さいです。
簡単に見られますが、私たちの前の貪欲な策略はできるだけ多くのチェーンを長さ-1の段階で消されます。
ですから、この問題はもう終わりました。
コード:
#include
#include
#include
using namespace std;
int a[2005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
int l = 1,r = n;
int ans = 0;
while(l テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1264
題意
nをあげます。一番少ない数を見つけてください。そしてこれらの数は一回まで使います。
1−nのすべての数は、加算により構成され得る。
最低何個の数をお聞きしますか？
クイズ:
数学の問題
今の[1,K]の範囲内の数なら、あなたは全部得られます。
一つの数を加えると、一番大きな数ができますか？
答えは3 K＋1です
なぜですか
あなたが加入した数がAであるとすると、少なくともK＋1〜A−1の範囲内の数は、A−Xを通じて得られなければなりません。
A-K，A-1は、Aを最大にするために、A-K=K＋1を考慮して、連続するので、A=2 K+1とする。
A+K=3 K+1は最大で構成できます。
だから結論を得ることができます。1枚のお金は最大で1元で、2枚のお金は4元で、3枚は13元で、4枚は40元です。
ですから、この問題はもう終わりました。
コード
#include
#include
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int ans = 1;
int l = 1;
int sum = 1;
while(sum テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1266
題意
四元の数は実数によって、i，j，kの3つの要素を加えて構成されています。そして、それらは次のような関係があります。
i^2=j^2=k^2=−1
i×j=−j×i=k
j×k=−k×j=i
k×i=−i×k=j
明らかに、4元の数は交換法則を満たしていません。Nの長さを持つ4元の倍数式（i，j，kだけを含む）をあげます。結果を1に等しくするために、式の中の任意の2つの数を選んで交換しますが、交換回数はM回より大きくはできません。
結果を1にできるなら、交換の最低ステップ数を出力します。
さもないと、出力−1。
クイズ:
数学の問題
この問題の結論は次の通りです。
1.この列の最後の答えがi，j，kなら、直接-1を出力します。
2.この列の最後の答えが1なら、0を出力します。
3.この列の最後の答えが-1なら、特別な場合ではなく、1を出力します。
特殊な状況は以下の通りです。
1.m=0
2.この串はi、j、k.（交換と交換は同じです。
結論に関する証明
最初の結論証明：
明らかに成立しています。位置を変えるのは記号だけです。
第二の結論も明らかに成立した。
第三の結論：
まず意識しました。交換法則は満足していませんが、結合律は満足しています。
すなわちi jk=i(jk)
隣同士の違う文字を自由に交換すればいいです。答えを-1に乗せることができます。
コード
#include
#include
using namespace std;
char s[1005];
int flag[4][4]={
{0,1,2,3},
{1,0,3,2},
{2,3,0,1},
{3,2,1,0}
};
int idx(char c)
{
if(c=='i')return 1;
if(c=='j')return 2;
if(c=='k')return 3;
return 0;
}
int main()
{
int n,m;
scanf("%d%d%s",&n,&m,s);
int sig=1;
int now = 0;
int Test = 0;
for(int i=0;i0&&s[i]!=s[i-1])
Test=1;
int k = idx(s[i]);
if(now == k)
{
sig = sig * (-1);
now = 0;
}
else
{
if(now==1&&k==3)
sig = sig * (-1);
if(now==2&&k==1)
sig = sig * (-1);
if(now==3&&k==2)
sig = sig * (-1);
now = flag[now][k];
}
}
if(now)return puts("-1");
if(sig==-1&&Test==0)return puts("-1");
if(sig==1)return puts("0");
else if(sig==-1&&m>0)return puts("1");
return puts("-1");
} テーマ接続:
http://acm.uestc.edu.cn/#/problem/show/1262
題意
n本の薬があります。中には2本の薬があります。他の薬よりも0.1 g軽いです。
どの薬の中の薬に問題があっても、一度に測定して答えが出るような仕組みが必要です。
シナリオの辞書順が一番小さいことが要求されます。
クイズ:
暴力
1.まずfibが間違っています。
2.n=2なら、注意出力1,1
3.データ範囲は52.
もしあなたがデータをnとする案を作ったとしたら、私達は今もう一つの数を加えて入れます。この数はいくらですか？
直接暴力
子供から暴力まで、どの数と前のn個の数の和が現れたことがないことを見ます。
そしてこの問題は終わりです。
コード
#include
#include
using namespace std;
int a[100000];
int ans[60];
int check(int x,int tot)
{
for(int i=1;i