solutions: ["import re\nimport sys\nn = int(input().strip())\nB = input().strip()\nprint(len(re.findall('010', B)))\n", "m = int(input())\nn = str(input().strip())\nprint(n.count('010'))\n", "n = int(input())\ns = input()\nprint(s.count('010'))\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\nans = 0\nfor i in range(n - 2):\n\tif B[i] == '0' and B[i + 1] == '1' and (B[i + 2] == '0'):\n\t\tans += 1\n\t\tB[i + 2] = '1'\nprint(ans)\n", "import sys\nn = int(input().strip())\nB = input().strip()\ni = 2\ncount = 0\nwhile i < n:\n\tif B[i - 2:i + 1] == '010':\n\t\tcount += 1\n\t\ti += 2\n\ti += 1\nprint(count)\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\nans = 0\nfor k in range(n):\n\tfor i in range(n - 2):\n\t\tif ''.join(B[i:i + 3]) == '010':\n\t\t\tB[i + 2] = '1'\n\t\t\tans += 1\n\t\t\tbreak\nprint(ans)\n", "n = int(input())\nB = list(input())\ncounter = 0\nfor i in range(1, n - 1):\n\tif B[i] == '1' and B[i - 1] == '0' and (B[i + 1] == '0'):\n\t\tB[i + 1] = '1'\n\t\tcounter += 1\nprint(counter)\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\nc = 0\nfor i in range(n - 2):\n\tif B[i:i + 3] == list('010'):\n\t\tj = i + 2\n\t\tB[j] = '1'\n\t\tc += 1\nprint(c)\n", "n = int(input().strip())\ns = input().strip()\nc = 0\nc = s.count('010')\nprint(c)\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\nc = 0\nfor i in range(n - 2):\n\tif B[i:i + 3] == ['0', '1', '0']:\n\t\tB[i + 2] = '1'\n\t\tc += 1\nprint(c)\n", "import re\nn = int(input().strip())\nB = input().strip()\n(B1, rep) = re.subn('010', '011', B)\nprint(rep)\n", "import sys\nn = int(input().strip())\nB = input().strip()\ndelta = 0\nwhile '01010' in B:\n\tidx = B.index('01010')\n\tB = B[:idx + 2] + '1' + B[idx + 3:]\n\tdelta += 1\nwhile '010' in B:\n\tidx = B.index('010')\n\tB = B[:idx + 1] + '0' + B[idx + 2:]\n\tdelta += 1\nprint(delta)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nif n < 3:\n\tprint(0)\nelse:\n\ttotal = 0\n\ti = 2\n\twhile i < n:\n\t\tif B[i - 2:i + 1] == '010':\n\t\t\ttotal += 1\n\t\t\ti += 3\n\t\telse:\n\t\t\ti += 1\n\tprint(total)\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\ncnt = 0\nfor i in range(3, n + 1):\n\tif B[i - 3:i] == ['0', '1', '0']:\n\t\tB[i - 1] = '1'\n\t\tcnt += 1\nprint(cnt)\n", "n = int(input())\ntxt = input().strip()\ncnt = 0\ni = 0\nwhile i < n:\n\tif i < n - 2 and txt[i] == '0' and (txt[i + 1] == '1') and (txt[i + 2] == '0'):\n\t\tcnt += 1\n\t\ttxt[i + 2] == '1'\n\t\ti += 2\n\ti += 1\nprint(cnt)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nsteps = 0\nwhile True:\n\tpos = B.find('010')\n\tif pos == -1:\n\t\tbreak\n\telse:\n\t\tsteps += 1\n\t\tB = B[pos + 3:]\nprint(steps)\n", "import sys\nn = int(input().strip())\nB = map(int, input().strip())\ncounter = 0\ntwo_back = 2\none_back = 2\nfor i in B:\n\tif i == 0 and one_back == 1 and (two_back == 0):\n\t\tcounter += 1\n\t\tone_back = 1\n\t\ttwo_back = 1\n\t\tcontinue\n\t(two_back, one_back) = (one_back, i)\nprint(counter)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nB2 = B.replace('01010', '01110')\nB2 = B2.replace('010', '011')\nk = 0\nfor i in range(len(B)):\n\tif B[i] != B2[i]:\n\t\tk += 1\nprint(k)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nres = 0\ni = 0\nwhile i < n - 2:\n\tcount = 0\n\twhile B[i:i + 3] == '010':\n\t\tcount += 1\n\t\ti += 2\n\tif count % 2 == 0:\n\t\tres += int(count / 2)\n\telse:\n\t\tres += int(count / 2) + 1\n\ti += 1\nprint(res)\n", "input()\nb = list(input())\nans = 0\nfor i in range(len(b) - 2):\n\tif b[i] == '0' and b[i + 1] == '1' and (b[i + 2] == '0'):\n\t\tb[i + 2] = '1'\n\t\tans += 1\nprint(ans)\n", "n = int(input().strip())\nl = list(input().strip())\nr = 0\nwhile len(l) >= 3:\n\tif l[0] == '0' and l[1] == '1' and (l[2] == '0'):\n\t\tr += 1\n\t\tif len(l) > 3 and l[3] == '1':\n\t\t\tl[2] = '1'\n\t\telse:\n\t\t\tl[1] = '0'\n\tl = l[1:]\nprint(r)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nc = 0\nS = B.replace('010', '011')\nfor i in range(len(B)):\n\tif B[i] != S[i]:\n\t\tc += 1\nprint(c)\n", "import re\nn = int(input().strip())\nB = input().strip()\nexp = re.compile('010')\nprint(len(exp.findall(B)))\n", "import sys\nimport re\nn = int(input().strip())\nB = input().strip()\nprint(len(re.findall('(010)', B)))\n", "import sys\nn = input()\na = input()\na = list(a)\ncount = 0\nfor i in range(len(a) - 2):\n\tif a[i] == '0' and a[i + 1] == '1' and (a[i + 2] == '0'):\n\t\ta[i + 2] = '1'\n\t\tcount += 1\nprint(count)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nC = B.split('010')\nk = 0\nfor var in C:\n\tk = k + len(var)\nprint(int((n - k) / 3))\n", "import sys\nn = int(input().strip())\nB = input().strip()\npattern = '010'\ncount = 0\nwhile True:\n\tx = B.find(pattern)\n\tif x < 0:\n\t\tbreak\n\tcount = count + 1\n\tB = B[x + 3:]\nprint(count)\n", "import sys\na = 0\nn = int(input().strip())\nB = [int(b_temp) for b_temp in input().strip()]\nfor i in range(n - 2):\n\tif B[i] == 0 and B[i + 1] == 1 and (B[i + 2] == 0):\n\t\tB[i + 2] = 1\n\t\ta += 1\nprint(a)\n", "import sys\nn = int(input().strip())\nB = input().strip()\ntimes = 0\nwhile '010' in B:\n\tB = B.replace('010', '011', 1)\n\ttimes += 1\nprint(times)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nc = 0\nl = B.find('010')\nwhile l > -1:\n\tB = B.replace('010', '011', 1)\n\tl = B.find('010')\n\tc += 1\nprint(c)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nif '010' not in B:\n\tprint(0)\nelse:\n\tnum = 0\n\twhile True:\n\t\tif '01010' in B:\n\t\t\tB = B.replace('01010', '01110', 1)\n\t\t\tnum = num + 1\n\t\telif '010' in B:\n\t\t\tB = B.replace('010', '000', 1)\n\t\t\tnum = num + 1\n\t\telse:\n\t\t\tbreak\n\tprint(num)\n", "def chan(stri, point):\n\tif stri[point] == 0:\n\t\tstri[point] = 1\n\telif stri[point] == 1:\n\t\tstri[point] = 0\n\treturn stri\ntemp = []\ncont = 0\nn = int(input())\nstri = input().strip()\nfor k in range(n - 2):\n\tif stri[0 + k:0 + k + 3] == '010':\n\t\tif not k - 2 in temp:\n\t\t\tstri = chan(stri, k + 2)\n\t\t\tcont += 1\n\t\t\ttemp.append(k)\nprint(cont)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nj = 0\nfor i in range(n):\n\tif '01010' in B:\n\t\tcatch = B.find('01010')\n\t\tlstB = list(B)\n\t\tlstB[catch + 2] = '1'\n\t\tB = ''.join(lstB)\n\t\tj += 1\n\t\tpass\n\telif '010' in B:\n\t\tcatch = B.find('010')\n\t\tlstB = list(B)\n\t\tlstB[catch] = '1'\n\t\tB = ''.join(lstB)\n\t\tj += 1\n\t\tpass\nprint(j)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nB = [i for i in B]\ni = 0\ncnt = 0\nwhile i < n - 2:\n\ttemp = B[i:i + 3]\n\tif ''.join(temp) == '010':\n\t\tcnt += 1\n\t\ti = i + 3\n\telse:\n\t\ti += 1\nprint(cnt)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nint_b = [int(x) for x in B]\ncount = 0\nfor i in range(len(int_b)):\n\tif int_b[i:i + 3] == [0, 1, 0]:\n\t\tint_b[i + 2] = 1\n\t\tcount += 1\nprint(count)\n", "def unbeautify(s):\n\tl = [int(ch) for ch in s]\n\ti = 0\n\tcount = 0\n\twhile i < len(l) - 2:\n\t\tif l[i:i + 3] == [0, 1, 0]:\n\t\t\tl[i + 2] = 1\n\t\t\tcount += 1\n\t\t\ti += 2\n\t\ti += 1\n\treturn count\n\ndef test():\n\tres = unbeautify('0101010')\n\tassert res == 2\n\tres = unbeautify('01100')\n\tassert res == 0\n\tres = unbeautify('0100101010')\n\tassert res == 3\n\ndef main():\n\t_ = input().strip()\n\ts = input().strip()\n\tprint(unbeautify(s))\nmain()\n", "import sys\nn = int(input().strip())\nB = input().strip()\nbb = [i for i in B]\nstrn = '010'\nc = 0\nwhile True:\n\ta = B.find(strn)\n\tif a >= 0:\n\t\tbb[a + 2] = '1'\n\t\tB = ''.join(bb)\n\t\tc += 1\n\telse:\n\t\tbreak\nprint(c)\n", "n = int(input().strip())\nb = input().strip()\n(i, step) = (0, 0)\nwhile i < n - 2:\n\tif b[i] + b[i + 1] + b[i + 2] == '010':\n\t\tstep += 1\n\t\ti += 2\n\ti += 1\nprint(step)\n", "import sys\nn = int(input().strip())\nB = [x for x in input().strip()]\nsteps = 0\nfor i in range(2, n):\n\tif B[i - 2] == '0' and B[i - 1] == '1' and (B[i] == '0'):\n\t\tB[i] = '1'\n\t\tsteps += 1\nprint(steps)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nif len(B) < 3:\n\tprint(0)\nelse:\n\tcount = 0\n\tBlist = list(B)\n\tfor i in range(1, len(Blist) - 1):\n\t\tif Blist[i] == '1' and Blist[i - 1] == '0' and (Blist[i + 1] == '0'):\n\t\t\tcount += 1\n\t\t\tBlist[i + 1] = '1'\n\tprint(count)\n", "import sys\nn = int(input())\ns = input().strip()\ns = [x for x in s]\ncnt = 0\nfor i in range(len(s)):\n\tv = ''.join([c for c in s[i:i + 3]])\n\tif v == '010':\n\t\ts[i + 2] = '1'\n\t\tcnt += 1\nprint(cnt)\n", "n = int(input())\ns = input()\ni = 1\nans = 0\nwhile i < n - 1:\n\tif s[i - 1:i + 2] == '010':\n\t\tans += 1\n\t\ti += 3\n\telse:\n\t\ti += 1\nprint(ans)\n", "import sys\nimport re\nn = int(input().strip())\nB = input().strip()\nugly = '010'\ncounter = 0\nfor ugly in B:\n\tif B.find('010') != -1:\n\t\tB = re.sub('010', '011', B, 1)\n\t\tcounter += 1\nprint(counter)\n", "import sys\nimport re\nn = int(input().strip())\nB = input().strip()\nmatches = re.findall('010', B)\nprint(len(matches))\n", "import sys\nn = int(input().strip())\nB = input().strip()\nprint(len(B.split('010')) - 1)\n", "_010 = ['0', '1', '0']\n\ndef minSteps(s):\n\tsteps = 0\n\tfor i in range(0, n - 2):\n\t\tif s[i:i + 3] == _010:\n\t\t\ts[i + 2] = 1\n\t\t\tsteps += 1\n\treturn steps\nn = int(input().strip())\nB = list(input().strip())\nprint(min(minSteps(list(B)), minSteps(B[::-1])))\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\nans = 0\nfor i in range(n - 2):\n\tif B[i] == '0' and B[i + 1] == '1' and (B[i + 2] == '0'):\n\t\tans += 1\n\t\tB[i + 2] = '1'\nprint(ans)\n", "import sys\nn = int(input().strip())\nb = input().strip()\nc = b.count('010')\nprint(c)\n", "import sys\nfrom collections import Counter\nn = int(input().strip())\nB = input().strip()\nc = B.count('010')\nprint(c)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nC = B\ncount = 0\ni = 0\nwhile i < len(B) - 2:\n\tif B[i:i + 3] == '010':\n\t\tC = C[:i + 2] + '.' + C[i + 3:]\n\t\tcount += 1\n\t\ti += 3\n\telse:\n\t\ti += 1\nprint(count)\n", "N = int(input())\nB = input().strip()\nd = 0\ni = B.find('010')\nwhile i >= 0:\n\td += 1\n\ti = B.find('010', i + 3)\nprint(d)\n", "import sys\nn = int(input().strip())\nB = input().strip()\n\ndef beautify(my_str):\n\tif len(my_str) in range(3):\n\t\treturn 0\n\tfor i in range(len(my_str) - 2):\n\t\tif my_str[i:i + 3] == '010':\n\t\t\treturn 1 + beautify(my_str[i + 3:])\n\treturn 0\nprint(beautify(B))\n", "import sys\nn = int(input().strip())\nB = input().strip()\ncount = 0\nx = 0\nleftIndex = -1\nprevIndex = -1\noverlap = 0\nwhile x < len(B):\n\tleftIndex = B.find('010', x)\n\tif leftIndex != -1:\n\t\tcount += 1\n\t\tif prevIndex + 2 == leftIndex:\n\t\t\toverlap += 1\n\t\telif overlap > 0:\n\t\t\tif overlap > 2:\n\t\t\t\tcount -= 2\n\t\t\telse:\n\t\t\t\tcount -= 1\n\t\t\toverlap = 0\n\t\tprevIndex = leftIndex\n\t\tx = leftIndex + 2\n\telse:\n\t\tx += 1\nif overlap > 0:\n\tif overlap > 2:\n\t\tcount -= 2\n\telse:\n\t\tcount -= 1\nprint(count)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nif '010' not in B:\n\tprint(0)\nelse:\n\tprint(B.count('010'))\n", "from sys import stdin\n\ndef BeautifulBinaryString(n: int, B: str) -> int:\n\tassert len(B) == n\n\tassert set(B).issubset({'0', '1'})\n\treturn B.count('010')\nINPUT = stdin.read().strip().splitlines()\nOUTPUT = BeautifulBinaryString(int(INPUT[0]), INPUT[1])\nprint(OUTPUT)\n", "import sys\nimport re\nn = int(input().strip())\nB = input().strip()\nmos = re.findall('010', B)\nprint(len(mos))\n", "n = int(input().strip())\nB = input().strip()\nc = 0\nwhile '010' in B:\n\tB = B[B.index('010') + 3:]\n\tc += 1\nprint(c)\n", "import sys\n\ndef solve(a):\n\t(cnt, i) = (0, 0)\n\twhile i < len(a):\n\t\tj = a.find('010', i)\n\t\tif j == -1:\n\t\t\tbreak\n\t\tif j < len(a) - 6 and a[j:j + 5] == '01010':\n\t\t\tcnt += 1\n\t\t\ti = j + 4\n\t\telse:\n\t\t\tcnt += 1\n\t\t\ti = j + 3\n\treturn cnt\nn = int(input().strip())\nB = input().strip()\nprint(solve(B))\n", "import sys\nn = input()\nB = input()\nprint(B.count('010'))\n", "n = int(input())\ns = input()\nprint(s.count('010'))\n", "import sys\nn = int(input().strip())\nB = input().strip()\nl = B.count('010')\nprint(l)\n", "def read_int():\n\treturn int(input().strip())\n\ndef read_string():\n\treturn str(input().strip())\nN = read_int()\nbs = read_string()\nL = len(bs)\ni = 0\ncount = 0\nwhile i < L:\n\tif bs[i:i + 5] == '01010':\n\t\tcount += 1\n\t\ti += 4\n\t\tcontinue\n\tif bs[i:i + 3] == '010':\n\t\tcount += 1\n\t\ti += 3\n\t\tcontinue\n\ti += 1\nprint(count)\n", "input()\n\ndef beautify(s):\n\tresult = 0\n\tfor i in range(len(s) - 2):\n\t\tif s[i:i + 3] == '010':\n\t\t\ts = s[:i + 2] + '1' + s[i + 3:]\n\t\t\tresult += 1\n\treturn result\nprint(beautify(input()))\n", "(n, B) = (input(), input())\nnchanges = 0\nwhile '010' in B:\n\tB = B.replace('010', 'XXX', 1)\n\tnchanges += 1\nprint(nchanges)\n", "n = int(input().strip())\nB = input().strip()\nl = list()\nfor i in B:\n\tl.append(i)\nc = 0\nfor i in range(0, n - 2, 1):\n\tif l[i] + l[i + 1] + l[i + 2] == '010':\n\t\tc = c + 1\n\t\tl[i + 2] = '1'\nprint(c)\n", "import sys\nimport re\nn = int(input().strip())\nB = input().strip()\ncount = 0\nx = re.findall('010', B)\nprint(len(x))\n", "import sys\nk = 0\na = False\nn = int(input().strip())\nB = input().strip()\nwhile a == False:\n\tif B.find('010') > -1:\n\t\ta = False\n\t\tB = B.replace('010', '011', 1)\n\t\tk += 1\n\telse:\n\t\ta = True\nprint(k)\n", "import sys\nn = int(input().strip())\nB = input().strip()\ncount = B.count('010')\nprint(count)\n", "n = int(input().strip())\nB = input().strip()\nprint(B.count('010'))\n", "n = int(input())\ns = input()\ncount = 0\nfor i in range(2, n, 1):\n\tif s[i - 2] == '0' and s[i - 1] == '1' and (s[i] == '0'):\n\t\tif i + 1 <= len(s) - 1 and s[i + 1] == '1':\n\t\t\ts = s[:i] + '1' + s[i + 1:]\n\t\telse:\n\t\t\ts = s[:i - 1] + '0' + s[i:]\n\t\tcount += 1\nprint(count)\n", "import sys\nn = int(input().strip())\nb = input().strip()\nc = 0\nwhile '010' in b:\n\ti = b.index('010')\n\tb = b[:i] + '011' + b[i + 3:]\n\tc += 1\nprint(c)\n", "import sys\nn = int(input().strip())\nb = input().count('010')\nprint(b)\n", "import sys\nprint(input() * False, input().count('010'), sep='')\n", "import sys\ncount = input()\nstring = str(input())\nprint(string.count('010'))\n", "import sys\nn = int(input().strip())\nB = input().strip()\ncnt = 0\ni = 0\nwhile i < len(B) - 2:\n\tif B[i:i + 3] == '010':\n\t\tcnt += 1\n\t\ti += 2\n\ti += 1\nprint(cnt)\n", "input()\nprint(input().count('010'))\n", "import sys\nn = int(input().strip())\nB = input().strip()\nif n <= 2:\n\tprint(0)\nelse:\n\t(p1, p2) = (B[0], B[1])\n\tcount = 0\n\tfor i in range(2, n):\n\t\tc = B[i]\n\t\tif p1 + p2 + c == '010':\n\t\t\tcount += 1\n\t\t\tp1 = p2\n\t\t\tp2 = '1'\n\t\telse:\n\t\t\tp1 = p2\n\t\t\tp2 = c\n\tprint(count)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nprint(B.count('010'))\n", "import sys\nn = int(input().strip())\nB = input().strip()\nl = [int(n) for n in B]\nr = 0\nfor ind in range(0, len(l) - 2):\n\tif l[ind] == 0 and l[ind + 1] == 1 and (l[ind + 2] == 0):\n\t\ttry:\n\t\t\tl[ind + 2] = 1\n\t\t\tr += 1\n\t\texcept:\n\t\t\tpass\nprint(r)\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\ncount = 0\nfor b1 in range(0, n - 2):\n\tif B[b1] == '0' and B[b1 + 1] == '1' and (B[b1 + 2] == '0'):\n\t\tB[b1 + 2] = '1'\n\t\tcount += 1\nprint(count)\n", "import sys\nimport re\nn = int(input().strip())\nB = input().strip()\ndfa = re.compile('010')\nmatch = dfa.search(B)\ncount = 0\nwhile match:\n\tcount += 1\n\tif match.end() < len(B):\n\t\tB = B[match.end():]\n\telse:\n\t\tbreak\n\tmatch = dfa.search(B)\nprint(count)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nprint(B.count('010'))\n", "import sys\nn = int(input().strip())\nB = input().strip()\nprint(B.count('010'))\n", "import sys\nn = int(input().strip())\nB = input().strip()\nb = []\nfor i in range(0, len(B)):\n\tb.append(B[i])\nif n < 3:\n\tprint(0)\nelse:\n\tcnt = 0\n\tfor i in range(3, n + 1):\n\t\tif b[i - 3] == '0' and b[i - 2] == '1' and (b[i - 1] == '0'):\n\t\t\tb[i - 1] = '1'\n\t\t\tcnt = cnt + 1\n\tprint(cnt)\n", "import sys\nn = input().strip()\nB = input().strip()\nprint(B.count('010'))\n", "import sys\nn = int(input().strip())\nB = str(input().strip())\nsolved = False\ncount = 0\nwhile not solved:\n\tindex = B.find('010')\n\tif index != -1:\n\t\tl = list(B)\n\t\tl[index + 2] = '1'\n\t\tB = ''.join(l)\n\t\tcount += 1\n\telse:\n\t\tsolved = True\nprint(count)\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\nTARGET = list('010')\nsteps = 0\nfor i in range(n - 2):\n\tif B[i:i + 3] == TARGET:\n\t\tB[i + 2] = '1'\n\t\tsteps += 1\nprint(steps)\n", "import sys\nn = int(input().strip())\nB = input().strip()\ncnt = 0\nfor i in range(n - 2):\n\tif B[i:i + 3] == '010':\n\t\tBnew = B[:i] + '011' + B[i + 3:]\n\t\tB = Bnew\n\t\tcnt += 1\nprint(cnt)\n", "import sys\nend = int(input().strip())\nstring = input().strip()\npattern = '010'\nstart = 0\ncounter = 0\nwhile start > -1 and start < end:\n\tstart = string.find(pattern, start)\n\tif start > -1:\n\t\tcounter += 1\n\t\tstart += len(pattern)\nprint(counter)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nprint(B.count('010'))\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\ncounter = 0\nfor pos in range(n - 2):\n\tif B[pos:pos + 3] == ['0', '1', '0']:\n\t\tB[pos + 2] = '1'\n\t\tcounter += 1\nprint(counter)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nprev_end = -1\nstart = 0\noperations = 0\nwhile start < n:\n\tif B[start] == '0' and B[start:start + 3] == '010':\n\t\tif start > prev_end:\n\t\t\toperations += 1\n\t\t\tprev_end = start + 2\n\t\tstart += 2\n\telse:\n\t\tstart += 1\nprint(operations)\n", "import sys\nn = int(input().strip())\nB = input().strip()\ni = 0\nresult = 0\nwhile i < n:\n\tif B[i:i + 3] == '010':\n\t\ti += 3\n\t\tresult += 1\n\telse:\n\t\ti += 1\nprint(result)\n", "import sys\nn = int(input().strip())\nb = list(input().strip())\nc = 0\ncount = 0\nwhile c < len(b) - 2:\n\tif b[c] == '0':\n\t\tif b[c + 1] == '1':\n\t\t\tif b[c + 2] == '0':\n\t\t\t\tb[c + 2] = '1'\n\t\t\t\tcount += 1\n\t\t\telse:\n\t\t\t\tc += 3\n\t\telse:\n\t\t\tc += 1\n\telse:\n\t\tc += 1\nprint(count)\n", "import sys\nn = int(input().strip())\nB = input().strip()\n\ndef solution(number):\n\treturn B.count('010')\nprint(solution(B))\n", "import sys\nn = int(input())\ns = input()\npattern = '010'\nop = 0\nflag = s.find(pattern)\nwhile flag != -1:\n\tif len(s) > flag + 3:\n\t\ts = s[:flag + 2] + '1' + s[flag + 3:]\n\telse:\n\t\ts = s[:flag + 2] + '1'\n\tflag = s.find(pattern)\n\top += 1\nprint(op)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nc = 0\nfor i in range(len(B) - 2):\n\tif B[i:i + 3] == '010':\n\t\tB = B[:i] + '011' + B[i + 3:]\n\t\tc += 1\nprint(c)\n", "import sys\nn = int(input().strip())\nB = list(input().strip())\nres = 0\nfor i in range(n - 2):\n\tif B[i] == '0' and B[i + 1] == '1' and (B[i + 2] == '0'):\n\t\tB[i + 2] = '1'\n\t\tres += 1\nprint(res)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nl = list(B)\ncount = 0\nfor i in range(len(l) - 2):\n\tif (B[i:i + 3] == '010') & (l[i] == '0'):\n\t\tl[i + 2] = '1'\n\t\tcount += 1\nprint(count)\n", "import sys\nn = int(input().strip())\nB = input().strip()\nres = 0\nwhile True:\n\ti = B.find('0101')\n\tif i == -1:\n\t\tbreak\n\tB = B[:i] + '0111' + B[i + 4:]\n\tres += 1\nwhile True:\n\ti = B.find('010')\n\tif i == -1:\n\t\tbreak\n\tB = B[:i] + '011' + B[i + 3:]\n\tres += 1\nprint(res)\n"]

