QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #59504 | #3491. Meow Factor 2 | yahoco | TL | 13ms | 6780kb | Python2 | 511b | 2022-10-29 19:32:42 | 2022-10-29 19:33:40 |
Judging History
answer
P = 'meow'
S = raw_input()
n = len(S)
opt = [i % 5 for i in range(5*(n+1))]
ans = 4
for i in range(n):
for j in range(4):
opt[5*(i+1)+j+1] = min(opt[5*i+j+1] + 1, # del
opt[5*(i+1)+j] + 1, # ins
opt[5*i+j] + (S[i] != P[j])) # sub
if i > 0 and j > 0 and S[i] == P[j-1] and S[i-1] == P[j]: # swap
opt[5*(i+1)+j+1] = min(opt[5*(i+1)+j+1], 1 + opt[5*(i-1)+j-1])
ans = min(ans, opt[5*(i+1)+4])
print ans
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 6572kb
input:
pastimeofwhimsy
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 5ms
memory: 6732kb
input:
yarn
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 7ms
memory: 6696kb
input:
meow
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 13ms
memory: 6780kb
input:
z
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 6ms
memory: 6732kb
input:
o
output:
3
result:
ok single line: '3'
Test #6:
score: -100
Time Limit Exceeded
input:
meomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeomeo...