How to read multiple lines in python

I realized that your program is difficult to understand. So I rewrote it and I think my version is a little self-explanatory.

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

      

        
        
        
      

    

My version prints 2

as I enter the example.

Here are some things I figured out when I was working on this:

The first line gives us constants ( N

and M

in the documentation, representing the maximum legal value and the number of paths, respectively). These values ​​should be stored in well-named variables, not put in a list and referenced by the index of the list. I have used names max_val

and num_paths

. You yourself made a mistake: you must find the paths from city 1 to city N, so there should be a check at the end d[0][max_val - 1]

; you used l[1]

which num_paths

, not l[0]

.

b

should be a square matrix. Your code was setting the width depending on the length a

, but max_val

they num_paths

may not always be equal, so this is a dangerous way to do it.

It's weird to iterate over every possible point of a square matrix and check if it should be set to 1 or not. It's also very inefficient, especially since the test in

is O (n), where n is the length of the array a

. Instead, create an empty square matrix and then just loop through the paths and set the values ​​to 1 for each path.

Likewise, it is weird to check input values ​​in a loop that initializes a square matrix; it is better to check the input values ​​as they are read in the input loop. Again, this is dangerous because it num_paths

may not be related to max_val

. Also, it is inefficient, because you checked a[i-1][0]

on a[i-1][1]

once a column in b

; this comparison uses no value at all j

. You have made each check five times; it is sufficient to perform each check once.

There is a Python idiom I have used where you can use _

(one underscore) as a variable name when you don't care about the value of that variable. When we just do something a certain number of times with a loop, and we will not use the value of the loop counter for something, I used it _

as a loop counter variable. Of course, this is not necessary.

To answer your real question: I see no way for your program to produce no output. I suspect there may be an issue on the server that triggers this test issue. Your program should always either print "INFINITE PATHS" or some integer value.

PS I don't understand how your program works; the problem description says that you must specify multiple paths mod 1e9, and I see nothing to provide this.