-2

これに対する解決策がどこにも見つからないようです。以下に、問題の説明を示します。

問題文

コヒマ王は、幹部クラスの従業員が家を建てることができる新しい専用の通りを予約しました。彼はあなたにその通りを計画するように割り当てました。あなたは通り沿いのどの区画に新しい建物を建てることを許可するかを決めなければなりません。これを行うために、最初に建物にフリー プロットを割り当てる可能な方法の数を計算する必要があります。ただし、建物を建てることが許可されている 2 つの連続したプロットが存在しないという制限があります。彼らが幸せに暮らせるように、自由な部屋。通りは M セクションに分割されます。各区画は、通りの両側に 1 つずつ、合計 2 つの区画に対応しています。可能な割り当ての数を見つけます。

入出力仕様

入力スペック

最初の行では、M ( 0 < M ≤ 1000 ) が与えられます。

出力仕様 結果を変数 output1 に出力する必要があります。

注: 可能な解決策がない場合は、出力として 0 を返す必要があります。

例

入力: 3

出力: 25

説明例:

通りの片側だけを見て、X を建物が許可されている区画としてマークし、Y を自由な区画としてマークすると、XYX、YXY、YYX、XYY、YYY になります。

反対側にも同じ数が存在するので、5*5 = 25通りの組み合わせがあります。

4

10 に答える 10

3

この問題は、順列と組み合わせ、特に二項定理に関連しています。スコープは、この問題の数学方程式を取得できる人であり、その方程式の入力として任意の M を簡単に取得できます。

しかし、コーディングを使用すると、Python ソリューションは次のようになります。

from itertools import product
M = 7 #change as per need
cnt = 0
l = []

for w in product(['x','y'], repeat=M):
    tmp = ''.join(w)
    if 'xx' not in tmp:
        l.append(tmp)
        cnt += 1
print cnt*cnt
print l

出力インスタンス:

1156
['xyxyxyx', 'xyxyxyy', 'xyxyyxy', 'xyxyyyx', 'xyxyyyy', 'xyyxyxy', 'xyyxyyx', 'xyyxyyy', 'xyyyxyx', 'xyyyxyy', 'xyyyyxy', 'xyyyyyx', 'xyyyyyy', 'yxyxyxy', 'yxyxyyx', 'yxyxyyy', 'yxyyxyx', 'yxyyxyy', 'yxyyyxy', 'yxyyyyx', 'yxyyyyy', 'yyxyxyx', 'yyxyxyy', 'yyxyyxy', 'yyxyyyx', 'yyxyyyy', 'yyyxyxy', 'yyyxyyx', 'yyyxyyy', 'yyyyxyx', 'yyyyxyy', 'yyyyyxy', 'yyyyyyx', 'yyyyyyy']

それで、それは問題を解決します。大きな M に対して予期しない出力が発生する可能性がある場合は、コメントを投稿してください。

于 2016-09-30T07:55:51.123 に答える
2

再帰を使用します。大きな入力の場合、非常に多くの時間がかかるため、時間の複雑さについてはわかりません（実際には大きな値でハングアップします）。小さい入力、つまり M < 10 の場合、これで答えが得られるようです。

#include <iostream>

using namespace std;

int recur(char c, int num, int N) {
if (num == N) {
    return 1;
}

if (num < N) {
    if (c == 'X') {
        return recur('Y', num + 1, N);
    } else {
        return (recur('X', num + 1, N) + recur('Y', num + 1, N));
    }
}
}

int main()
{
int N = 4;

//x is number of combinations when the first slot is used to build a house
int x = recur('X', 1, N);

//y is number of combinations when the first slot is left empty
int y = recur('Y', 1, N);

cout << "x = " << x << endl;
cout << "y = " << y << endl;

//Since same number exists on other side also
cout << "total = " << (x + y) * (x + y) << endl;

return 0;
}
于 2014-09-05T17:49:54.983 に答える
1

