3

私は Python を初めて使用し、Kingdom Connectivity のインタビューストリートの問題を解決しようとしていました。なんとか問題を解決できましたが、指定された形式の入力に問題があり、システムでソリューションを試してみましたが、出力は正しいですが、そこでコンパイルするとすぐに出力がありません。

入力は次の形式です。

5 5
1 2
2 3
3 4
1 3
4 5

この問題を解決する方法を教えてください。

現在、raw_input()ループ内から入力を取得し、 を使用して分割していa.split(' ')ます。

ここに質問の一部があります:

**Input Description:**

First line contains two integers N and M.

Then follow M lines ,each having two integers say x and y, 1<=x,y<=N , indicating there is a road from city x to city y.

**Output Description:**

Print the number of different paths from city 1 to city N modulo 1,000,000,000(10^9).If there are infinitely many different paths print "INFINITE PATHS"(quotes are for clarity).

**Sample Input:**

5 5
1 2
2 4
2 3
3 4
4 5

**Sample Output:**

2

**Sample Input:**

5 5
1 2
4 2
2 3
3 4
4 5

**Sample Output:**

INFINITE PATHS

これが私の解決策です

import sys
import numpy as np
c=0
x=raw_input()
y=x.split(' ')
l=(int(y[0]),int(y[1]))
e=[raw_input() for i in range(l[1])]
f=[e[i].split(' ') for i in range(l[1])]
a=[map(int,i) for i in f]
b=[[0 for i in a] for j in range(l[0])]
for i in range(l[0]+1):
    for j in range(l[0]+1):
        if [i,j] in a:
            b[i-1][j-1]=1
        elif a[i-1][0]>=a[i-1][1]:
            print "INFINITE PATHS"
            sys.exit(0)
for i in range(0,l[1]): 
    d=np.linalg.matrix_power(b,i+1)
    c+=d[0][l[1]-1]   
print c

ここにスクリーンショットがあります ここに画像の説明を入力

4

3 に答える 3

3

あなたのプログラムは理解しにくいと思いました。それで、書き直して、私のバージョンの方が少し分かりやすいと思います。

import sys
import numpy as np


line = raw_input()
max_val, num_paths = (int(n) for n in line.split())


# a will be a list of tuples of int, taken from the input.
#
# Each tuple represents a path, so this is effectively a sparse representation
# of a square matrix of possible paths.
#
# Input city numbers are 1-based, but we will treat them as 0-based, so
# subtract 1 from each value before appending to array a.

a = []
for _ in xrange(num_paths):
    line = raw_input()

    # TRICKY: subtract 1 to convert from 1-based to 0-based city numbers
    tup = tuple(int(n)-1 for n in line.split())

    if len(tup) != 2:
        raise ValueError, "input should only have two values per line"
    for n in tup:
        if not 0 <= n < max_val:
            raise ValueError, "value must be in range [1, %d]" % max_val
        if tup[0] >= tup[1]:
            #raise ValueError, "INFINITE PATHS"
            print "INFINITE PATHS"
            sys.exit(0)
    a.append(tup)


# Expand the sparse matrix representation into an actual square matrix.
# It should have a 1 anywhere a path was indicated with a tuple in list a,
# and a 0 everywhere else.
b = [ [0 for _ in xrange(max_val)] for _ in xrange(max_val)]
for i, j in a:
    b[i][j] = 1


c = 0
for i in xrange(num_paths):
    d = np.linalg.matrix_power(b, i + 1)
    c += d[0][max_val - 1]
print c

入力例を指定すると、私のバージョンは印刷2されます。

これに取り組んでいるときにわかったことがいくつかあります。

最初の行は定数を示します (ドキュメントNMは、それぞれ有効な最大値とパスの数を表します)。これらの値をリストに入れてリスト インデックスで参照するのではなく、適切な名前を付けて変数に保存する必要があります。と の名前を使用しましmax_valnum_paths。あなた自身が間違いを犯しました: 都市 1 から都市 N へのパスを見つけることになっているので、最後のチェックはd[0][max_val - 1];になるはずです。ではなくどちらを使用しましl[1]たか。num_pathsl[0]

b正方行列でなければなりません。あなたのコードは の長さに基づいて幅を設定していましたaが、常に等しいmax_valnum_pathsは限らないため、これは危険な方法です。

正方行列のすべての可能な点をループして、1 として設定する必要があるかどうかを確認するのは奇妙です。また、特にinテストが O(n) であり、 n が配列の長さであるため、非常に非効率的aです。代わりに、空の正方行列を構築し、パスをループして、パスごとに 1 の値を設定します。

同様に、正方行列を初期化するループで入力値を検証するのは奇妙です。入力ループで読み取られるときに入力値を検証することをお勧めします。num_pathsまた、 とは無関係かもしれないので危険max_valです。また、列ごとに1回チェックa[i-1][0]していたため、非効率的です。その比較では、値はまったく使用されません。各チェックを 5 回行っていました。各チェックを 1 回行うだけで十分です。a[i-1][1]bj

私が使用した Python イディオムがあり_ます。変数の値を気にしない場合は、変数の名前として (単一のアンダースコア) を使用できます。ループで特定の回数だけ何かを実行していて、ループ カウンター値を何にも使用しない場合は_、ループ カウンター変数として a を使用しました。もちろん、これは必須ではありません。

あなたの実際の質問に答えるには:あなたのプログラムが出力を生成しない方法はありません。このテスト問題を実行するサーバーに問題があるのではないかと思います。あなたのプログラムは、常に "INFINITE PATHS" を出力するか、何らかの整数値を出力する必要があります。

PS私はあなたのプログラムがどのように機能するかを実際には理解していません。問題の説明には、1e9 を法とする多数のパスを提供する必要があると書かれていますが、それを強制するものは何もありません。

于 2012-03-20T00:25:20.860 に答える
1

指定された入力は次のように読み取ることができます。

line = raw_input()
n, m = map(int, line.split())

for _ in range(m):
  line = raw_input()
  x, y = map(int, line.split())
  print x, y
于 2012-03-19T22:12:06.317 に答える
0

スクリプトと同じフォルダーにあるファイル input.txt に入力がある場合:

with open("input.txt") as f:
    l = [int(i) for i in f.readline().split(" ")]
    a = []
    for line in f.readlines():
        a.append([int(i) for i in line.strip().split(" ")])
print(l, a)

入力がコマンドライン引数として渡される場合:

import sys
input_string = sys.argv[1]
print(input_string) # test if this prints the input
...
于 2012-03-19T22:34:06.297 に答える