15

テニストーナメントの後、各選手は何試合したか尋ねられました。アスリートは、別のアスリートと複数の試合をすることはできません。入力として得られるのは、アスリートの数と各アスリートの試合数だけです。出力として、アスリートの回答に従ってトーナメントを行うことができた場合は 1、そうでない場合は 0 になります。例えば:

Input: 4 3 3 3 3      Output: 1  
Input: 6 2 4 5 5 2 1  Output: 0  
Input: 2 1 1          Output: 1  
Input: 1 0            Output: 0  
Input: 3 1 1 1        Output: 0  
Input: 3 2 2 0        Output: 0  
Input: 3 4 3 2        Output: 0  

入力の最初の数字は、アスリートの回答の一部ではありません。これは、トーナメントに参加したアスリートの数です。 1.

これまでのところ、これは私たちが書いたものですが、それほどうまくいきませんでした:

import java.util.Scanner;
import java.util.Arrays;

public class Tennis {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        String N;
        int count;
        int sum = 0;
        int max;
        int activeAthletes;
        int flag;

        System.out.printf("Give: ");
        N = input.nextLine();

        String[] arr = N.split(" ");
        int[] array = new int[arr.length];

        for (count = 0; count < arr.length; count++) {
            array[count] = Integer.parseInt(arr[count]);
            //System.out.print(arr[count] + " ");
        }

        for (count = 1; count < arr.length; count++) {
            sum += array[count];
        }
        //System.out.println("\n" + sum);

        activeAthletes = array[0];

        for (count = 1; count < array.length; count++) {
            if (array[count] == 0) {
                activeAthletes--;
            }
        }

        max = array[1];
        for (count = 2; count < array.length; count++) {
            if (array[count] > max) {
                max = array[count];
            }
        }
       // System.out.println(max);

        if ((sum % 2 == 0) && (max < activeAthletes)) {            
            flag = 1;
        } else{
            flag = 0;
        }

        System.out.println(flag);
    }
}

他に何をすべきか本当にわからないので、繰り返しますが、宿題としてタグ付けしますが(モデレーターが再び閉じると思うため)、そうではありません、それは私の兄弟が見つけたものであり、私たちは解決しようとしています.

多くの方から回答をいただき、本当に感謝していますが、明日仕事があるので寝なければならないので、明日残りの回答を読んで何がうまくいくか見てみようと思います。

4

5 に答える 5

7

100% うまくいくかどうかわからないので、次のようにします。

  1. 入力の並べ替え
  2. 配列内の各要素が右から左へ (大きい方から小さい方へ)

    • インデックス i の要素の値 n に基づいて、左の n 個の要素を 1 減らします
    • リストの最後または値 0 に達したために減少できない場合は失敗を返します
  3. 成功を返します。

このロジック (正しければ) は、O(N*log(N)) ソリューションにいくつかの変更を加えることができますが、初心者のプログラマーにとっては多すぎると私は現在考えています。

編集:

これは入力では正しく機能しません
2 2 1 1

すべての手順は次のとおりです (並べ替えなし)。

  1. 一方、リスト L の任意の要素は 0 ではありません:

    • リスト L で最大の要素 N を見つける
    • 値 >= 1 の場合、リスト L 内の N 個の他の値を 1 減らします (この最大要素を減らさないでください)
      • このステップで失敗した場合は失敗を返します
    • この要素 N を 0 に設定します
  2. 返品OK

于 2012-04-25T21:40:48.320 に答える
5

ここにヒントがあります。これらの質問に答えなさい

  1. N 人の選手がいる場合、試合の最大数はいくつですか?
  2. アスリート X が与えられた場合、彼ができる最大試合数は?
  3. これらだけをチェックするにはこれで十分ですか?確信が持てない場合は、可能なすべてのプレイヤーのマッチングを生成し、少なくとも 1 つのプレイヤーが入力を満たすかどうかを確認するプログラムを作成してみてください。これは少数のアスリートにしか機能しませんが、良い練習になります。または、手でそれを行う

この質問を別の方法で尋ねると、行が値と等しい 1 と 0 の対称行列を作成できますか。これが「誰が誰を演じたか」の表になります。これを N x N グリッドのように考えてください。ここで、grid[i][j] = grid[j][i] (あなたが誰かと対戦する場合、その人はあなたと対戦します) および grid[i][i] = 0 (誰も自分自身をプレイしません)

例えば

Input: 4 3 3 3 3 Output: 1

のように見える

 0 1 1 1
 1 0 1 1
 1 1 0 1
 1 1 1 0 

ただし、これではこれを行うことはできません: 入力: 3 2 2 0 出力: 0

編集

これはこれと等価です ( Degree (グラフ理論)より)