difficulty: EASY

source: hacker rank

question:
Alice has a binary string. She thinks a binary string is beautiful if and only if it doesn't contain the substring $\text{"010"}$.

In one step, Alice can change a $0$ to a $1$ or vice versa. Count and print the minimum number of steps needed to make Alice see the string as beautiful.

Example

$b=\textbf{010}$

She can change any one element and have a beautiful string.

Function Description

Complete the beautifulBinaryString function in the editor below.

beautifulBinaryString has the following parameter(s):

string b: a string of binary digits

Returns

int: the minimum moves required

Input Format

The first line contains an integer $n$, the length of binary string.

The second line contains a single binary string $\boldsymbol{b}$.

Constraints

$1\leq n\leq100$
$b[i]\in\{0,1\}$.

Output Format

Print the minimum number of steps needed to make the string beautiful.

Sample Input 0

STDIN       Function
-----       --------
7           length of string n = 7
0101010     b = '0101010'

Sample Output 0

2

Explanation 0:

In this sample, $b=\text{"0101010"}$

The figure below shows a way to get rid of each instance of $\text{"010"}$:

![image](1.png)
Make the string beautiful by changing $2$ characters ($b[2]$ and $b\left[5\right]$).

Sample Input 1

5
01100

Sample Output 1

0

Sample Case 1:

