Skip to content

google codejam 예선

1번 문제 - reversort

input.txt

1
2
3
4
5
6
7
3
4
4 2 1 3
2
1 2
7
7 6 5 4 3 2 1

output.txt

1
2
3
Case #1: 6
Case #2: 1
Case #3: 12

내 풀이

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
sys.stdin = open("1\\input.txt")
T = int(input())

def reversort(l):
    cost = 0

    len_l = len(l)
    for i in range(len_l-1):
        min_idx = l.index(min(l))
        l[0:min_idx+1] = l[0:min_idx+1][::-1]
        cost_i = min_idx + 1
        cost += cost_i
        l.pop(0)
    return cost



for t in range(T):
    N = int(input())
    l = list(map(int, input().split()))
    cost = reversort(l)
    print("Case #%d: %d" % (t+1, cost))

2번 문제

input.txt

1
2
3
4
5
4
2 3 CJ?CC?
4 2 CJCJ
1 3 C?J
2 5 ??J???

output.txt

1
2
3
4
Case #1: 5
Case #2: 10
Case #3: 1
Case #4: 0

내 풀이

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import sys
sys.stdin = open("2\\input.txt")

T = int(input())

for t in range(T):
    X, Y, ARR = input().split()
    X = int(X)
    Y = int(Y)
    cost = 0
    ARR = ARR.replace("?", "")
    for i in range(len(ARR)):
        if ARR[i:i+2] == "CJ":
            cost += X
        elif ARR[i:i+2] == "JC":
            cost += Y
    print("Case #%d: %d" % (t+1, cost))

3번 문제

input.txt

1
2
3
4
5
6
5
4 6
2 1
7 12
7 2
2 1000

output.txt

1
2
3
4
5
Case #1: 4 2 1 3
Case #2: 1 2
Case #3: 7 6 5 4 3 2 1
Case #4: IMPOSSIBLE
Case #5: IMPOSSIBLE

내 풀이

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import sys
sys.stdin = open("3\\input.txt")

T = int(input())

for t in range(T):
    rslt = None
    len_l, cost = map(int, input().split())
    max_cost = (len_l*(len_l+1))//2 - 1
    min_cost = len_l - 1
    if cost > max_cost:
        rslt = "IMPOSSIBLE"
    elif cost < min_cost:
        rslt = "IMPOSSIBLE"
    else:
        cost -= (len_l - 1)
        left_l = []
        right_l = []
        mid_l = []
        is_max_order = True
        cur_val = 1
        cost_to_be_used = len_l-1
        while (cost >= cost_to_be_used) and (cost_to_be_used > 0):
            if is_max_order:
                right_l = [cur_val] + right_l
            else:
                left_l.append(cur_val)
            cur_val += 1
            cost -= cost_to_be_used
            cost_to_be_used -= 1
            is_max_order = not is_max_order
        if is_max_order:
            mid_l = list(range(cur_val, len_l+1))
        else:
            mid_l = list(range(cur_val, len_l+1))[::-1]
        if cost > 0:
            mid_l[:cost+1] = mid_l[:cost+1][::-1]

        rslt = left_l + mid_l + right_l
        rslt = ' '.join(map(str, rslt))

    print("Case #%d: %s" % (t+1, rslt))

4, 5번 문제는 skip...

(본선 1A는 4월 10일 예정입니다...)