2020ブルーブリッジカップ合併検査

7月5日のブルーブリッジカップb組の原題も続々と出てきて、今日はc題の合併検査を見て、まず問題を出します:【問題の説明】新型コロナウイルスによって引き起こされた新型コロナウイルスは最近A国で蔓延して、できるだけ早く疫病をコントロールするために、A国は大量の民衆にウイルスの核酸検査に入る準備をしています.しかし、検査に用いる試薬箱は不足しています.この困難を解決するために、科学者は1つの方法を考えました:合併検査.(k個)採取した標本を同一のキットに入れて検出した.結果が陰性であれば、このk人はいずれも陰性であることを示し、1つのキットでk人の検出を完了した.結果が陽性であれば、少なくとも1人が陽性であることを示し、このk人のサンプルを全て独立して検出する必要がある(理論的には、検出前のk−1人が陰性であればk番目が陽性と推定されるが、実際の操作ではこの推定を利用せず、k個人を独立して検出する)に加え、最初の併合検出を加えてk+1個のキットを用いてk個人の検出を完了した.A国は、測定された民衆の感染率はおよそ1%と推定し、均一であった分布.すみません、kはいくら取れば一番試薬箱を節約できますか?正直に言うと、初めてこの問題を見ると斬新で、均一な分布に関連して、数学の確率論を使うと思っていたが、相応の構造も見つからなかったので、本題の構想も確かに明確ではなかった.その後、ネットで他の人のブログを見て分析してやっとこの問題を解決し、このブログを書いてノートとして勉強した.考え方:この問題はまず検査の総人数をmと仮定し、もちろん確定した数字を仮定することもできます.例えば1001000などです.それから、私たちは提案に基づいて、検査時にk人単位で集団検査を行うことができます.では、まずm/k個のキットが必要で、この結果は下に整理されています.その後、この群の0.01 m人は陽性であり、感染は均一に分布しているため、追加の0.01 m*k個のキットが必要であり、m/kに余裕がある場合、追加のキットには1を加える必要があるため、必要なキット全体が両者に加算される.

int main()
{
    int m=100;//      
    int minn=9999999;
    int k,sum,ans;
    for(k=1;k<=100;k++)
    {
        if(100%k==0)
        {
            sum=100/k+k;
        }
        else
            sum=100/k+k+1;
        if(sum<minn)//             
        {
            minn=sum;
            ans=k;
        }
    }
    cout<<ans<<endl;
}