In this sample $b=\text{"01100"}$

Explanation 1

The substring $\text{"010"}$ does not occur in $\boldsymbol{b}$, so the string is already beautiful in $0$ moves.

Sample Input 2

10
0100101010

Sample Output 2

3

Explanation 2

In this sample $b=\text{"0100101010"}$

One solution is to change the values of $b[2],b[5]\:\text{and}\:b[9]$ to form a beautiful string.

data_split: test


solutions: ["t = int(input())\nt1 = 3\nwhile t1 < t:\n\tt -= t1\n\tt1 *= 2\nprint(t1 - t + 1)\n", "n = int(input())\ndec = 3\nwhile n > dec:\n\tn -= dec\n\tdec *= 2\nprint(dec - n + 1)\n", "from sys import stdin, stdout\nt = int(stdin.readline())\ntempsCycle = 3\ntAffiche = -1\nwhile tAffiche == -1:\n\tif tempsCycle >= t:\n\t\ttAffiche = tempsCycle - t + 1\n\telse:\n\t\tt -= tempsCycle\n\ttempsCycle *= 2\nprint(tAffiche)\n", "time = int(input())\nt = 3\nmult = 2\nwhile time > t:\n\tt += 3 * mult\n\tmult *= 2\nprint(1 + (t - time))\n", "def value_at_t(t):\n\tt_start = 1\n\tv_start = 3\n\twhile True:\n\t\tif t_start <= t < t_start + v_start:\n\t\t\treturn v_start - (t - t_start)\n\t\telse:\n\t\t\tt_start += v_start\n\t\t\tv_start *= 2\nt = int(input())\nprint(value_at_t(t))\n", "t = int(input())\nvalue = 3\ntime = 1\nwhile True:\n\tif t < time + value:\n\t\tprint(value - (t - time))\n\t\tbreak\n\t(time, value) = (time + value, value * 2)\n", "import sys\na1 = [1]\na2 = [3]\nt = int(input())\nbr = int(1)\nwhile a1[-1] <= t:\n\ta1.append(a1[br - 1] + a2[br - 1])\n\ta2.append(a2[br - 1] * 2)\n\tbr += 1\nres = a2[-2] - (t - a1[-2])\nprint(res)\n", "t = int(input())\na = [0, 3]\ns = 3\nwhile s < t:\n\ta.append(a[-1] * 2)\n\ts += a[-1]\ns -= a[-1]\nprint(a[-1] - (t - s) + 1)\n", "t = int(input())\n\ndef strange(t):\n\tif t < 4:\n\t\treturn 4 - t\n\tn = 0\n\tsumi = 0\n\twhile True:\n\t\tif sumi + 3 * 2 ** n > t:\n\t\t\tbreak\n\t\tsumi += 3 * 2 ** n\n\t\tn += 1\n\tmaxi = 3 * 2 ** n\n\trem = t - sumi\n\treturn maxi - rem + 1\nprint(strange(t))\n", "import math\nt = int(input())\nd = math.ceil(math.log(((t - 3) / 2 + 3) / 3, 2))\ntop = (math.pow(2, d) - 1) * 6 + 3\nprint(int(top - t + 1))\n", "import math\n\ndef solve(t):\n\tstage = int(math.log((t + 2) / 3, 2))\n\ta = []\n\tfor i in range(stage + 2):\n\t\ta.append(sum(a) + 2 * i + 1)\n\treturn a[-1] - t\nt = int(input())\nprint(solve(t))\n", "import math\nn = int(input())\nt = int(math.ceil(math.log(n / 3 + 1, 2)))\nval = 3 * 2 ** (t - 1)\nprint(val - (n - val + 2))\n", "max = 3\nn_iter = int(input())\nwhile n_iter > max:\n\tn_iter -= max\n\tmax *= 2\ncounter = max + 1 - n_iter\nprint(counter)\n", "(c, cmax) = (0, 3)\nt = int(input().strip())\nwhile c < t:\n\tc += cmax\n\tcmax *= 2\nprint(c - t + 1)\n", "t = int(input())\nk = 3\ni = 1\nwhile i <= t:\n\ti += k\n\tk *= 2\ni = i - k // 2\nprint(k // 2 - (t - i))\n", "from math import log, ceil\nt = int(input())\n\ndef geom_sum(x):\n\treturn int(3 * (2 ** x - 1))\n\ndef lower_sum(t):\n\treturn int(ceil(log(t / 3 + 1) / log(2)))\nprint(geom_sum(lower_sum(t)) - t + 1)\n", "t = int(input().strip())\nstart_time = 3\nwhile t > start_time:\n\tt -= start_time\n\tstart_time = start_time << 1\nnum = start_time - t + 1\nprint(num)\n", "t = int(input())\n(start, step) = (0, 3)\nwhile t > start:\n\tstart += step\n\tstep *= 2\nprint(start - t + 1)\n", "t = int(input().strip())\nnot_done = True\nt_start = 3\nc_start = 3\nwhile not_done:\n\tif t < t_start:\n\t\tnot_done = False\n\telse:\n\t\tc_start *= 2\n\t\tt_start += c_start\nprint(c_start - (t - (t_start - c_start)) + 1)\n", "t = int(input())\nn = 0\ncount = 0\nwhile n < t:\n\tn += 3 * 2 ** count\n\tcount += 1\nprint(n - t + 1)\n", "import math\nt = int(input().strip())\nx = int(math.log((t + 2) / 3, 2))\nst = 3 * (pow(2, x) - 1) + 1\np3 = 3 * pow(2, x)\nans = p3 - t + st\nprint(ans)\n", "t = int(input())\nx = 3\nsum = 0\nwhile sum < t:\n\tsum += x\n\tx *= 2\nprint(sum - t + 1)\n", "import math as m\nn = int(input())\nx = m.ceil(m.log(m.ceil(n / 3) + 1, 2))\nst = 3 * (2 ** (x - 1) - 1) + 1\nend = 3 * (2 ** x - 1)\nno = end - st + 1\ndiff = n - st + 1\nprint(no - diff + 1)\n", "counter = 3\nt = int(input().strip())\nwhile t > counter:\n\tt -= counter\n\tcounter *= 2\nprint(counter - t + 1)\n", "import math\nt = int(input().strip())\ncol = math.ceil(math.log2(t / 3 + 1))\ncolmax = (2 ** col - 1) * 3\nprint(colmax - t + 1)\n", "t = int(input())\na = [3]\nwhile sum(a) < t:\n\ta.append(a[-1] * 2)\nprint(a[-1] - (t - sum(a[:-1])) + 1)\n", "import math\nt = int(input())\nk = 1\nr = 3\nwhile t > r:\n\tt -= r\n\tr *= 2\nr -= t - 1\nprint(r)\n", "t = int(input())\ntime = 1\nvalue = 3\nnext_value = value * 2\nnext_time = value + time\nwhile next_time < t:\n\t(time, value) = (next_value, next_time)\n\tnext_value = next_value * 2\n\tnext_time = value + time\nif t == next_time:\n\tprint(next_value)\nelse:\n\tdiff = t - time\n\tresult = value - diff\n\tprint(result)\n", "t = int(input())\nc = 3\nlast = 3\nwhile c < t:\n\tc += last * 2\n\tlast = last * 2\nprint(c - t + 1)\n", "t = int(input().strip())\nmultiply = 3\nmultCounter = 1\nless = True\nwhile less:\n\tif multiply < t:\n\t\tmultCounter = multCounter * 2 + 1\n\t\tmultiply = 3 * multCounter\n\telse:\n\t\tless = False\nsetTop = 1 + 3 * ((multCounter - 1) / 2)\nsetRange = setTop + 2\ndiff = abs(setTop - t)\noutput = setRange - diff\nprint(int(output))\n", "t = int(input())\nn = t // 3 + 1\ni = 0\nwhile n > 0:\n\tn //= 2\n\ti += 1\nprint(3 * (2 ** i - 1) + 1 - t)\n", "t = int(input())\ni = 0\ntt = 3\nwhile t - tt > 0:\n\ti += 1\n\ttt += 3 * 2 ** i\nprint(tt - t + 1)\n", "import math\nt = int(input())\nn = int(math.log(t / 3 + 1, 2)) - 1\nprint(3 * 2 ** (n + 1) + 1 - (t - 3 * (2 ** (n + 1) - 1)))\n", "import math\n\ndef isInt(x):\n\tif x - int(x) == 0:\n\t\treturn True\n\treturn False\n\ndef main():\n\tt = int(input())\n\tif t == 1:\n\t\tprint(3)\n\tif t == 2:\n\t\tprint(2)\n\tif t == 3:\n\t\tprint(1)\n\tif t > 3:\n\t\ta = 3\n\t\tr = 2\n\t\tk = math.log(t / 3 + 1, 2)\n\t\tif isInt(k):\n\t\t\tprint(1)\n\t\telse:\n\t\t\tn = int(k)\n\t\t\ts = 3 * (2 ** n - 1)\n\t\t\tterm = a * r ** (n - 1)\n\t\t\tans = 2 * term - (t - s) + 1\n\t\t\tprint(int(ans))\nmain()\n", "t = int(input())\nex = 0\nx = 3\np = 3\ni = 0\nwhile ex <= t:\n\tex = ex + 3 * pow(2, i)\n\ti += 1\ni -= 1\nex = ex - 3 * pow(2, i)\nx = 3 * pow(2, i)\np = x - (t - ex) + 1\nprint(p)\n", "from sys import stdin\nimport math\nt = int(input().strip())\np = 0\nn = 0\nwhile n < t:\n\tn += 3 * 2 ** p\n\tp += 1\np -= 1\nfirst = n - 3 * 2 ** p + 1\nans = 3 * 2 ** p - (t - first)\nprint(ans)\n", "import sys\nt = int(input())\nnum_cycles = 0\nt_temp = t\njump = 3\nwhile t_temp > jump:\n\tt_temp -= jump\n\tjump *= 2\n\tnum_cycles += 1\nprint(3 * pow(2, num_cycles) - t_temp + 1)\n", "import math\nnumber = int(input())\n\ndef answer(number):\n\tp = math.floor(math.log(number // 3 + 1, 2))\n\tmaxSumOfSeriesThat = 3 * (2 ** p - 1)\n\tif maxSumOfSeriesThat == number:\n\t\treturn 1\n\telse:\n\t\treturn 3 * 2 ** p - (number - maxSumOfSeriesThat) + 1\nprint(answer(number))\n", "t = int(input())\nt1 = t // 3\npower = 0\nwhile 2 ** power - 1 <= t1:\n\tpower += 1\nt2 = t - 3 * (2 ** (power - 1) - 1)\nif t2 == 0:\n\tn = 1\nelse:\n\tn = 3 * 2 ** (power - 1) - t2 + 1\nprint(n)\n", "t = int(input())\nT_now = 1\nwhile 3 * (T_now - 1) < t:\n\tT_now *= 2\nprint(3 * T_now - (t + 2))\n", "def solve(t):\n\tn = t\n\tif t < 3:\n\t\treturn 4 - t\n\tL = []\n\tL.append(t % 3)\n\tt = t // 3\n\twhile t:\n\t\tL.append(t % 2)\n\t\tt = t // 2\n\ty = L[-1] * 3 * pow(2, len(L) - 2)\n\tdiff = n - y\n\tout = y - diff - 2\n\tif out <= 0:\n\t\ty = 2 * y\n\t\tdiff = n - y\n\t\tout = y - diff - 2\n\treturn out\nprint(solve(int(input())))\n", "t = int(input().strip())\nn = x = 0\nwhile x < t:\n\tn = n + 1\n\tx = 3 * (2 ** n - 1)\nprint(x - t + 1)\n", "from math import *\n\ndef genf(i):\n\treturn ceil(3 * (pow(2, ceil(log(i / 3 + 1, 2))) - 1))\nn = int(input())\nprint(genf(n) - n + 1)\n", "import math\nt = int(input())\nr = int(math.log2((t - 1) // 3 + 1))\nprint(3 * 2 ** (r + 1) - t - 2)\n", "import math\nt = int(input())\ncycle = int(math.ceil(math.log(t / 3 + 1, 2)))\nstarting_value = 3 * 2 ** (cycle - 1)\nstarting_t = (2 ** (cycle - 1) - 1) * 3 + 1\nvalue = starting_value - (t - starting_t)\nprint(value)\n", "import math\nt = int(input())\np = math.log(t / 3 + 1, 2)\nn = math.floor(p) + math.ceil(p - math.floor(p))\nans = 3 * 2 ** n - t - 2\nprint(ans)\n", "t = int(input())\nremainder = t % 3\npoweroftwo = (t - t % 3) // 3\nif remainder:\n\tpoweroftwo += 1\nindex = len(bin(poweroftwo)[2:])\nprint(3 * (2 ** index - 1) - t + 1)\n", "def solution(t):\n\ttime = 1\n\tvalue = 3\n\tresult = 0\n\twhile True:\n\t\tnext_t = time * 2 + 2\n\t\tif time <= t < next_t:\n\t\t\tresult = value - (t - time)\n\t\t\tbreak\n\t\ttime = next_t\n\t\tvalue *= 2\n\treturn result\nt = int(input().strip())\nresult = solution(t)\nprint(result)\n", "t = int(input())\ns = 3\nv = 3\ni = 1\nc = 0\nif t <= 3:\n\tprint(3 - t + 1)\nelse:\n\twhile True:\n\t\tv = v * 2\n\t\ts = v + s\n\t\tif t % s == t:\n\t\t\tc = i\n\t\t\tbreak\n\t\telif t % s == 0 and t / s == 1.0:\n\t\t\tc = i\n\t\t\tbreak\n\t\ti = i + 1\n\tprint(s - t + 1)\n", "import math\nt = int(input())\nn = math.floor(math.log((t + 3) / 6, 2)) + 1\nk1 = 3 * 2 ** n\nk2 = 2 ** (n - 1) - 1\nk3 = t - 3 - 6 * k2\nk4 = k1 - k3 + 1\nprint(int(k4))\n", "p = int(input())\ncount1 = 0\ncount2 = 0\nif p <= 3:\n\tprint(3 - (p - 1))\nelif p > 3 and p <= 9:\n\tprint(9 - (p - 1))\nelse:\n\tfor i in range(int(p / 2)):\n\t\tz = 3 * pow(2, i)\n\t\tcount1 = count1 + z\n\t\tif p > count2 and p <= count1:\n\t\t\tprint(1 + (count1 - p))\n\t\t\texit(0)\n\t\tcount2 = count2 + z\n", "t = int(input())\ncount = 3\ntemp = 3\ntotal = 3\nwhile True:\n\tif t <= total:\n\t\tprint(total - t + 1)\n\t\tbreak\n\telse:\n\t\ttotal = total + temp * 2\n\t\ttemp = temp * 2\n", "import math\nt = int(input())\ns = 3\nn = 1\nwhile s < t:\n\ts += 6 * math.pow(2, n - 1)\n\tn += 1\nprint(int(s + 1 - t))\n", "a = int(input())\nx = 0\ncount = 3\nscore = 1\nwhile x < a:\n\tx += count\n\tcount *= 2\nscore += x - a\nprint(score)\n", "t = int(input())\ncount = 3\ntemp = 3\ntotal = 3\nwhile True:\n\tif t <= total:\n\t\tprint(total - t + 1)\n\t\tbreak\n\telse:\n\t\ttotal = total + temp * 2\n\t\ttemp = temp * 2\n", "import sys\nimport math\nt = int(input().strip())\nm = math.floor(math.log2((t - 1) // 3 + 1))\nr = t - 3 * (2 ** m - 1)\nprint(3 * 2 ** (m + 1) - t - 2)\n", "from math import log2\nt = int(input().strip())\ncycle = int(log2((t - 1) // 3 + 1))\ncycle_start = 3 * 2 ** cycle\nstart_time = 3 * (2 ** cycle - 1) + 1\ncounter = cycle_start - (t - start_time)\nprint(counter)\n", "import sys\nt = int(input().strip())\nn = 3\nwhile t - n > 0:\n\tt = t - n\n\tn *= 2\nprint(n - t + 1)\n", "from math import log\nt = int(input())\ngen = int(log((t + 2) / 3, 2))\ngensize = 3 * 2 ** gen\nli = t + 2 - gensize\nprint(gensize - li)\n", "import sys\nt = int(input().strip())\nx = 1\nwhile 3 * (x - 1) < t:\n\tx <<= 1\nx = (x - 1) * 3\nif x == t:\n\tprint(1)\nelse:\n\tprint(1 + (x - t))\n", "import sys\nt = int(input().strip())\ncur = 1\ncounter = 3\nwhile True:\n\tval = cur + counter\n\tif val <= t:\n\t\tcur = val\n\t\tcounter = val + 2\n\telse:\n\t\tbreak\ncounter = counter - (t - cur)\nprint(counter)\n", "import math\nt = int(input())\nn = math.floor(math.log((t + 3) / 6, 2)) + 1\nk1 = 3 * 2 ** n\nk2 = 2 ** (n - 1) - 1\nk3 = t - 3 - 6 * k2\nk4 = k1 - k3 + 1\nprint(int(k4))\n", "from math import floor, log\nt = int(input())\nprint(3 * 2 ** floor(log((t - 1) / 3 + 1, 2)) - t + 3 * (2 ** floor(log((t - 1) / 3 + 1, 2)) - 1) + 1)\n", "import sys\nimport math\nt = int(input().strip())\nn = math.log10((t + 2) / 3) / math.log10(2)\nn = math.floor(n)\nnTop = math.floor(3 * math.pow(2, n))\ntTop = nTop - 2\ndiff = t - tTop\nprint(nTop - diff)\n", "import sys\nt = int(input().strip())\ntc = t\ncycle = -1\ntwopow = (tc + 2) // 3\nhighbit = 0\nwhile twopow > 0:\n\ttwopow = twopow >> 1\n\thighbit += 1\nhighbit = 0 if highbit == 0 else highbit - 1\ncounter = 3 * 2 ** (highbit + 1) - tc - 2\nprint(counter)\n", "import sys\nfrom math import *\nt = int(input().strip())\nnext_t = 3\nwhile t - next_t > 0:\n\tt -= next_t\n\tnext_t *= 2\nprint(next_t - (t - 1))\n", "import sys\ntarget = int(input().strip())\ncounter = 3\nt = 1\nwhile counter + t - 1 < target:\n\tt = t + counter\n\tcounter *= 2\nprint(counter - (target - t))\n", "from math import floor, log2\nt = int(input())\nres = 0\nn = log2((t + 2) / 3)\nif n.is_integer():\n\tres = int(3 * 2 ** n)\nelse:\n\tn = floor(n)\n\tres = 3 * 2 ** n + (t - (3 * 2 ** n - 2)) * -1\nprint(res)\n", "import sys\nt = int(input().strip())\nn = 3\nwhile True:\n\tif t <= n:\n\t\tbreak\n\tt -= n\n\tn *= 2\nprint(n - t + 1)\n", "import sys\nimport math\nt = int(input().strip())\ny = int(math.log2((t + 2) // 3))\nres = 3 * 2 ** (y + 1) - t - 2\nprint(res)\n", "import sys\nimport math\nt = int(input())\nn = math.floor(math.log(t / 3 + 1) / math.log(2))\ns = 3 * (2 ** n - 1)\nremainder = t - s\nanswer = 3 * 2 ** n - remainder + 1\nprint(answer)\n", "t = int(input().strip())\nn = 2\nwhile 3 * (n - 1) < t:\n\tn = 2 * n\nprint(3 * (n - 1) - t + 1)\n", "t = int(input()) - 1\nif t < 3:\n\tprint([3, 2, 1][t])\nelse:\n\tstartval = 3\n\twhile t >= startval:\n\t\tt -= startval\n\t\tstartval *= 2\n\tprint(startval - t)\n", "import sys\n\ndef stc(t):\n\tn = t\n\ti = 0\n\twhile n > 0:\n\t\tn = int(n / 2) - 1\n\t\ti = i + 1\n\tp = 3 * 2 ** (i - 1)\n\tn = t - p + 2\n\tprint(p - n)\nt = int(input().strip())\nstc(t)\n", "tf = int(input())\nt = []\nt.append(1)\nt.append(4)\nt.append(10)\nt.append(22)\nt.append(46)\nt.append(94)\nt.append(190)\nt.append(382)\nt.append(766)\nt.append(1534)\nt.append(3070)\nt.append(6142)\nt.append(12286)\nt.append(24574)\nt.append(49150)\nt.append(98302)\nt.append(196606)\nt.append(393214)\nt.append(786430)\nt.append(1572862)\nt.append(3145726)\nt.append(6291454)\nt.append(12582910)\nt.append(25165822)\nt.append(50331646)\nt.append(100663294)\nt.append(201326590)\nt.append(402653182)\nt.append(805306366)\nt.append(1610612734)\nt.append(3221225470)\nt.append(6442450942)\nt.append(12884901886)\nt.append(25769803774)\nt.append(51539607550)\nt.append(103079215102)\nt.append(206158430206)\nt.append(412316860414)\nt.append(824633720830)\nt.append(1000000000001)\nnv = next((x[0] for x in enumerate(t) if x[1] > tf)) - 1\nsum = 2 * t[nv] + 2 - tf\nprint(sum)\n", "import sys\nt = int(input().strip())\nc = 3\nt1 = 0\nwhile t1 < t:\n\tt1 = t1 + c\n\tc = 2 * c\nt1 = t1 - c\nt1 = t - t1\nc = c - t1 + 1\nprint(c)\n", "t = int(input())\na = 3\nwhile t > a:\n\tt -= a\n\ta <<= 1\nprint(a + 1 - t)\n", "import sys\nt = int(input().strip())\nd = 3\nwhile d < t:\n\tt = t - d\n\td = d * 2\nprint(d - t + 1)\n", "import sys\nT = int(input().strip())\nif T > 3:\n\tn = 0\n\twhile 3 * (2 ** n - 1) < T:\n\t\tn += 1\n\tt = T % (3 * (2 ** (n - 1) - 1))\n\tprint(1 + 3 * 2 ** (n - 1) - t)\nelse:\n\tprint(4 - T)\n", "import sys\nt = int(input().strip())\n(c, n, i) = (1, 3, 0)\nwhile c < t:\n\ti += 1\n\tnxt = (2 ** i - 1) * 3 + 1\n\tif t >= nxt:\n\t\t(c, n) = (nxt, nxt + 2)\n\telse:\n\t\tbreak\nprint(n - (t - c))\n", "t = int(input().strip())\n(t1, rem) = divmod(t - 1, 3)\ncycle = 0\nt0 = 1\nwhile t1:\n\tt0 += 3 * 2 ** cycle\n\tt1 = divmod(t1 - 1, 2)[0]\n\tcycle += 1\ncycle0 = 3 * 2 ** cycle\nprint(t0 + cycle0 - t)\n", "import sys\nt = int(input().strip())\ni = 3\nt1 = 3\nflag = 0\nwhile t1 < t:\n\ti = i * 2\n\tt1 = t1 + i\n\tflag = 1\nt1 -= i\nt1 += 1\nprint(i - (t - t1))\n", "import sys\nt = int(input().strip())\nn = 2\nwhile 3 * (n - 1) < t:\n\tn = 2 * n\nprint(3 * (n - 1) - t + 1)\n", "from math import log\nn = int(input())\nif n <= 3:\n\tc = 0\nelse:\n\tc = int(log(int((n - 1) / 3) + 1, 2))\nstart = 1 + 3 * (2 ** c - 1)\nval = 3 * 2 ** c\nprint(val - (n - start))\n", "import sys\nt = int(input().strip())\nn = 2\nwhile 3 * (n - 1) < t:\n\tn = n * 2\nprint(3 * (n - 1) - t + 1)\n", "import sys\nt = int(input())\nsum = 3\nn = 1\nwhile t > sum:\n\tn += 1\n\tsum = 3 * (pow(2, n) - 1)\nd = t - 3 * (pow(2, n - 1) - 1)\nprint(3 * pow(2, n - 1) - d + 1)\n", "ti = int(input())\n(t, v) = (1, 3)\nwhile 1:\n\ttemp = t + v\n\tif ti < temp:\n\t\tbreak\n\tt = temp\n\tv = t + 2\nprint(v - (ti - t))\n", "import sys\nt = int(input().strip())\nn = 2\nwhile 3 * (n - 1) < t:\n\tn = 2 * n\nprint(3 * (n - 1) - t + 1)\n", "import sys\nimport math\nt = int(input().strip())\nt -= 1\nlow = int(t / 3)\nlow_log = int(math.log(low + 1, 2))\nres = 2 ** low_log * 3 - t\nif low_log > 0:\n\tres += (2 ** low_log - 1) * 3\nprint(res)\n", "t = int(input())\ns = 3\nwhile t > s:\n\tt -= s\n\ts *= 2\nprint(s - t + 1)\n", "t = int(input())\nif t == 1:\n\tprint(3)\nelif t == 2:\n\tprint(2)\nelif t == 3:\n\tprint(1)\nelse:\n\tlis = []\n\tlis2 = [3]\n\tinit = 3\n\twhile True:\n\t\tif init > 10 ** 12:\n\t\t\tbreak\n\t\telse:\n\t\t\tlis.append(init)\n\t\tinit *= 2\n\tfor i in range(1, len(lis)):\n\t\tlis2.append(lis2[i - 1] + lis[i])\n\tup = -1\n\tpos = -1\n\tfor i in range(len(lis2)):\n\t\tif t < lis2[i]:\n\t\t\tup = lis2[i]\n\t\t\tpos = i\n\t\t\tbreak\n\tval = up - lis2[pos - 1] - (up - t)\n\tprint(lis[pos] - val + 1)\n", "import math\nt = int(input().strip())\nh = int(math.log(1 + t // 3, 2))\nprint(pow(2, h + 1) * 3 - 1 - t - 1)\n", "from math import *\n\ndef func():\n\tt = int(input())\n\td = []\n\tfor i in range(int(sqrt(t)) + 1):\n\t\td.append([0, 0])\n\ta = 1\n\tb = 3\n\td[0][0] = a\n\td[0][1] = b\n\ti = 1\n\twhile a < t:\n\t\td[i][1] = 2 * d[i - 1][1]\n\t\td[i][0] = d[i][1] - 2\n\t\ta = d[i][0]\n\t\tb = d[i][1]\n\t\tc = d[i - 1][0]\n\t\te = d[i - 1][1]\n\t\ti = i + 1\n\tif a == t:\n\t\tprint(b)\n\telse:\n\t\tprint(e - (t - c))\nfunc()\n", "import sys\n\ndef cycles(i):\n\tif i == 0:\n\t\treturn 3\n\treturn 3 * 2 ** i + cycles(i - 1)\nt = int(input().strip())\nn = 0\nwhile cycles(n) < t:\n\tn += 1\ncycle_start_time = 3 * (2 ** n - 1) + 1\ncycle = 3 * 2 ** n\nif t == cycle_start_time:\n\tprint(cycle)\nelse:\n\tprint(cycle - (t - cycle_start_time))\n", "import sys\nt = int(input().strip())\nstart = 3\nwhile t > start:\n\tt -= start\n\tstart *= 2\nprint(start - t + 1)\n", "import sys\nt = int(input().strip())\nc = 3\nwhile c < t:\n\tt = t - c\n\tc = c * 2\nprint(c - t + 1)\n", "time = int(input())\nt = 3\nc = 3\nwhile True:\n\tif t > time:\n\t\tbreak\n\telse:\n\t\tc *= 2\n\t\tt = t + c\nprint(t - time + 1)\n"]

difficulty: EASY

source: hacker rank

question:
There is a strange counter. At the first second, it displays the number $3$. Each second, the number displayed by decrements by $\mbox{1}$ until it reaches $\mbox{1}$. In next second, the timer resets to $2\times\textbf{the initial number for the prior cycle}$ and continues counting down. The diagram below shows the counter values for each time $\boldsymbol{\boldsymbol{t}}$ in the first three cycles:

![image](1.png)
Find and print the value displayed by the counter at time $\boldsymbol{\boldsymbol{t}}$.

Function Description

Complete the strangeCounter function in the editor below.

strangeCounter has the following parameter(s):

int t: an integer

Returns

int: the value displayed at time $\boldsymbol{\boldsymbol{t}}$

Input Format

A single integer, the value of $\boldsymbol{\boldsymbol{t}}$.

Constraints

$1\leq t\leq10^{12}$

Subtask

$1\leq t\leq10^5$ for $60\%$ of the maximum score.

Sample Input
4

Sample Output
6

Explanation

Time $t=4$ marks the beginning of the second cycle.  It is double the number displayed at the beginning of the first cycle:$2\times3=6$. This is shown in the diagram in the problem statement.

data_split: test


Intersection of Two Prisms

source: ACM International Collegiate Programming Contest, Asia Regional 2010, Japan

