• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
54%
SHARE
TWEET

# byteland-3-check.py

a guest Mar 6th, 2013 172 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. """
2. This program will verify a solution to Bytelandian Exchange 3. To use:
3.
4.  python byteland-3-check.py < solution.txt
5.
6. If the program executes with no assertion errors, your solution is correct.
7.
8. The first line of the file is two integers N and p, with N = the number of the coin you start
9.  with and p = the smallest coin that Machine #1 will output. (For the basic challenge, p = 1,
10.  and for the Bonus, p = 2.)
11. Each line after the first is a single number that represents an exchange:
12.  -N means to put a coin with a value of N into Machine #1.
13.      This will add three coins valued N/2, N/3, and N/4 to your collection.
14.  N means to put a coin with a value of N into Machine #2, along with your smallest-valued coin
15.      with a value of at least p. This will add a coin with a value of N+1 to your collection.
16.
17. For example, the input might start like this:
18. 897 1
19. -897
20. -224
21. -56
22. -14
23. -3
24. 299
25. 300
26.
27. This represents 5 uses of Machine #1 followed by 2 uses of Machine #2. At this point, the coins
28. you have will be: 448 301 112 74 28 18 7 4
29.
30. At the end you must have at least 2 coins worth >= p, one of which is worth >= N.
31. """
32.
33. import sys, collections
34.
35. lines = list(sys.stdin)
36. N, p = map(int,lines[0].split())
37. coins = collections.Counter()
38. coins[N] = 1
39. for line in lines[1:]:
40.         n = int(line)
41.         assert abs(n)
42.         if n < 0:
43.                 # Use Machine 1
44.                 n = -n
45.                 assert coins[n]
46.                 coins[n] -= 1
47.                 coins[n//2] += 1
48.                 coins[n//3] += 1
49.                 coins[n//4] += 1
50.         else:
51.                 # Use Machine 2
52.                 m = min(coin for coin in coins if coins[coin])
53.                 assert coins[n]
54.                 assert coins[m]
55.                 coins[n] -= 1
56.                 coins[m] -= 1
57.                 if n == m:
58.                         assert coins[n] >= 0
59.                 coins[n+1] += 1
60.         # Throw out useless coins
61.         for n in coins:
62.                 if n < p:
63.                         coins[n] = 0
64.         print("%s | %s" %
65.                 (line.strip(),
66.                 " ".join(map(str, sorted(list(coins.elements()), reverse=True))))
67.         )
68. largest = max(coin for coin in coins if coins[coin])
69. ncoins = sum(coins.values())
70. assert largest >= N and ncoins > 1
RAW Paste Data
Top