GCJ 2017 Qual A. Oversized Pancake Flipper ( Greedy )

Dashboard - Qualification Round 2017 - Google Code Jam

題意：
給一個由 '+', '-' 組成的序列。問能不能透過任意次操作將該序列全部元素變成 '+'。操作只有一種，將連續 K 個元素內容反轉。

制約：
1 ≤ T ≤ 100.
Every character in S is either + or -.
2 ≤ K ≤ length of S.
2 ≤ length of S ≤ 1000.

解法：
由於操作的順序不重要，所以可以由左到右不回頭決定，顯然遇到左界為 '+' 就不能在這裡操作，反之就必須操作。

時間 / 空間複雜度：
O( S )

T = int( input() )
for ti in range( 1, T + 1, 1 ):
  S, K = map( str, input().split( ' ' ) )
  S = list( S )
  K = int( K )
  ans = 0
  for i in range( len( S ) - K + 1 ):
    if S[ i ] == '+': continue
    ans += 1
    for j in range( i, i + K, 1 ):
      if S[ j ] == '+':
        S[ j ] = '-'
      else:
        S[ j ] = '+'
  for i in range( len( S ) ):
    if S[ i ] == '-':
      ans = -1
      break
  if ans == -1:
    print( "Case #%d: IMPOSSIBLE" % ti )
  else:
    print( "Case #%d: %d" % ( ti, ans ) )