raw_problem:
Problem I: Intersection of Two Prisms

Suppose that P1 is an infinite-height prism whose axis is parallel to the z-axis, and P2 is also an infinite-height prism whose axis is parallel to the y-axis. P1 is defined by the polygon C1 which is the cross section of P1 and the xy-plane, and P2 is also defined by the polygon C2 which is the cross section of P2 and the xz-plane.

Figure I.1 shows two cross sections which appear as the first dataset in the sample input, and
Figure I.2 shows the relationship between the prisms and their cross sections.

Figure I.1: Cross sections of Prisms

Figure I.2: Prisms and their cross sections

Figure I.3: Intersection of two prisms

Figure I.3 shows the intersection of two prisms in Figure I.2, namely, P1 and P2.

Write a program which calculates the volume of the intersection of two prisms.

Input

The input is a sequence of datasets. The number of datasets is less than 200.

Each dataset is formatted as follows.

m n

x11 y11

x12 y12

.

.

.

x1m y1m

x21 z21

x22 z22

.

.

.

x2n z2n

m and n are integers (3 ≤ m ≤ 100, 3 ≤ n ≤ 100) which represent the numbers of the vertices of the polygons, C1 and C2, respectively.

x1i, y<sbu>1i, x2j and z2j are integers between -100 and 100, inclusive. (x1i, y1i) and (x2j , z2j) mean the i-th and j-th vertices' positions of C1 and C2 respectively.

The sequences of these vertex positions are given in the counterclockwise order either on the xy-plane or the xz-plane as in Figure I.1.

You may assume that all the polygons are convex, that is, all the interior angles of the polygons are less than 180 degrees. You may also assume that all the polygons are simple, that is, each polygon's boundary does not cross nor touch itself.

The end of the input is indicated by a line containing two zeros.

Output

For each dataset, output the volume of the intersection of the two prisms, P1 and P2, with a decimal representation in a line.

None of the output values may have an error greater than 0.001. The output should not contain any other extra characters.

Sample Input

4 3
7 2
3 3
0 2
3 1
4 2
0 1
8 1
4 4
30 2
30 12
2 12
2 2
15 2
30 8
13 14
2 8
8 5
13 5
21 7
21 9
18 15
11 15
6 10
6 8
8 5
10 12
5 9
15 6
20 10
18 12
3 3
5 5
10 3
10 10
20 8
10 15
10 8
4 4
-98 99
-99 -99
99 -98
99 97
-99 99
-98 -98
99 -99
96 99
0 0

Output for the Sample Input

4.708333333333333
1680.0000000000005
491.1500000000007
0.0
7600258.4847715655

solutions: ["import sys\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\ndef solve():\n    M, N = map(int, readline().split())\n    if M == N == 0:\n        return False\n    P = [list(map(int, readline().split())) for i in range(M)]\n    Q = [list(map(int, readline().split())) for i in range(N)]\n    xs = set()\n    xs.update(x for x, y in P)\n    xs.update(x for x, z in Q)\n    *X, = xs\n    X.sort()\n    def calc(x):\n        y_ma = -100; y_mi = 100\n        for i in range(M):\n            x0, y0 = P[i-1]; x1, y1 = P[i]\n            if x0 <= x <= x1 or x1 <= x <= x0:\n                if x0 == x1:\n                    y_ma = max(y_ma, max(y1, y0))\n                    y_mi = min(y_mi, min(y1, y0))\n                else:\n                    y = (x - x0)*(y1-y0) / (x1-x0) + y0\n                    y_ma = max(y_ma, y)\n                    y_mi = min(y_mi, y)\n        if not y_mi <= y_ma:\n            return 0\n        z_ma = -100; z_mi = 100\n        for i in range(N):\n            x0, z0 = Q[i-1]; x1, z1 = Q[i]\n            if x0 <= x <= x1 or x1 <= x <= x0:\n                if x0 == x1:\n                    z_ma = max(z_ma, max(z1, z0))\n                    z_mi = min(z_mi, min(z1, z0))\n                else:\n                    z = (x - x0)*(z1-z0) / (x1-x0) + z0\n                    z_ma = max(z_ma, z)\n                    z_mi = min(z_mi, z)\n        if not z_mi <= z_ma:\n            return 0\n        return (z_ma - z_mi) * (y_ma - y_mi)\n    ans = 0\n    L = len(X)\n    for i in range(L-1):\n        x0 = X[i]; x1 = X[i+1]\n        s0 = calc(x0); s1 = calc((x0 + x1)/2); s2 = calc(x1)\n        if s1 > 0:\n            ans += (x1 - x0) * (s0 + s2 + 4*s1) / 6\n    write(\"%.16f\\n\" % ans)\n    return True\nwhile solve():\n    ...\n", "# aoj 1313\nimport sys\ninput = sys.stdin.readline\n\n\n# the width of the polygon sliced at x\ndef width(X, Y, x):\n    n = len(X)\n    lb, ub = float('inf'), -float('inf')\n    for i in range(n):\n        x1, y1, x2, y2 = X[i], Y[i], X[(i+1) % n], Y[(i+1) % n]\n        if (x1-x)*(x2-x) <= 0 and x1 != x2:\n            y = y1 + (y2-y1) * (x-x1) / (x2-x1)\n            lb = min(lb, y)\n            ub = max(ub, y)\n    return max(0, ub-lb)\n\n\nwhile True:\n    m, n = map(int, input().split())\n    if m == n == 0:\n        break\n    X1 = [0] * m\n    Y1 = [0] * m\n    X2 = [0] * n\n    Z2 = [0] * n\n    for i in range(m):\n        X1[i], Y1[i] = map(int, input().split())\n    for i in range(n):\n        X2[i], Z2[i] = map(int, input().split())\n    min1, max1 = min(X1), max(X1)\n    min2, max2 = min(X2), max(X2)\n    X = X1 + X2\n    X.sort()\n    ans = 0\n    for i in range(len(X)-1):\n        a, b = X[i], X[i+1]\n        c = (a+b) / 2\n        if min1 <= c <= max1 and min2 <= c <= max2:\n            fa = width(X1, Y1, a) * width(X2, Z2, a)\n            fb = width(X1, Y1, b) * width(X2, Z2, b)\n            fc = width(X1, Y1, c) * width(X2, Z2, c)\n            ans += (b-a) / 6 * (fa+4*fc+fb)\n    print(ans)\n\n", "# aoj 1313\nimport sys\ninput = sys.stdin.readline\n\n\n# the width of the polygon sliced at x\ndef width(X, Y, x):\n    n = len(X)\n    lb, ub = float('inf'), -float('inf')\n    for i in range(n):\n        x1, y1, x2, y2 = X[i], Y[i], X[(i+1) % n], Y[(i+1) % n]\n        if (x1-x)*(x2-x) <= 0 and x1 != x2:\n            y = y1 + (y2-y1) * (x-x1) / (x2-x1)\n            lb = min(lb, y)\n            ub = max(ub, y)\n    return max(0, ub-lb)\n\n\nwhile True:\n    m, n = map(int, input().split())\n    if m == n == 0:\n        break\n    X1 = [0] * m\n    Y1 = [0] * m\n    X2 = [0] * n\n    Z2 = [0] * n\n    for i in range(m):\n        X1[i], Y1[i] = map(int, input().split())\n    for i in range(n):\n        X2[i], Z2[i] = map(int, input().split())\n    min1, max1 = min(X1), max(X1)\n    min2, max2 = min(X2), max(X2)\n    X = X1 + X2\n    X.sort()\n    ans = 0\n    for i in range(len(X)-1):\n        a, b = X[i], X[i+1]\n        c = (a+b) / 2\n        if min1 <= c <= max1 and min2 <= c <= max2:\n            fa = width(X1, Y1, a) * width(X2, Z2, a)\n            fb = width(X1, Y1, b) * width(X2, Z2, b)\n            fc = width(X1, Y1, c) * width(X2, Z2, c)\n            ans += (b-a) / 6 * (fa+4*fc+fb)\n    print(ans)\n\n", "\"\"\"\nhttps://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1313\n\u6559\u79d1\u66f8\u306e\u6307\u793a\u901a\u308a\u306b\u5b9f\u88c5\u3057\u305f\u3002\n\n\"\"\"\n\n\ndef width(polygon, x):\n    w = []\n\n    for i in range(len(polygon)):\n        p, q = polygon[i], polygon[(i + 1) % len(polygon)]\n        if p[0] == x:\n            w.append(p[1])\n        elif (p[0] < x and x < q[0]) or (p[0] > x and x > q[0]):\n            x0, y0 = p[0], p[1]\n            x1, y1 = q[0], q[1]\n            w.append(y0 + 1.0 * (y1 - y0) * (x - x0) / (x1 - x0))\n\n    assert len(w) > 0\n    return max(w) - min(w)\n\n\ndef volume(Pxy, Pxz, X):\n    X = sorted(set(X))\n    total = 0.0\n    xmin = max(min(Pxy)[0], min(Pxz)[0])\n    xmax = min(max(Pxy)[0], max(Pxz)[0])\n    for i in range(len(X) - 1):\n        a, b = X[i], X[i + 1]\n        if not (xmin <= a and a <= xmax and xmin <= b and b <= xmax):\n            continue\n        m = (a + b) / 2.0\n        va = width(Pxy, a) * width(Pxz, a)\n        vb = width(Pxy, b) * width(Pxz, b)\n        vm = width(Pxy, m) * width(Pxz, m)\n        area = ((b - a) / 6) * (va + 4 * vm + vb)\n        total += area\n    return total\n\n\ndef main():\n    Pxy = []\n    Pxz = []\n    X = []\n    while True:\n        m, n = map(int, input().split())\n        if m == 0 and n == 0:\n            break\n        for _ in range(m):\n            x, y = map(int, input().split())\n            Pxy.append((x, y))\n            X.append(x)\n        for _ in range(n):\n            x, z = map(int, input().split())\n            Pxz.append((x, z))\n            X.append(x)\n        print(volume(Pxy, Pxz, X))\n\n        Pxy = []\n        Pxz = []\n        X = []\n\n\nif __name__ == \"__main__\":\n    main()\n\n", "def width(_X, _Y, _n, _x):\n    lb = float(\"inf\")\n    ub = -float(\"inf\")\n\n    for j in range(0, _n):\n        x1 = _X[j]\n        y1 = _Y[j]\n        x2 = _X[(j + 1) % _n]\n        y2 = _Y[(j + 1) % _n]\n\n        if (x1 - _x) * (x2 - _x) <= 0 and x1 != x2:\n            y = y1 + (y2 - y1) * (_x - x1) / (x2 - x1)\n            lb = min(lb, y)\n            ub = max(ub, y)\n\n    return max(0, ub - lb)\n\n\nif __name__ == '__main__':\n    while True:\n        M, N = list(map(int, input().split()))\n        if M == 0 and N == 0:\n            break\n\n        X1 = []\n        Y1 = []\n        X2 = []\n        Z2 = []\n        for i in range(M):\n            tmp_x1, tmp_y1 = list(map(int, input().split()))\n            X1.append(tmp_x1)\n            Y1.append(tmp_y1)\n\n        for i in range(N):\n            tmp_x2, tmp_z2 = list(map(int, input().split()))\n            X2.append(tmp_x2)\n            Z2.append(tmp_z2)\n\n        min1 = min(X1)\n        max1 = max(X1)\n        min2 = min(X2)\n        max2 = max(X2)\n\n        xs = X1 + X2\n        xs = sorted(xs)\n        res = 0\n        for i in range(0, len(xs) - 1):\n            a = xs[i]\n            b = xs[i + 1]\n            c = (a + b) / 2\n            # print(\"a\" + str(a) + \"b\" + str(b) + \"c\" + str(c))\n            if min1 <= c <= max1 and min2 <= c <= max2:\n                fa = width(X1, Y1, M, a) * width(X2, Z2, N, a)\n                fb = width(X1, Y1, M, b) * width(X2, Z2, N, b)\n                fc = width(X1, Y1, M, c) * width(X2, Z2, N, c)\n                res += ((b - a) / 6) * (fa + 4 * fc + fb)\n                # print(res)\n\n        print(res)\n", "def width(X,Y,x):\n     n = len(X)\n     lb,ub = float('inf'),-float('inf')\n     for i in range(n):\n          x1,y1,x2,y2 = X[i],Y[i],X[(i+1)%n],Y[(i+1)%n]\n          if (x1-x)*(x2-x) <= 0 and x1 != x2:\n               y = y1 + (y2-y1)*(x-x1)/(x2-x1)\n               lb = min(lb,y)\n               ub = max(ub,y)\n     return max(0,ub-lb)\n\nwhile 1:\n     M,N = map(int,input().split())\n     if not (M and N):\n          break\n     X1 = [0]*M\n     Y1 = [0]*M\n     X2 = [0]*N\n     Z2 = [0]*N\n     XS = [0]*N\n     for i in range(M):\n          X1[i],Y1[i] = map(int,input().split())\n     for i in range(N):\n          X2[i],Z2[i] = map(int,input().split())\n     XS = X1+X2\n     XS.sort()\n     min1,max1 = min(X1),max(X1)\n     min2,max2 = min(X2),max(X2)\n     res = 0\n     for i in range(len(XS)-1):\n          a = XS[i]\n          b = XS[i+1]\n          c = (a+b)/2\n          if min1 <= c <= max1 and min2 <= c <= max2:\n               fa = width(X1,Y1,a)*width(X2,Z2,a)\n               fb = width(X1,Y1,b)*width(X2,Z2,b)\n               fc = width(X1,Y1,c)*width(X2,Z2,c)\n               res += (b-a)/6 * (fa+4*fc+fb)\n     print('%.10f'%res)\n\n"]

