Last active
April 8, 2018 15:02
-
-
Save pankgeorg/8a6c087521c31daf02d534e5912e22ec to your computer and use it in GitHub Desktop.
Codejam 2018 Qualification Round Problem 1a,b
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def reader(): | |
""" read the input from stdin """ | |
N = int(input()) | |
tcs = [] | |
for i in range(N): | |
(l, instructions) = input().split(" ") | |
tcs.append((int(l), instructions)) | |
return tcs | |
def damage(instructions): | |
""" Calculates the damage the spaceship will do given an instruction string """ | |
dmg = 0 | |
current = 1 | |
if instructions is None: | |
return 0 | |
for i in instructions: | |
if i == 'C': | |
current *=2 | |
else: | |
dmg += current | |
return dmg | |
def greedy_swap(instructions): | |
""" Replace instructions with new instructions, less harmful ones """ | |
rev = instructions[::-1] | |
if "SC" in rev: | |
return rev.replace("SC", "CS", 1)[::-1] | |
else: | |
# Return None to signify you can't do anything more | |
return None | |
def solver(D, instructions): | |
"""Solver""" | |
i = 0 | |
while instructions: | |
cost = damage(instructions) | |
if cost <= D: | |
# Either you managed to mitigate the damage | |
return i | |
instructions = greedy_swap(instructions) | |
i += 1 | |
# Or you can't | |
return "IMPOSSIBLE" | |
import sys | |
for i, (x, y) in enumerate(reader()): | |
print("Case #{}: {}".format(i, solver(x,y))) | |
sys.stdout.flush() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Codejam 2018 Qualification Round solution for Problem 1 (small + big)