Hakimi (1962) は、(d1, d2, ..., dn)が単純グラフの次数列であることを証明しました(d2 − 1, d3 − 1, ..., dd1+1 − 1, dd1+ 2, dd1+3, ..., dn)です。この事実は、与えられた実現可能な次数シーケンスを持つ単純なグラフを見つけるための単純なアルゴリズムにつながります。

  1. エッジのないグラフから始めます。
  2. 次数要件がまだ満たされていない頂点のリストを、残りの次数要件の昇順でない順序で維持します。
  3. 最初の頂点をこのリストの次のd1頂点に接続し、リストから削除します。リストを並べ替え、すべての学位要件が満たされるまで繰り返します。

特定の次数列を持つグラフの数を見つけたり推定したりする問題は、グラフ列挙の分野の問題です。

于 2012-04-25T20:50:11.017 に答える
2

おそらく、アスリートの試合数の配列を取り、そこにある最大数を決定できます。

次に、その数を 1 に分割し、それらの 1 を配列の他のいくつかのメンバーから差し引くことができるかどうかを確認します。

その最大数の配列メンバーをゼロにして配列から削除し、値を減らして他のメンバーを更新します。

次に、プロセスを繰り返します。新しい最大数を決定し、それを配列の他のメンバーから減算します。

任意の時点で、1 を減算するのに十分な配列メンバーがない場合は、アプリに 0 を返させます。それ以外の場合は、配列内のメンバーがなくなるまでそれを続けます。その時点で、アプリに 1 を返させることができます。

また、ゼロまで削減された配列メンバーを削除することを忘れないでください。

于 2012-04-25T20:54:30.017 に答える
0

編集:以下のソリューションは、無効な入力を有効なものとして渡します。これは確実な陰性を確認するための迅速な方法ですが、誤検出を許してしまいます。


数学者が提案するものは次のとおりです。

  1. 一致数の合計は偶数でなければなりません。3 3 4 2 1これは、誰か13が自分自身と対戦したことを意味します。
  2. プレーヤーの場合、すべての試合で 1 人のプレーヤーが脱落する場合n、少なくともn-1個別の試合を行う必要があります。(ノックアウト トーナメント。) これを確認するには、2、4、8、16、32... 人のプレーヤーのマッチの木を描きます。勝者を決めるには 1、3、7、31... のマッチが必要です。
  3. プレーヤーの場合n、繰り返しの試合がないと仮定して、全員が全員と 1 回対戦した場合の最大試合数はn choose 2、または(n!)/(2!)(n-2)!(総当りトーナメント) です。n!は階乗関数 ですn! = n * n-1 * n-2 * ... * 3 * 2 * 1.

したがって、基準は次のとおりです。

  1. 一致数の合計は偶数でなければなりません。
  2. 一致数の合計は少なくとも である必要があります2n-2。(2 の掛け算に注意してください。試合ごとに、両方のプレイヤーのカウントが 1 ずつ増えます。)
  3. 一致数の合計は最大で でなければなりません2 * n choose 2
  4. [編集] 各プレイヤーは、少なくとも 1 つの試合に参加する必要があります。

トーナメントがノックアウト トーナメントとラウンド ロビン トーナメントのクロスである場合、 と の中間のどこかで試合を行うことができn-1ますn choose 2

編集:

以上のn-1マッチをプレイしたプレイヤーがいる場合、そのプレイヤーは誰かと少なくとも 2 回対戦したことになります。

トーナメントがノックアウト トーナメントであり、各プレイヤーが参加する試合数をできるだけ少なくするように設定されている場合、各プレイヤーは最大で2log_2(n)試合程度しか参加できません (log基本 2 を切り上げます)。一致します。1024 人のプレイヤーが参加するトーナメントでは、最大 10 試合。

于 2012-04-25T20:57:17.920 に答える
0

あなたの例はすべて、一致を数えて2で割るかどうかを調べることで簡単に解決できます.

あなたの例でカバーされていない問題は、他のプレイヤーの合計よりも多くのゲームを持っているプレイヤーです:

  • 入力: 4 5 1 1 1 出力: 0

さらにプレイヤーを追加すると、これは複雑になる可能性があります。

  • 入力: 6 5 5 5 1 1 1 出力: 0

この質問を解決するにはどうすればよいですか?さて、最大プレイヤーと最小プレイヤーからペアごとに 1 つのゲームを削除し、何が起こるか見てみましょう。

  • 入力: 6 5 5 5 1 1 1
  • 入力: 5 5 5 4 1 1 -
  • 入力: 4 5 4 4 1 - -
  • 入力: 3 4 4 4 - - -

次のルールに違反しています。

アスリートは、別のアスリートと複数の試合をすることはできません。

3 人のプレーヤーが残っている場合、それぞれが 2 ゲームを超えることはできません。

于 2012-04-25T21:42:53.620 に答える