source: aizu

question:
Problem I: Intersection of Two Prisms

Suppose that P_{1} is an infinite-height prism whose axis is parallel to the z-axis, and P_{2} is also an infinite-height prism whose axis is parallel to the y-axis. P_{1} is defined by the polygon C_{1} which is the cross section of P_{1} and the xy-plane, and P_{2} is also defined by the polygon C_{2} which is the cross section of P_{2} and the xz-plane.

Figure I.1 shows two cross sections which appear as the first dataset in the sample input, and
Figure I.2 shows the relationship between the prisms and their cross sections.

![image](1.png)
Figure I.1: Cross sections of Prisms
![image](2.png)
Figure I.2: Prisms and their cross sections
![image](3.png)
Figure I.3: Intersection of two prisms

Figure I.3 shows the intersection of two prisms in Figure I.2, namely, P_{1} and P_{2}.

Write a program which calculates the volume of the intersection of two prisms.

Input

The input is a sequence of datasets. The number of datasets is less than 200.

Each dataset is formatted as follows.

m n
x_{11} y_{11}
x_{12} y_{12}
.
.
.
x_{1m} y_{1m}
x_{21} z_{21}
x_{22} z_{22}
.
.
.
x_{2n} z_{2n}

m and n are integers (3 ≤ m ≤ 100, 3 ≤ n ≤ 100) which represent the numbers of the vertices of the polygons, C_{1} and C_{2}, respectively.

x_{1i}, y1i, x_{2j} and z_{2j} are integers between -100 and 100, inclusive. (x_{1i}, y_{1i}) and (x_{2j} , z_{2j}) mean the i-th and j-th vertices' positions of C_{1} and C_{2} respectively.

The sequences of these vertex positions are given in the counterclockwise order either on the xy-plane or the xz-plane as in Figure I.1.

You may assume that all the polygons are convex, that is, all the interior angles of the polygons are less than 180 degrees. You may also assume that all the polygons are simple, that is, each polygon's boundary does not cross nor touch itself.

The end of the input is indicated by a line containing two zeros.

Output

For each dataset, output the volume of the intersection of the two prisms, P_{1} and P_{2}, with a decimal representation in a line.

None of the output values may have an error greater than 0.001. The output should not contain any other extra characters.

Sample Input

4 3
7 2
3 3
0 2
3 1
4 2
0 1
8 1
4 4
30 2
30 12
2 12
2 2
15 2
30 8
13 14
2 8
8 5
13 5
21 7
21 9
18 15
11 15
6 10
6 8
8 5
10 12
5 9
15 6
20 10
18 12
3 3
5 5
10 3
10 10
20 8
10 15
10 8
4 4
-98 99
-99 -99
99 -98
99 97
-99 99
-98 -98
99 -99
96 99
0 0

Output for the Sample Input

4.708333333333333
1680.0000000000005
491.1500000000007
0.0
7600258.4847715655

image_tags:
3D Geometry
3D Geometry
3D Geometry

data_split: test