この背後にあるロジックを提案します。X を 1、Y を 0 と見なします。010 101 000 100 001 は、2 つの 1 が隣接せず、合計 = 5 の場合です。結果 5*5 を返します。したがって、3 ビットの 2 進数を生成し、そのような数値ごとにカウントを増やします。

于 2016-03-09T16:46:28.863 に答える
0 
package HackerRank;

import java.io.IOException;
import java.util.Scanner;

class Tester1KingKohm {
    public static void plotmaker(int input) {
        int i = 1;
        int countx = 1;
        int county = 1;
        while (i <= input) {
            if (i > 1) {
                int tempx = countx;
                countx = county;
                county = tempx + county;
            }
            i++;
        }
        System.out.println(countx + " " + county);
        int total = countx + county;
        int bothsidetotal = total * total;
        System.out.println(bothsidetotal);

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        plotmaker(sc.nextInt());
    }
}
于 2016-11-10T02:49:35.750 に答える
0

再帰がこの問題の最良の解決策になると思います。私の考えは、深さ M で形成できるツリーについて考えることです。最後に、ツリー内の葉ノードの数を数えます。それはただの考えですが、実際の再帰は、最初に X を取ることができるかどうかを考えることから始めることができます。親（前のプロット）がYを取得した場合にのみ、XとYの両方を取得できます。ただし、親がXを取得した場合、Yのみを取得できます。このアイデアで、次のような再帰を作成しました。

int count=0; //Maintain a global counter to count the leaves
void fun(bool xTaken, int M)

{

     if(M==0)
     {
        count++; //We've reached the leaf
        return;
     }

     if(xTaken==false)
     {
        //We can take X
        fun(true,M-1);

        //or we can take Y
        fun(false,M-1);
     }

     else if(xTaken==true)
     {
        //We can only take Y
        fun(false,M-1);
     }

}

答えはcount*countになります。ここでも、メモ化を使用して重複する再帰を処理することで、この再帰を最適化できます。

于 2016-03-27T07:35:26.713 に答える
0

これが最も効率的な解決策かどうかはわかりませんが、次のようになります。特定の値 m に対して、必要な配置の総数は次のとおりです。

r=1;sum=0;

while(m>=r)
{

    sum+=mCr;

    m--;

    r++;

}

たとえば、m=7 ans= 7C1 + 6C2 + 5C3 + 4C4 の場合。

于 2016-09-15T09:48:00.967 に答える
0

複数のテスト ケースがある場合は、次のソリューションを使用します。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;

public class KohimaKing {

    static HashMap<Integer,BigInteger> fibboTerm = new HashMap<Integer,BigInteger>();
    public static void main(String[] args) throws Exception

    {
        fibboTerm.put(new Integer(0),new BigInteger("0"));
        fibboTerm.put(new Integer(1),new BigInteger("2"));
        fibboTerm.put(new Integer(2),new BigInteger("3"));
        Integer i=new Integer(3);
        for(;i<=1000;i++)
        {
            fibboTerm.put(i, fibboTerm.get(i-2).add(fibboTerm.get(i-1)));
        }


        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter sections");
        int m = Integer.parseInt(br.readLine());
        System.out.println(fibboTerm.get(m).multiply(fibboTerm.get(m)));

    }   
}
于 2015-04-24T12:58:54.713 に答える
-1 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;

public class KingKohima 
{

    public static void main(String[] args) throws Exception

    {
        BigInteger a = new BigInteger("2");
        BigInteger b = new BigInteger("3");
        BigInteger result = new BigInteger("0");


        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        if(m<=0)
        {
            System.out.println("0");
        }
        else if(m==1)
        {
            System.out.println("2");
        }
        else if(m==2)
        {
            System.out.println("3");
        }
        else
        {
            Integer i=new Integer(3);

            for(;i<=m;i++)
            {
                result = a.add(b);
                a=new BigInteger(b.toString());
                b=new BigInteger(result.toString());

            }
        }

        System.out.println(result.multiply(result));

    }

}
于 2015-04-24T12:55:31.500 に答える