|
|
@@ -0,0 +1,248 @@ |
|
|
{ |
|
|
"cells": [ |
|
|
{ |
|
|
"cell_type": "code", |
|
|
"execution_count": 13, |
|
|
"metadata": {}, |
|
|
"outputs": [ |
|
|
{ |
|
|
"name": "stdout", |
|
|
"output_type": "stream", |
|
|
"text": [ |
|
|
"1 (0, 1, 1)\n", |
|
|
"2 (1, 1, 3)\n", |
|
|
"3 (1, 2, 3)\n", |
|
|
"4 (2, 1, 7)\n", |
|
|
"5 (2, 2, 7)\n", |
|
|
"6 (2, 3, 7)\n", |
|
|
"7 (2, 4, 7)\n", |
|
|
"8 (3, 1, 15)\n", |
|
|
"9 (3, 2, 15)\n", |
|
|
"10 (3, 3, 15)\n" |
|
|
] |
|
|
} |
|
|
], |
|
|
"source": [ |
|
|
"def getLevelPositionCurrsum(n):\n", |
|
|
" c = 0\n", |
|
|
" total = 0\n", |
|
|
" i = 1;\n", |
|
|
" while total <= n:\n", |
|
|
" total += i\n", |
|
|
" if total >= n:\n", |
|
|
" return (c, n + i - total, total)\n", |
|
|
" c += 1\n", |
|
|
" i *= 2\n", |
|
|
" \n", |
|
|
" return (0, 0, 0)\n", |
|
|
"\n", |
|
|
"for i in range(1, 11):\n", |
|
|
" print i, getLevelPositionCurrsum(i)" |
|
|
] |
|
|
}, |
|
|
{ |
|
|
"cell_type": "code", |
|
|
"execution_count": 21, |
|
|
"metadata": { |
|
|
"collapsed": true |
|
|
}, |
|
|
"outputs": [], |
|
|
"source": [ |
|
|
"def solution(n, k):\n", |
|
|
" (l, p, cs) = getLevelPositionCurrsum(k)\n", |
|
|
" stalls = n - cs\n", |
|
|
" c = 2 ** l\n", |
|
|
" if stalls % c == 0:\n", |
|
|
" lrs = stalls / c\n", |
|
|
" if lrs % 2 == 0:\n", |
|
|
" return (lrs / 2, lrs / 2)\n", |
|
|
" else:\n", |
|
|
" return ((lrs + 1) / 2, (lrs - 1) / 2)\n", |
|
|
" else:\n", |
|
|
" re = stalls % c\n", |
|
|
" lrs = stalls / c\n", |
|
|
" if lrs % 2 == 0:\n", |
|
|
" if p <= re:\n", |
|
|
" return (lrs / 2 + 1, lrs / 2)\n", |
|
|
" else:\n", |
|
|
" return (lrs / 2, lrs / 2)\n", |
|
|
" else:\n", |
|
|
" if p <= re:\n", |
|
|
" return ((lrs + 1) / 2, (lrs + 1) / 2)\n", |
|
|
" else:\n", |
|
|
" return ((lrs + 1) / 2, (lrs - 1) / 2)\n", |
|
|
" \n", |
|
|
" \n", |
|
|
" " |
|
|
] |
|
|
}, |
|
|
{ |
|
|
"cell_type": "code", |
|
|
"execution_count": 36, |
|
|
"metadata": {}, |
|
|
"outputs": [], |
|
|
"source": [ |
|
|
"def sol(inputFile):\n", |
|
|
" res = ''\n", |
|
|
" with open(inputFile) as f:\n", |
|
|
" lineNumber = int(f.readline())\n", |
|
|
" for i in range(lineNumber):\n", |
|
|
" line = f.readline()\n", |
|
|
" n = int(line.split(' ')[0])\n", |
|
|
" k = int(line.split(' ')[1])\n", |
|
|
" (a, b) = solution(n, k)\n", |
|
|
" res += 'Case #' + str(i + 1) + ': ' + str(a) + ' ' + str(b) + '\\n'\n", |
|
|
" with open(inputFile.replace('.in', '.out'), 'w') as fo:\n", |
|
|
" fo.write(res)\n", |
|
|
" return res" |
|
|
] |
|
|
}, |
|
|
{ |
|
|
"cell_type": "code", |
|
|
"execution_count": 45, |
|
|
"metadata": {}, |
|
|
"outputs": [ |
|
|
{ |
|
|
"name": "stdout", |
|
|
"output_type": "stream", |
|
|
"text": [ |
|
|
"Case #1: 1 0\n", |
|
|
"Case #2: 1 0\n", |
|
|
"Case #3: 1 1\n", |
|
|
"Case #4: 0 0\n", |
|
|
"Case #5: 500 499\n", |
|
|
"Case #6: 0 0\n", |
|
|
"Case #7: 1 0\n", |
|
|
"Case #8: 0 0\n", |
|
|
"Case #9: 0 0\n", |
|
|
"Case #10: 3 3\n", |
|
|
"Case #11: 0 0\n", |
|
|
"Case #12: 1 0\n", |
|
|
"Case #13: 7 6\n", |
|
|
"Case #14: 1 0\n", |
|
|
"Case #15: 1 0\n", |
|
|
"Case #16: 0 0\n", |
|
|
"Case #17: 0 0\n", |
|
|
"Case #18: 1 1\n", |
|
|
"Case #19: 0 0\n", |
|
|
"Case #20: 1 0\n", |
|
|
"Case #21: 1 0\n", |
|
|
"Case #22: 0 0\n", |
|
|
"Case #23: 3 2\n", |
|
|
"Case #24: 1 1\n", |
|
|
"Case #25: 0 0\n", |
|
|
"Case #26: 0 0\n", |
|
|
"Case #27: 1 0\n", |
|
|
"Case #28: 0 0\n", |
|
|
"Case #29: 0 0\n", |
|
|
"Case #30: 1 0\n", |
|
|
"Case #31: 249 249\n", |
|
|
"Case #32: 0 0\n", |
|
|
"Case #33: 1 1\n", |
|
|
"Case #34: 1 0\n", |
|
|
"Case #35: 0 0\n", |
|
|
"Case #36: 0 0\n", |
|
|
"Case #37: 0 0\n", |
|
|
"Case #38: 1 0\n", |
|
|
"Case #39: 1 1\n", |
|
|
"Case #40: 0 0\n", |
|
|
"Case #41: 0 0\n", |
|
|
"Case #42: 0 0\n", |
|
|
"Case #43: 1 0\n", |
|
|
"Case #44: 7 6\n", |
|
|
"Case #45: 1 1\n", |
|
|
"Case #46: 250 249\n", |
|
|
"Case #47: 0 0\n", |
|
|
"Case #48: 1 1\n", |
|
|
"Case #49: 0 0\n", |
|
|
"Case #50: 0 0\n", |
|
|
"Case #51: 0 0\n", |
|
|
"Case #52: 0 0\n", |
|
|
"Case #53: 3 2\n", |
|
|
"Case #54: 499 499\n", |
|
|
"Case #55: 3 2\n", |
|
|
"Case #56: 0 0\n", |
|
|
"Case #57: 0 0\n", |
|
|
"Case #58: 0 0\n", |
|
|
"Case #59: 1 0\n", |
|
|
"Case #60: 250 249\n", |
|
|
"Case #61: 1 0\n", |
|
|
"Case #62: 0 0\n", |
|
|
"Case #63: 0 0\n", |
|
|
"Case #64: 0 0\n", |
|
|
"Case #65: 0 0\n", |
|
|
"Case #66: 0 0\n", |
|
|
"Case #67: 125 124\n", |
|
|
"Case #68: 1 1\n", |
|
|
"Case #69: 0 0\n", |
|
|
"Case #70: 0 0\n", |
|
|
"Case #71: 0 0\n", |
|
|
"Case #72: 0 0\n", |
|
|
"Case #73: 0 0\n", |
|
|
"Case #74: 3 3\n", |
|
|
"Case #75: 1 0\n", |
|
|
"Case #76: 1 1\n", |
|
|
"Case #77: 0 0\n", |
|
|
"Case #78: 3 3\n", |
|
|
"Case #79: 0 0\n", |
|
|
"Case #80: 2 1\n", |
|
|
"Case #81: 0 0\n", |
|
|
"Case #82: 0 0\n", |
|
|
"Case #83: 0 0\n", |
|
|
"Case #84: 1 0\n", |
|
|
"Case #85: 2 2\n", |
|
|
"Case #86: 1 0\n", |
|
|
"Case #87: 3 3\n", |
|
|
"Case #88: 0 0\n", |
|
|
"Case #89: 1 1\n", |
|
|
"Case #90: 0 0\n", |
|
|
"Case #91: 1 0\n", |
|
|
"Case #92: 1 1\n", |
|
|
"Case #93: 0 0\n", |
|
|
"Case #94: 0 0\n", |
|
|
"Case #95: 0 0\n", |
|
|
"Case #96: 3 2\n", |
|
|
"Case #97: 0 0\n", |
|
|
"Case #98: 0 0\n", |
|
|
"Case #99: 0 0\n", |
|
|
"Case #100: 0 0\n", |
|
|
"\n" |
|
|
] |
|
|
} |
|
|
], |
|
|
"source": [ |
|
|
"print sol('C-small-practice-1.in')" |
|
|
] |
|
|
}, |
|
|
{ |
|
|
"cell_type": "code", |
|
|
"execution_count": null, |
|
|
"metadata": { |
|
|
"collapsed": true |
|
|
}, |
|
|
"outputs": [], |
|
|
"source": [] |
|
|
} |
|
|
], |
|
|
"metadata": { |
|
|
"kernelspec": { |
|
|
"display_name": "Python 2", |
|
|
"language": "python", |
|
|
"name": "python2" |
|
|
}, |
|
|
"language_info": { |
|
|
"codemirror_mode": { |
|
|
"name": "ipython", |
|
|
"version": 2 |
|
|
}, |
|
|
"file_extension": ".py", |
|
|
"mimetype": "text/x-python", |
|
|
"name": "python", |
|
|
"nbconvert_exporter": "python", |
|
|
"pygments_lexer": "ipython2", |
|
|
"version": "2.7.12" |
|
|
} |
|
|
}, |
|
|
"nbformat": 4, |
|
|
"nbformat_minor": 2 |
|
|
} |