TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

40.0% (2/5)

Tags

Description

Petya 在看完犯罪現場調查這題之後,決定自己也來練習看看。但是因為 Petya 在寫的時候沒有很認真思考,導致他寫出了錯誤的程式,在上傳之後得到了一個 WA。以下是他寫的程式:

#include <cstdio>

const int kMaxN = 1001, kInf = 100000001;
int x[kMaxN][kMaxN];

int main() {
  int N, M;
  scanf("%d%d", &N, &M);
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) x[i][j] = kInf;
  }
  for (int i = 0; i <= N; i++) x[i][i] = x[0][i] = 0;
  while (M--) {
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    if (-d < x[b][a]) x[b][a] = -d;
  }
  for (int k = 0; k <= N; k++) {
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= N; j++) {
        if (x[i][j] - x[i][k] > x[k][j]) x[i][j] = x[i][k] + x[k][j];
      }
    }
  }
  for (int i = 0; i <= N; i++) {
    if (x[i][i] < 0) {
      puts("-1");
      return 0;
    }
  }
  for (int i = 1; i <= N; i++) printf("%d\n", x[0][i]);
}

眼尖的你一眼就發現了 Petya 程式中的錯誤。為了幫助 Petya 讓他可以找到自己的錯誤,你決定產生許多不同 $N$ 值的測資,使得他的程式在每個測資中都輸出錯誤的答案,以方便他 debug。

Input Format

輸入只有一個正整數 $N$,代表要輸出的測資的 $N$ 值。保證一定存在符合條件的測資可以讓 Petya 的程式輸出錯誤的答案。

你上傳的程式碼大小必須在 1KiB 以內,否則你將獲得一個 WA

Output Format

請輸出一個符合上列題目 Input Format 且 $N$ 為指定值的測資,使得 Petya 的程式會輸出錯誤的答案。輸出格式請參見原題的輸入格式。

Sample Input

本題無範例輸入。

Sample Output

本題無範例輸出。

Hints

Problem Source

Problem Set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 20
8 7 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 32768 65536 1
1 500 32768 65536 2
2 500 32768 65536 3
3 500 32768 65536 4
4 500 32768 65536 5
5 500 32768 65536 6
6 500 32768 65536 7
7 500 32768 65536 8