pdf questions
Canadian Computing Competition: 2004 Stage 1, Senior #1
A collection of words is prefix-free if no word is a prefix of any other word. A collection of words is suffix-free if no word is a suffix of any other word. A collection of words is fix-free if it is both prefix-free and suffix-free.
For this problem, a word is a sequence of lower-case letters of length between and . A word is a prefix of word if consists of the first characters of , in order, for some . That is, the word cat has prefixes c, ca, and cat. Similarly, a word is a suffix of if consists of the last characters of , in order, for some .
Your input will be lines: the first line will be the number , and the remaining lines will be the collections of words each. (That is, lines , , and compose the first collection, lines , , and compose the second collection, and so on). Your output will be lines, each line containing either Yes (if that collection of words is fix-free) or No (if that collection is not fix-free).
Sample Input
2
abba
aab
bab
a
ab
aa
Sample Output
Yes
No
#Hints: Using python stirng find and rfind
txt = "welcome, welcome, welcome"
x = txt.find("welcome")
print(x) #0
x = txt.rfind("welcome")
print(x) #18
Problem S5: Super Plumber
You are to write a program to play a video game in which Super Plumber (SP) navigates
an obstacle course collecting prizes on the way to rescuing The Princess (TP).
The obstacle course is an m by n grid. SP starts at the bottom-left corner and makes his
way to TP in the bottom-right corner. Some of the grid locations are occupied by
obstacles through which SP cannot pass. Others are occupied by gold coins valued
between $1.00 and $9.00.
The game is a traditional scroll game, which means that SP can move only to the right,
up, or down. SP moves one grid location at a time, always to an adjacent location with no
obstacle. He cannot occupy any location which he previously occupied - if he moves up,
he cannot move down until he moves right; if he moves down he cannot move up until he
moves right. SP collects the gold coins at locations he visits. You are to find the
maximum possible total value of coins that SP can collect while rescuing TP.
Input has several test cases. The first line of each test case contains m and n, both integers
not less than 2 or greater than 100. The grid is then given as m lines with n characters
each. An obstacle is denoted by an asterisk ('*'); a coin is denoted by a digit ('1' through
'9'); an empty location is denoted by a period ('.').
It is always possible for SP to rescue TP. A line containing 0 0 follows the last test case.
Output one line for each test case giving the amount of money that SP can collect. The
sample input below contains two test cases. For the first case, SP can collect $27.00 with
the following sequence of moves: Up, Right, Down, Right, Right, Right, Right, Up,
Right, Right, Down, Right, Right. For the second case, SP can collect $34.00 with the
following sequence: Up, Right, Down.
Sample Input
5 10
..3.......
..........
..7.....
.9...1..
..8..9....
2 2
99
88
0 0
Sample Output
27
34
Answer 答案：
bruce force
'''
5 10
..3.......
..........
..7.**....
.9**...1..
..8..9....
2 2
99
88
0 0
'''
m, n = input().split()
m = int(m)
n = int(n)
lines = []
for i in range(1, m+1):
lines.append(input())
board = []
for r in range(0, m):
board.append([0 for c in range(0, n)])
for i in range(0, m):
for j in range(0,n):
if lines[i][j] == '.':
board[i][j] = 0
elif lines[i][j] == '*':
board[i][j] = -1
else:
board[i][j] = ord(lines[i][j]) - ord('0')
print()
print(m, n)
print(lines)
print(board)
results = []
def getGold(x, y):
return(max(0, board[x][y]))
def solve(x, y, gold, prevDir):
if x < 0 or x >= m or y < 0 or y>=n:
return
if board[x][y] == -1:
return
if x == m - 1 and y == n - 1:
results.append(gold + getGold(x,y))
return
gold = gold + getGold(x,y)
if prevDir == 'right':
solve(x - 1, y, gold, 'up')
solve(x + 1, y, gold, 'down')
solve(x, y+1, gold, 'right')
elif prevDir == 'up':
solve(x - 1, y, gold, 'up')
solve(x, y+1, gold, 'right')
else:
solve(x + 1, y, gold, 'down')
solve(x, y+1, gold, 'right')
solve(m-1, 0, 0, 'right')
print(max(results))
================================================================================================================================================================================================================================================================================================================================
bottom-up memorization(must faster)
'''
5 10
..3.......
..........
..7.**....
.9**...1..
..8..9....
2 2
99
88
0 0
'''
nInf = float('-inf')
m, n = input().split()
m = int(m)
n = int(n)
lines = []
for i in range(1, m+1):
lines.append(input())
board = []
for r in range(0, m+1):
board.append([0 for c in range(0, n+1)])
def getGold(x, y):
return(max(0, board[x][y]))
for i in range(0, m):
for j in range(0,n):
if lines[i][j] == '.':
board[i+1][j+1] = 0
elif lines[i][j] == '*':
board[i+1][j+1] = -1
else:
board[i+1][j+1] = ord(lines[i][j]) - ord('0')
'''
print()
print(m, n)
print(lines)
print(board)
'''
table = []
for r in range(0, m+2):
row = []
for c in range(0, n+1):
if r == 0 or r == m+1 or c == 0:
row.append([nInf, nInf, nInf])
else:
row.append([-1,-1,-1])
table.append(row)
table[m][0][0] = getGold(m,0)
table[m][0][1] = getGold(m,0)
table[m][0][2] = getGold(m,0)
#d = 0 for up, d = 1 for down, d = 2 right
UP = 0
DOWN = 1
RIGHT = 2
def solve(r, c, d):
if table[r][c][d] != -1:
return table[r][c][d]
elif board[r][c] == -1:
table[r][c][d] = nInf
return nInf
elif d == UP:
fromLeft = solve(r, c - 1, RIGHT)
fromBelow = solve(r + 1, c, UP)
table[r][c][d] = max(fromLeft, fromBelow) + getGold(r,c)
return table[r][c][d]
elif d == DOWN:
fromLeft = solve(r, c - 1, RIGHT)
fromAbove = solve(r - 1, c, DOWN)
table[r][c][d] = max(fromAbove, fromLeft) + getGold(r,c)
return table[r][c][d]
elif d == RIGHT:
fromLeft = solve(r, c - 1, RIGHT)
fromBelow = solve(r + 1, c, UP)
fromAbove = solve(r - 1, c, DOWN)
table[r][c][d] = max(fromLeft, fromBelow, fromAbove) + getGold(r,c)
return table[r][c][d]
print(max(solve(m,n,UP), solve(m,n,DOWN), solve(m,n,RIGHT)))