solutions: ["from collections import deque\n\nclass Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tgrids = targetGrid\n\t\tnum_to_range = dict()\n\t\tfor (i, row) in enumerate(targetGrid):\n\t\t\tfor (j, val) in enumerate(row):\n\t\t\t\tif val not in num_to_range:\n\t\t\t\t\tnum_to_range[val] = [i, i, j, j]\n\t\t\t\tnum_to_range[val][0] = min(num_to_range[val][0], i)\n\t\t\t\tnum_to_range[val][1] = max(num_to_range[val][1], i)\n\t\t\t\tnum_to_range[val][2] = min(num_to_range[val][2], j)\n\t\t\t\tnum_to_range[val][3] = max(num_to_range[val][3], j)\n\t\tm = len(grids)\n\t\tn = len(grids[0])\n\t\tgrid_list = [[list() for j in range(n)] for i in range(m)]\n\t\tfor (num, val) in list(num_to_range.items()):\n\t\t\tfor i in range(val[0], val[1] + 1):\n\t\t\t\tfor j in range(val[2], val[3] + 1):\n\t\t\t\t\tgrid_list[i][j].append(num)\n\t\tpaths = {val: set() for val in list(num_to_range)}\n\t\tfor (i, row) in enumerate(targetGrid):\n\t\t\tfor (j, val) in enumerate(row):\n\t\t\t\tfor parent in grid_list[i][j]:\n\t\t\t\t\tif parent != val:\n\t\t\t\t\t\tpaths[parent].add(val)\n\t\tparent_counter = {val: 0 for val in list(num_to_range)}\n\t\tfor (parent, childs) in list(paths.items()):\n\t\t\tfor child in childs:\n\t\t\t\tparent_counter[child] += 1\n\t\tqueue = deque()\n\t\tfor (child, cnt) in list(parent_counter.items()):\n\t\t\tif cnt == 0:\n\t\t\t\tqueue.append(child)\n\t\tseen = set()\n\t\twhile queue:\n\t\t\tparent = queue.popleft()\n\t\t\tseen.add(parent)\n\t\t\tfor child in paths[parent]:\n\t\t\t\tparent_counter[child] -= 1\n\t\t\t\tif parent_counter[child] == 0:\n\t\t\t\t\tqueue.append(child)\n\t\treturn len(seen) == len(num_to_range)\n", "SIDE_LEFT = 'left'\nSIDE_RIGHT = 'right'\nSIDE_TOP = 'top'\nSIDE_BOTTOM = 'bottom'\n\nclass Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tcolour_set = set()\n\t\tfor row in targetGrid:\n\t\t\tfor cell in row:\n\t\t\t\tcolour_set.add(cell)\n\t\tcolour_overlap_info = self.get_colour_boundaries_and_overlap(targetGrid, colour_set)\n\t\tremaining_colours = colour_set.copy()\n\t\tuntangled_colours = set()\n\t\twhile remaining_colours:\n\t\t\tnew_untangled_colours = set()\n\t\t\tfor colour in remaining_colours:\n\t\t\t\tcolour_overlap_info[colour] -= untangled_colours\n\t\t\t\tif len(colour_overlap_info[colour]) == 0:\n\t\t\t\t\tnew_untangled_colours.add(colour)\n\t\t\tif new_untangled_colours:\n\t\t\t\tuntangled_colours |= new_untangled_colours\n\t\t\t\tremaining_colours -= new_untangled_colours\n\t\t\telse:\n\t\t\t\tbreak\n\t\treturn len(remaining_colours) == 0\n\n\tdef get_colour_boundaries_and_overlap(self, targetGrid, colour_set):\n\t\tcolours_info = {}\n\t\tfor colour in colour_set:\n\t\t\tboundaries = {}\n\t\t\tfor (row_index, row) in enumerate(targetGrid):\n\t\t\t\tfor (col_index, cell) in enumerate(row):\n\t\t\t\t\tif cell == colour:\n\t\t\t\t\t\tif not boundaries:\n\t\t\t\t\t\t\tboundaries = {SIDE_LEFT: col_index, SIDE_RIGHT: col_index, SIDE_TOP: row_index, SIDE_BOTTOM: row_index}\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tif boundaries[SIDE_LEFT] > col_index:\n\t\t\t\t\t\t\t\tboundaries[SIDE_LEFT] = col_index\n\t\t\t\t\t\t\tif boundaries[SIDE_RIGHT] < col_index:\n\t\t\t\t\t\t\t\tboundaries[SIDE_RIGHT] = col_index\n\t\t\t\t\t\t\tif boundaries[SIDE_BOTTOM] < row_index:\n\t\t\t\t\t\t\t\tboundaries[SIDE_BOTTOM] = row_index\n\t\t\toverlapping_colours = set()\n\t\t\tfor row_index in range(boundaries[SIDE_TOP], boundaries[SIDE_BOTTOM] + 1):\n\t\t\t\tfor col_index in range(boundaries[SIDE_LEFT], boundaries[SIDE_RIGHT] + 1):\n\t\t\t\t\tcell = targetGrid[row_index][col_index]\n\t\t\t\t\tif cell != colour:\n\t\t\t\t\t\toverlapping_colours.add(cell)\n\t\t\tcolours_info[colour] = overlapping_colours\n\t\treturn colours_info\n", "class Solution:\n\tfrom collections import defaultdict, Counter\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tshapes = {}\n\t\tfor (i, row) in enumerate(targetGrid):\n\t\t\tfor (j, color) in enumerate(row):\n\t\t\t\tif color not in shapes:\n\t\t\t\t\tshapes[color] = [i, i, j, j]\n\t\t\t\telse:\n\t\t\t\t\tshapes[color][0] = min(shapes[color][0], i)\n\t\t\t\t\tshapes[color][1] = max(shapes[color][1], i)\n\t\t\t\t\tshapes[color][2] = min(shapes[color][2], j)\n\t\t\t\t\tshapes[color][3] = max(shapes[color][3], j)\n\t\tedges = defaultdict(set)\n\t\tfor (color, [min_r, max_r, min_c, max_c]) in list(shapes.items()):\n\t\t\tfor r in range(min_r, max_r + 1):\n\t\t\t\tfor c in range(min_c, max_c + 1):\n\t\t\t\t\tif targetGrid[r][c] != color:\n\t\t\t\t\t\tedges[color].add(targetGrid[r][c])\n\t\tdeps = Counter()\n\t\tfor (_, ts) in list(edges.items()):\n\t\t\tfor c in ts:\n\t\t\t\tdeps[c] += 1\n\t\tlayer = [c for c in list(shapes.keys()) if not deps[c]]\n\t\twhile layer:\n\t\t\tnew_layer = []\n\t\t\tfor c in layer:\n\t\t\t\tfor t in edges[c]:\n\t\t\t\t\tdeps[t] -= 1\n\t\t\t\t\tif not deps[t]:\n\t\t\t\t\t\tnew_layer.append(t)\n\t\t\tlayer = new_layer\n\t\treturn all((not v for (c, v) in list(deps.items())))\n", "class Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\ta = [(math.inf, math.inf, -math.inf, -math.inf) for _ in range(61)]\n\t\tsource = [[0] * len(targetGrid[0]) for _ in targetGrid]\n\t\tfor i in range(len(targetGrid)):\n\t\t\tfor j in range(len(targetGrid[i])):\n\t\t\t\ta[targetGrid[i][j]] = (min(a[targetGrid[i][j]][0], j), min(a[targetGrid[i][j]][1], i), max(a[targetGrid[i][j]][2], j), max(a[targetGrid[i][j]][3], i))\n\t\tgr = defaultdict(set)\n\t\tfor p in range(len(a)):\n\t\t\t(x, y, z, t) = a[p]\n\t\t\tif x != math.inf:\n\t\t\t\tfor i in range(y, t + 1):\n\t\t\t\t\tfor j in range(x, z + 1):\n\t\t\t\t\t\tif targetGrid[i][j] != p:\n\t\t\t\t\t\t\tgr[p].add(targetGrid[i][j])\n\t\tvisited = set()\n\t\tinp = set()\n\n\t\tdef dfs(k):\n\t\t\tinp.add(k)\n\t\t\tfor x in gr[k]:\n\t\t\t\tif x in inp:\n\t\t\t\t\treturn False\n\t\t\t\telif x not in visited and (not dfs(x)):\n\t\t\t\t\treturn False\n\t\t\tinp.remove(k)\n\t\t\tvisited.add(k)\n\t\t\treturn True\n\t\tfor i in range(61):\n\t\t\tif i not in visited and (not dfs(i)):\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\ttop = defaultdict(lambda : float('inf'))\n\t\tbottom = defaultdict(lambda : -1)\n\t\tleft = defaultdict(lambda : float('inf'))\n\t\tright = defaultdict(lambda : -1)\n\t\tfor row in range(len(targetGrid)):\n\t\t\tfor col in range(len(targetGrid[row])):\n\t\t\t\tcolor = targetGrid[row][col]\n\t\t\t\ttop[color] = min(top[color], row)\n\t\t\t\tbottom[color] = max(bottom[color], row)\n\t\t\t\tleft[color] = min(left[color], col)\n\t\t\t\tright[color] = max(right[color], col)\n\t\tedges = defaultdict(list)\n\t\tfor row in range(len(targetGrid)):\n\t\t\tfor col in range(len(targetGrid[row])):\n\t\t\t\tcolor = targetGrid[row][col]\n\t\t\t\tfor otherColor in top:\n\t\t\t\t\tif color != otherColor and top[otherColor] <= row <= bottom[otherColor] and (left[otherColor] <= col <= right[otherColor]):\n\t\t\t\t\t\tedges[otherColor].append(color)\n\t\tnodestates = [0 for _ in range(61)]\n\n\t\tdef dfs(current):\n\t\t\tnodestates[current] = 1\n\t\t\tfor neighbor in edges[current]:\n\t\t\t\tif nodestates[neighbor] == 1:\n\t\t\t\t\treturn True\n\t\t\t\telif nodestates[neighbor] == 0:\n\t\t\t\t\tdfs(neighbor)\n\t\t\tnodestates[current] = 2\n\t\tcycleDetected = False\n\t\tfor node in top:\n\t\t\tif nodestates[node] == 0:\n\t\t\t\tif dfs(node):\n\t\t\t\t\tcycleDetected = True\n\t\t\t\t\tbreak\n\t\treturn not cycleDetected\n", "class Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tboundaries = [(math.inf, math.inf, -math.inf, -math.inf) for _ in range(61)]\n\t\tfor i in range(len(targetGrid)):\n\t\t\tfor j in range(len(targetGrid[i])):\n\t\t\t\tcolor = targetGrid[i][j]\n\t\t\t\t(min_i, min_j, max_i, max_j) = boundaries[color]\n\t\t\t\tboundaries[color] = (min(min_i, i), min(min_j, j), max(max_i, i), max(max_j, j))\n\t\tgraph = defaultdict(set)\n\t\tfor color in range(len(boundaries)):\n\t\t\t(min_i, min_j, max_i, max_j) = boundaries[color]\n\t\t\tif min_i != math.inf:\n\t\t\t\tfor i in range(min_i, max_i + 1):\n\t\t\t\t\tfor j in range(min_j, max_j + 1):\n\t\t\t\t\t\tif targetGrid[i][j] != color:\n\t\t\t\t\t\t\tgraph[color].add(targetGrid[i][j])\n\t\tvisited = set()\n\t\tin_progress = set()\n\n\t\tdef dfs(source):\n\t\t\tin_progress.add(source)\n\t\t\tfor vertex in graph[source]:\n\t\t\t\tif vertex in in_progress or (vertex not in visited and (not dfs(vertex))):\n\t\t\t\t\treturn False\n\t\t\tin_progress.remove(source)\n\t\t\tvisited.add(source)\n\t\t\treturn True\n\t\tfor color in range(61):\n\t\t\tif color not in visited and (not dfs(color)):\n\t\t\t\treturn False\n\t\treturn True\n", "def walk(grid):\n\tfor (i, row) in enumerate(grid):\n\t\tfor (j, elem) in enumerate(row):\n\t\t\tyield ((i, j), elem)\n\ndef extend(bound, ij):\n\t(i, j) = ij\n\tif bound is None:\n\t\treturn (ij, ij)\n\telse:\n\t\t((i0, j0), (i1, j1)) = bound\n\t\treturn ((min(i0, i), min(j0, j)), (max(i1, i), max(j1, j)))\n\ndef contains(bound, ij):\n\t(i, j) = ij\n\t((i0, j0), (i1, j1)) = bound\n\treturn i0 <= i <= i1 and j0 <= j <= j1\n\ndef has_toposort(prereq):\n\troots = [x for x in prereq if not prereq[x]]\n\twhile roots:\n\t\tr = roots.pop()\n\t\tdel prereq[r]\n\t\tfor c in prereq:\n\t\t\tif r in prereq[c]:\n\t\t\t\tprereq[c].remove(r)\n\t\t\t\tif not prereq[c]:\n\t\t\t\t\troots.append(c)\n\treturn not prereq\n\ndef printable(grid):\n\t(m, n) = (len(grid), len(grid[0]))\n\tassert m >= 1 and n >= 1\n\tcolors = {c for row in grid for c in row}\n\tbounds = {c: None for c in colors}\n\tfor ((i, j), c) in walk(grid):\n\t\tbounds[c] = extend(bounds[c], (i, j))\n\tprereq = {c: set() for c in colors}\n\tfor ((i, j), c) in walk(grid):\n\t\tfor c2 in colors:\n\t\t\tif c2 == c:\n\t\t\t\tcontinue\n\t\t\tif contains(bounds[c2], (i, j)):\n\t\t\t\tprereq[c].add(c2)\n\treturn has_toposort(prereq)\n\nclass Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\treturn printable(targetGrid)\n", "from collections import defaultdict\n\nclass Solution:\n\n\tdef all_same(self, left, right, bottom, top, color):\n\t\tfor i in range(bottom, top + 1):\n\t\t\tfor j in range(left, right + 1):\n\t\t\t\tif self.grid[i][j] and self.grid[i][j] != color:\n\t\t\t\t\treturn False\n\t\treturn True\n\n\tdef fill(self, left, right, bottom, top):\n\t\tfor i in range(bottom, top + 1):\n\t\t\tfor j in range(left, right + 1):\n\t\t\t\tself.grid[i][j] = 0\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tself.rect = defaultdict(lambda : [10 ** 9, -10 ** 9, 10 ** 9, -10 ** 9])\n\t\tfor (i, row) in enumerate(targetGrid):\n\t\t\tfor (j, color) in enumerate(row):\n\t\t\t\tself.rect[color][0] = min(self.rect[color][0], j)\n\t\t\t\tself.rect[color][1] = max(self.rect[color][1], j)\n\t\t\t\tself.rect[color][2] = min(self.rect[color][2], i)\n\t\t\t\tself.rect[color][3] = max(self.rect[color][3], i)\n\t\tself.grid = targetGrid\n\t\twhile self.rect:\n\t\t\tfor color in self.rect:\n\t\t\t\t(left, right, bottom, top) = self.rect[color]\n\t\t\t\tif self.all_same(left, right, bottom, top, color):\n\t\t\t\t\tself.fill(left, right, bottom, top)\n\t\t\t\t\tself.rect.pop(color)\n\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef isPrintable(self, A: List[List[int]]) -> bool:\n\t\t(m, n) = (len(A), len(A[0]))\n\t\tc = collections.Counter()\n\t\tdic = collections.defaultdict(lambda : [m + n, -1, m + n, -1, 0])\n\t\tseen = set()\n\t\tremoved = set()\n\t\tfor (i, row) in enumerate(A):\n\t\t\tfor (j, x) in enumerate(row):\n\t\t\t\tdic[x][0] = min(dic[x][0], i)\n\t\t\t\tdic[x][2] = min(dic[x][2], j)\n\t\t\t\tdic[x][1] = max(dic[x][1], i)\n\t\t\t\tdic[x][3] = max(dic[x][3], j)\n\t\t\t\tdic[x][4] += 1\n\t\t\t\tseen.add(x)\n\n\t\tdef helper(x):\n\t\t\treturn abs((dic[x][1] - dic[x][0] + 1) * (dic[x][3] - dic[x][2] + 1) - dic[x][4])\n\t\ttemp = sorted(seen, key=helper)\n\t\tk = 0\n\t\twhile len(temp) != len(removed):\n\t\t\tfor t in temp:\n\t\t\t\tif t in removed:\n\t\t\t\t\tcontinue\n\t\t\t\tif helper(t) == 0:\n\t\t\t\t\tremoved.add(t)\n\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\t(a, b, c, d, total) = dic[t]\n\t\t\t\t\tflag = True\n\t\t\t\t\tfor i in range(a, b + 1):\n\t\t\t\t\t\tfor j in range(c, d + 1):\n\t\t\t\t\t\t\tif A[i][j] != t and A[i][j] not in removed:\n\t\t\t\t\t\t\t\tflag = False\n\t\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\tif not flag:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\tif flag:\n\t\t\t\t\t\tremoved.add(t)\n\t\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tbreak\n\t\treturn len(temp) == len(removed)\n", "class Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tcoverage = dict()\n\t\tfor y in range(len(targetGrid)):\n\t\t\tfor x in range(len(targetGrid[y])):\n\t\t\t\tval = targetGrid[y][x]\n\t\t\t\tif val not in coverage:\n\t\t\t\t\tcoverage[val] = (y, x, y, x)\n\t\t\t\telse:\n\t\t\t\t\tasdf = coverage[val]\n\t\t\t\t\tasdf = (min(asdf[0], y), min(asdf[1], x), max(asdf[2], y), max(asdf[3], x))\n\t\t\t\t\tcoverage[val] = asdf\n\t\tprint(coverage)\n\t\tbefore = dict()\n\t\tdone = set()\n\t\tfor color in coverage:\n\t\t\tasdf = coverage[color]\n\t\t\ts = set()\n\t\t\tfor y in range(asdf[0], asdf[2] + 1):\n\t\t\t\tfor x in range(asdf[1], asdf[3] + 1):\n\t\t\t\t\ts.add(targetGrid[y][x])\n\t\t\t\tif color in s:\n\t\t\t\t\ts.remove(color)\n\t\t\tbefore[color] = s\n\t\tprint(before)\n\t\twhile len(before) > 0:\n\t\t\tgotOne = False\n\t\t\tfor color in list(before.keys()):\n\t\t\t\tdependencies = before[color]\n\t\t\t\tdependencies = dependencies - done\n\t\t\t\tif len(dependencies) == 0:\n\t\t\t\t\tbefore.pop(color)\n\t\t\t\t\tdone.add(color)\n\t\t\t\t\tgotOne = True\n\t\t\t\telse:\n\t\t\t\t\tbefore[color] = dependencies\n\t\t\tif gotOne == False:\n\t\t\t\treturn False\n\t\treturn True\n", "import queue\n\nclass Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tcolor_bounds = {}\n\t\tfor (i, row) in enumerate(targetGrid):\n\t\t\tfor (j, color) in enumerate(row):\n\t\t\t\tif not color in color_bounds:\n\t\t\t\t\tcolor_bounds[color] = {'row': [1000000.0, -1000000.0], 'col': [1000000.0, -1000000.0]}\n\t\t\t\tcolor_bounds[color]['row'][0] = min(color_bounds[color]['row'][0], i)\n\t\t\t\tcolor_bounds[color]['row'][1] = max(color_bounds[color]['row'][1], i)\n\t\t\t\tcolor_bounds[color]['col'][0] = min(color_bounds[color]['col'][0], j)\n\t\t\t\tcolor_bounds[color]['col'][1] = max(color_bounds[color]['col'][1], j)\n\t\tgraph = collections.defaultdict(list)\n\t\tdegree = Counter()\n\t\tfor (color, bounds) in list(color_bounds.items()):\n\t\t\tseen = set()\n\t\t\tfor i in range(bounds['row'][0], bounds['row'][1] + 1):\n\t\t\t\tfor j in range(bounds['col'][0], bounds['col'][1] + 1):\n\t\t\t\t\tother_color = targetGrid[i][j]\n\t\t\t\t\tif other_color != color and other_color not in seen:\n\t\t\t\t\t\tseen.add(other_color)\n\t\t\t\t\t\tgraph[other_color].append(color)\n\t\t\t\t\t\tdegree[color] += 1\n\t\tq = queue.Queue()\n\t\tfor color in list(color_bounds.keys()):\n\t\t\tif degree[color] == 0:\n\t\t\t\tq.put(color)\n\t\tprocessed_nodes = 0\n\t\twhile not q.empty():\n\t\t\tcolor = q.get()\n\t\t\tprocessed_nodes += 1\n\t\t\tfor next_color in graph[color]:\n\t\t\t\tdegree[next_color] -= 1\n\t\t\t\tif degree[next_color] == 0:\n\t\t\t\t\tq.put(next_color)\n\t\treturn processed_nodes == len(color_bounds)\n", "class Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tR = len(targetGrid)\n\t\tC = len(targetGrid[0])\n\t\tWHITE = 0\n\t\tGRAY = 1\n\t\tBLACK = 2\n\t\tboxes = collections.defaultdict(lambda : [61, 61, -1, -1])\n\t\tfor (r, row) in enumerate(targetGrid):\n\t\t\tfor (c, v) in enumerate(row):\n\t\t\t\tboxes[v][0] = min(boxes[v][0], r)\n\t\t\t\tboxes[v][1] = min(boxes[v][1], c)\n\t\t\t\tboxes[v][2] = max(boxes[v][2], r)\n\t\t\t\tboxes[v][3] = max(boxes[v][3], c)\n\t\tgraph = {color: set() for color in boxes}\n\t\tfor (color, (r1, c1, r2, c2)) in boxes.items():\n\t\t\tfor r in range(r1, r2 + 1):\n\t\t\t\tfor c in range(c1, c2 + 1):\n\t\t\t\t\tif targetGrid[r][c] != color:\n\t\t\t\t\t\tgraph[color].add(targetGrid[r][c])\n\t\tstate = collections.defaultdict(int)\n\n\t\tdef dfs(u):\n\t\t\tstate[u] = GRAY\n\t\t\tfor v in graph[u]:\n\t\t\t\tif state[v] == WHITE:\n\t\t\t\t\tif not dfs(v):\n\t\t\t\t\t\treturn False\n\t\t\t\telif state[v] == GRAY:\n\t\t\t\t\treturn False\n\t\t\tstate[u] = BLACK\n\t\t\treturn True\n\t\tfor s in graph:\n\t\t\tif state[s] == WHITE:\n\t\t\t\tif not dfs(s):\n\t\t\t\t\treturn False\n\t\treturn True\n", "class Solution:\n\n\tdef isPrintable(self, M: List[List[int]]) -> bool:\n\t\tcolorA = collections.defaultdict(lambda : [61, 61, -1, -1])\n\t\tfor (r, row) in enumerate(M):\n\t\t\tfor (c, color) in enumerate(row):\n\t\t\t\tcolorA[color][0] = min(colorA[color][0], r)\n\t\t\t\tcolorA[color][1] = min(colorA[color][1], c)\n\t\t\t\tcolorA[color][2] = max(colorA[color][2], r)\n\t\t\t\tcolorA[color][3] = max(colorA[color][3], c)\n\t\tgraph = {color: set() for color in colorA}\n\t\tfor (color, (top, left, bottom, right)) in list(colorA.items()):\n\t\t\tfor r in range(top, bottom + 1):\n\t\t\t\tfor c in range(left, right + 1):\n\t\t\t\t\tif M[r][c] != color:\n\t\t\t\t\t\tgraph[color].add(M[r][c])\n\t\t(W, G, B) = (0, 1, 2)\n\t\tstate = collections.defaultdict(int)\n\n\t\tdef check(node):\n\t\t\tstate[node] = G\n\t\t\tfor nei in graph[node]:\n\t\t\t\tif state[nei] == W:\n\t\t\t\t\tif not check(nei):\n\t\t\t\t\t\treturn False\n\t\t\t\tif state[nei] == G:\n\t\t\t\t\treturn False\n\t\t\tstate[node] = B\n\t\t\treturn True\n\t\tfor node in graph:\n\t\t\tif state[node] == W:\n\t\t\t\tif not check(node):\n\t\t\t\t\treturn False\n\t\treturn True\n", "class Grid(object):\n\n\tdef __init__(self):\n\t\tself.ps = set()\n\t\tself.lx = 100\n\t\tself.ly = 100\n\t\tself.rx = 0\n\t\tself.ry = 0\n\n\tdef add(self, x, y):\n\t\tself.ps.add((x, y))\n\t\tself.lx = min(self.lx, x)\n\t\tself.ly = min(self.ly, y)\n\t\tself.rx = max(self.rx, x)\n\t\tself.ry = max(self.ry, y)\n\n\tdef is_full(self):\n\t\treturn len(self.ps) == (self.rx - self.lx + 1) * (self.ry - self.ly + 1)\n\n\tdef overlap(self, grid):\n\t\tflag = self.rx < grid.lx\n\t\tflag = flag and self.ry > grid.ly\n\t\tflag = flag and self.lx > grid.rx\n\t\tflag = flag and self.ly < grid.ry\n\t\treturn not flag\n\n\tdef contain(self, grid):\n\t\tif not self.overlap(grid):\n\t\t\treturn False\n\t\tfor (x, y) in grid.ps:\n\t\t\tif self.lx <= x <= self.rx and self.ly <= y <= self.ry:\n\t\t\t\treturn True\n\t\treturn False\n\n\tdef __str__(self):\n\t\treturn '({0.lx}, {0.ly}), ({0.rx}, {0.ry})'.format(self)\n\nclass Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tgrids = defaultdict(Grid)\n\t\tfor (x, row) in enumerate(targetGrid):\n\t\t\tfor (y, c) in enumerate(row):\n\t\t\t\tgrids[c].add(x, y)\n\t\tcolors = grids.keys()\n\t\t(graph, degree) = (defaultdict(set), defaultdict(int))\n\t\tvis = set()\n\t\tfor c1 in colors:\n\t\t\tfor c2 in colors:\n\t\t\t\tif c1 == c2 or (c1, c2) in vis:\n\t\t\t\t\tcontinue\n\t\t\t\tvis.add((c1, c2))\n\t\t\t\tif grids[c1].contain(grids[c2]):\n\t\t\t\t\tgraph[c1].add(c2)\n\t\t\t\t\tdegree[c2] += 1\n\t\tq = []\n\t\tfor c in colors:\n\t\t\tif degree[c] == 0:\n\t\t\t\tq.append(c)\n\t\tvis = []\n\t\twhile q:\n\t\t\tc1 = q.pop()\n\t\t\tvis.append(c1)\n\t\t\tfor c2 in graph[c1]:\n\t\t\t\tdegree[c2] -= 1\n\t\t\t\tif degree[c2] == 0:\n\t\t\t\t\tq.append(c2)\n\t\treturn len(vis) == len(colors)\n", "class Solution:\n\n\tdef isPrintable(self, target: List[List[int]]) -> bool:\n\t\t(TOP, LEFT, BOTTOM, RIGHT) = (0, 1, 2, 3)\n\t\t(M, N) = (len(target), len(target[0]))\n\t\tboxes = defaultdict(lambda : [math.inf, math.inf, -math.inf, -math.inf])\n\t\tfor (i, row) in enumerate(target):\n\t\t\tfor (j, x) in enumerate(row):\n\t\t\t\tboxes[x][TOP] = min(boxes[x][TOP], i)\n\t\t\t\tboxes[x][LEFT] = min(boxes[x][LEFT], j)\n\t\t\t\tboxes[x][BOTTOM] = max(boxes[x][BOTTOM], i)\n\t\t\t\tboxes[x][RIGHT] = max(boxes[x][RIGHT], j)\n\t\tgraph = {color: set() for color in boxes}\n\t\tfor (color, (i1, j1, i2, j2)) in boxes.items():\n\t\t\tfor i in range(i1, i2 + 1):\n\t\t\t\tfor j in range(j1, j2 + 1):\n\t\t\t\t\tif target[i][j] != color:\n\t\t\t\t\t\tgraph[color].add(target[i][j])\n\t\t(WHITE, GRAY, BLACK) = (0, 1, 2)\n\t\tcolor = defaultdict(int)\n\n\t\tdef dfs(u):\n\t\t\tcolor[u] = GRAY\n\t\t\tfor v in graph[u]:\n\t\t\t\tif color[v] == GRAY:\n\t\t\t\t\treturn False\n\t\t\t\telif color[v] == WHITE and (not dfs(v)):\n\t\t\t\t\treturn False\n\t\t\tcolor[u] = BLACK\n\t\t\treturn True\n\t\treturn all((color[u] == BLACK or dfs(u) for u in graph))\n", "class Component:\n\n\tdef __init__(self, color):\n\t\tself.cells = set()\n\t\tself.color = color\n\t\tself.min_row = float('inf')\n\t\tself.max_row = float('-inf')\n\t\tself.min_col = float('inf')\n\t\tself.max_col = float('-inf')\n\n\tdef add_cell(self, u):\n\t\tself.cells.add(u)\n\t\tself.min_row = min(self.min_row, u[0])\n\t\tself.max_row = max(self.max_row, u[0])\n\t\tself.min_col = min(self.min_col, u[1])\n\t\tself.max_col = max(self.max_col, u[1])\n\n\tdef remove_cell(self, u):\n\t\tself.cells.remove(u)\n\nclass Solution:\n\n\tdef isPrintable(self, targetGrid: List[List[int]]) -> bool:\n\t\tgrid = targetGrid\n\n\t\tdef discover_components():\n\t\t\tcomponents = {}\n\t\t\tfor i in range(len(grid)):\n\t\t\t\tfor j in range(len(grid[i])):\n\t\t\t\t\tcolor = grid[i][j]\n\t\t\t\t\tif color not in components:\n\t\t\t\t\t\tcomponents[color] = Component(color)\n\t\t\t\t\tcomponents[color].add_cell((i, j))\n\t\t\treturn components\n\n\t\tdef is_rectangular(c):\n\t\t\tfor i in range(c.min_row, c.max_row + 1):\n\t\t\t\tfor j in range(c.min_col, c.max_col + 1):\n\t\t\t\t\tif grid[i][j] != c.color:\n\t\t\t\t\t\treturn False\n\t\t\treturn True\n\n\t\tdef replace_holes(cx, marked_for_removal):\n\t\t\tfor i in range(cx.min_row, cx.max_row + 1):\n\t\t\t\thole_colors = set()\n\t\t\t\tfor j in range(cx.min_col, cx.max_col + 1):\n\t\t\t\t\tif grid[i][j] == cx.color:\n\t\t\t\t\t\tcontinue\n\t\t\t\t\tif grid[i][j] not in marked_for_removal:\n\t\t\t\t\t\treturn\n\t\t\tfor i in range(cx.min_row, cx.max_row + 1):\n\t\t\t\tfor j in range(cx.min_col, cx.max_col + 1):\n\t\t\t\t\tif grid[i][j] != cx.color:\n\t\t\t\t\t\tcx.add_cell((i, j))\n\t\t\t\t\t\thc = grid[i][j]\n\t\t\t\t\t\tmarked_for_removal[hc].remove_cell((i, j))\n\t\t\t\t\t\tif len(marked_for_removal[hc].cells) == 0:\n\t\t\t\t\t\t\tdel marked_for_removal[hc]\n\t\t\t\t\t\tgrid[i][j] = cx.color\n\t\tcomponents = discover_components()\n\t\tmarked_for_removal = {}\n\t\twhile len(components) > 0:\n\t\t\tfound_new_comp_to_remove = False\n\t\t\tfor c in components:\n\t\t\t\tif is_rectangular(components[c]):\n\t\t\t\t\tmarked_for_removal[c] = components[c]\n\t\t\t\t\tdel components[c]\n\t\t\t\t\tfound_new_comp_to_remove = True\n\t\t\t\t\tbreak\n\t\t\tif not found_new_comp_to_remove:\n\t\t\t\treturn False\n\t\t\tfor c in list(components.keys()):\n\t\t\t\treplace_holes(components[c], marked_for_removal)\n\t\treturn True\n"]

starter_code:
class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:

difficulty: MEDIUM

raw_tags: ['Array', 'Graph', 'Topological Sort', 'Matrix']

source: leetcode

tags: ['Matrices', 'Graph algorithms', 'Data structures', 'Directed graphs']

skill_types: ['Data structures']

raw_problem:
There is a strange printer with the following two special requirements:

On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.

Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Constraints:

m == targetGrid.length

n == targetGrid[i].length

1 <= m, n <= 60

1 <= targetGrid[row][col] <= 60

question:
There is a strange printer with the following two special requirements:

- On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
- Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.
Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:
![image](1.png)

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:
![image](2.png)

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Constraints:

- m == targetGrid.length
- n == targetGrid[i].length
- 1 <= m, n <= 60
- 1 <= targetGrid[row][col] <= 60

image_tags: Patterns Patterns

data_split: test