結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー mudbdb
提出日時 2015-06-20 02:45:32
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 45 ms / 5,000 ms
コード長 2,063 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 22,528 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 15:33:33
合計ジャッジ時間 1,117 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘player1’:
main.c:46:16: warning: implicit declaration of function ‘player2’; did you mean ‘player1’? [-Wimplicit-function-declaration]
   46 |           rc = player2(N - Pr[i]);
      |                ^~~~~~~
      |                player1
main.c: In function ‘main’:
main.c:103:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  103 |   scanf("%d", &N);
      |   ^~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
int Pr_end = 0;
int *Pr = 0;
int pr_gen(int N)
{
  int i, j;
  char *chk = (char*)malloc(sizeof(char)*(N+1));
  for (i=0; i<=N; i++) chk[i] = 1;
  chk[0] = 0;
  chk[1] = 0;
  for (i=2; i<=N; i++) {
    if (chk[i] == 1) {
      for (j=i*2; j<=N; j+=i) chk[j] = 0;
      Pr_end++;
    }
  }
  Pr = (int*)malloc(sizeof(int)*Pr_end);
  Pr_end = 0;
  for (i=0; i<=N; i++) {
    if (chk[i] == 1) {
      Pr[Pr_end] = i;
      Pr_end++;
    }
  }
  free(chk);
  chk = 0;
  return 0;
}
char *Play1 = 0;
char *Play2 = 0;
int player1(int N)
{
  int rc = 0;  // (rc = 1 -> win) (rc = -1 -> lose)
  if (Play1[N] != 0) {
    rc = Play1[N];
  } else {
    if (N == 0 || N == 1) {
      rc = 1;
    } else {
      int i;
      int win = 0;
      int lose = 0;
      for (i=0; i<Pr_end; i++) {
        if (N - Pr[i] >= 0) {
          rc = player2(N - Pr[i]);
          if (rc == 1) {
            win++;
          } else {
            lose++;
          }
        } else {
          break;
        }
      }
      if (lose >= 1) {
        rc = 1;
      } else {
        rc = -1;
      }
    }
    Play1[N] = rc;
  }
  return rc;
}
int player2(int N)
{
  int rc = 0;
  if (Play2[N] != 0) {
    rc = Play2[N];
  } else {
    if (N == 0 || N == 1) {
      rc = 1;
    } else {
      int i;
      int win = 0;
      int lose = 0;
      for (i=0; i<Pr_end; i++) {
        if (N - Pr[i] >= 0) {
          rc = player1(N - Pr[i]);
          if (rc == 1) {
            win++;
          } else {
            lose++;
          }
        } else {
          break;
        }
      }
      if (lose >= 1) {
        rc = 1;
      } else {
        rc = -1;
      }
    }
    Play2[N] = rc;
  }
  return rc;
}
int main()
{
  int N;
  scanf("%d", &N);

  pr_gen(N);

  Play1 = (char*)malloc(sizeof(char)*(N+1));
  Play2 = (char*)malloc(sizeof(char)*(N+1));
  int i;
  for (i=0; i<(N+1); i++) Play1[i] = 0;
  for (i=0; i<(N+1); i++) Play2[i] = 0;
  int rc = player1(N);

  if (rc == 1) {
    printf("Win\n");
  } else {
    printf("Lose\n");
  }
  return 0;
}
0