{"id":1411,"date":"2013-03-18T11:15:23","date_gmt":"2013-03-18T03:15:23","guid":{"rendered":"https:\/\/blog.rexdf.org\/?p=1411"},"modified":"2013-03-18T11:15:23","modified_gmt":"2013-03-18T03:15:23","slug":"codeforces-round-173-div-2-yet-another-number-game","status":"publish","type":"post","link":"https:\/\/blog.rexdf.org\/en\/2013\/03\/codeforces-round-173-div-2-yet-another-number-game\/","title":{"rendered":"Codeforces Round #173 (Div. 2) Yet Another Number Game"},"content":{"rendered":"<p>&nbsp;<\/p>\n<div>\n<div>D. Yet Another Number Game<\/div>\n<div>\n<div>time limit per test<\/div>\n<p>2 seconds<\/p><\/div>\n<div>\n<div>memory limit per test<\/div>\n<p>256 megabytes<\/p><\/div>\n<div>\n<div>input<\/div>\n<p>standard input<\/p><\/div>\n<div>\n<div>output<\/div>\n<p>standard output<\/p><\/div>\n<\/div>\n<div>\n<p>Since most contestants do not read this part, I have to repeat that Bitlandians are quite weird. They have their own jobs, their own working method, their own lives, their own sausages and their own games!<\/p>\n<p>Since you are so curious about Bitland, I&#8217;ll give you the chance of peeking at one of these games.<\/p>\n<p>BitLGM and BitAryo are playing yet another of their crazy-looking genius-needed Bitlandish games. They&#8217;ve got a sequence of\u00a0<i>n<\/i>\u00a0non-negative integers\u00a0<i>a<\/i><sub>1<\/sub>,\u2009<i>a<\/i><sub>2<\/sub>,\u2009&#8230;,\u2009<i>a<\/i><sub><i>n<\/i><\/sub>. The players make moves in turns. BitLGM moves first. Each player can and must do one of the two following actions in his turn:<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>Take one of the integers (we&#8217;ll denote it as\u00a0<i>a<\/i><sub><i>i<\/i><\/sub>). Choose integer\u00a0<i>x<\/i>\u00a0(1\u2009\u2264\u2009<i>x<\/i>\u2009\u2264\u2009<i>a<\/i><sub><i>i<\/i><\/sub>). And then decrease\u00a0<i>a<\/i><sub><i>i<\/i><\/sub>\u00a0by\u00a0<i>x<\/i>, that is, apply assignment:<i>a<\/i><sub><i>i<\/i><\/sub>\u2009=\u2009<i>a<\/i><sub><i>i<\/i><\/sub>\u2009-\u2009<i>x<\/i>.<\/li>\n<li>Choose integer\u00a0<i>x<\/i>\u00a0<img decoding=\"async\" class=\"ls_lazyimg\" alt=\"\" src=\"https:\/\/static.rexdf.org\/plugins\/images-lazyload-and-slideshow\/blank_250x250.gif\" file=\"http:\/\/codeforces.ru\/renderer\/9bcd77b1a4d70adef53560c92a78c087c5d0039f.png\" align=\"middle\" \/><noscript><img decoding=\"async\" alt=\"\" src=\"http:\/\/codeforces.ru\/renderer\/9bcd77b1a4d70adef53560c92a78c087c5d0039f.png\" align=\"middle\" \/><\/noscript>. And then decrease all\u00a0<i>a<\/i><sub><i>i<\/i><\/sub>\u00a0by\u00a0<i>x<\/i>, that is, apply assignment:\u00a0<i>a<\/i><sub><i>i<\/i><\/sub>\u2009=\u2009<i>a<\/i><sub><i>i<\/i><\/sub>\u2009-\u2009<i>x<\/i>, for all\u00a0<i>i<\/i>.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>The player who cannot make a move loses.<\/p>\n<p>You&#8217;re given the initial sequence\u00a0<i>a<\/i><sub>1<\/sub>,\u2009<i>a<\/i><sub>2<\/sub>,\u2009&#8230;,\u2009<i>a<\/i><sub><i>n<\/i><\/sub>. Determine who wins, if both players plays optimally well and if BitLGM and BitAryo start playing the described game in this sequence.<\/p>\n<\/div>\n<div>\n<div>Input<\/div>\n<p>The first line contains an integer\u00a0<i>n<\/i>\u00a0(1\u2009\u2264\u2009<i>n<\/i>\u2009\u2264\u20093).<\/p>\n<p>The next line contains\u00a0<i>n<\/i>\u00a0integers\u00a0<i>a<\/i><sub>1<\/sub>,\u2009<i>a<\/i><sub>2<\/sub>,\u2009&#8230;,\u2009<i>a<\/i><sub><i>n<\/i><\/sub>\u00a0(0\u2009\u2264\u2009<i>a<\/i><sub><i>i<\/i><\/sub>\u2009&lt;\u2009300).<\/p>\n<\/div>\n<div>\n<div>Output<\/div>\n<p>Write the name of the winner (provided that both players play optimally well). Either &#8220;BitLGM&#8221; or &#8220;BitAryo&#8221; (without the quotes).<\/p>\n<\/div>\n<div>\n<div>Sample test(s)<\/div>\n<div>\n<div>\n<div>input<\/div>\n<pre>2 1 1<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>BitLGM<\/pre>\n<\/div>\n<div>\n<div>input<\/div>\n<pre>2 1 2<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>BitAryo<\/pre>\n<\/div>\n<div>\n<div>input<\/div>\n<pre>3 1 2 1<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>BitLGM<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<pre class=\"brush: cpp; gutter: true\">\r\n#include &lt;iostream&gt;\r\n#include &lt;cstdio&gt;\r\n#include &lt;cstdlib&gt;\r\n#include &lt;cstring&gt;\r\n\r\nusing namespace std;\r\n\r\nint tab2[305][305];\r\nint tab3[305][305][305];\r\n\r\nint check2(int x,int y)\r\n{\r\n\tif(0==x &amp;&amp; 0==y)return 1;\r\n\tint Min=x&lt;y?x:y;\r\n\tfor(int i=Min;i&gt;=0;i--)\r\n\t  if(1==tab2[x-i][y-i])return 0;\r\n\tfor(int i=0;i&lt;=y;i++)\r\n\t  if(1==tab2[x][i])return 0;\r\n\tfor(int i=0;i&lt;=x;i++)\r\n\t  if(1==tab2[i][y])return 0;\r\n\treturn 1;\r\n}\r\n\r\nvoid mark2(int x,int y)\r\n{\r\n\tfor(int i=0;;i++)\r\n\t{\r\n\t\tif(x+i&gt;303 || y+i&gt;303)break;\r\n\t\ttab2[x+i][y+i]=0;\r\n\t}\r\n\tfor(int i=0;i&lt;303;i++)\r\n\t{\r\n\t\ttab2[x][i]=0;\r\n\t\ttab2[i][y]=0;\r\n\t}\r\n\ttab2[x][y]=1;\r\n}\r\n\r\nvoid inital2()\r\n{\r\n\tmemset(tab2,-1,sizeof(tab2));\r\n\t\/\/tab2[0][0]=1;\r\n\tfor(int i=0;i&lt;303;i++)\r\n\t  for(int j=0;j&lt;303;j++)\r\n\t  {\r\n\t  \tif(tab2[i][j]!=-1)continue;\r\n\t  \tif(check2(i,j))\r\n\t  \t{\r\n\t  \t\tmark2(i,j);\r\n\t  \t\tmark2(j,i);\r\n\t  \t}\r\n\t  }\r\n\t\/*\r\n\tfor(int i=0;i&lt;10;i++)\r\n\t{\r\n\t  for(int j=0;j&lt;10;j++)\r\n\t    cout&lt;&lt;tab2[i][j]&lt;&lt;&quot; &quot;;\r\n\t  cout&lt;&lt;endl;\r\n\t}\r\n\t*\/\r\n}\r\n\r\nint check3(int x,int y,int z)\r\n{\r\n\tif(0==x &amp;&amp; 0==y &amp;&amp; 0==z)return 1;\r\n\tint Min=x&lt;y?x:y;\r\n\tMin=Min&lt;z?Min:z;\r\n\tfor(int i=Min;i&gt;=0;i--)\r\n\t  if(1==tab3[x-i][y-i][z-i])return 0;\r\n\tfor(int i=0;i&lt;=z;i++)\r\n\t  if(1==tab3[x][y][i])return 0;\r\n\tfor(int i=0;i&lt;=y;i++)\r\n\t  if(1==tab3[x][i][z])return 0;\r\n\tfor(int i=0;i&lt;=x;i++)\r\n\t  if(1==tab3[i][y][z])return 0;\r\n\treturn 1;\r\n}\r\n\r\nvoid mark3(int x,int y,int z)\r\n{\r\n\tfor(int i=0;;i++)\r\n\t{\r\n\t\tif(x+i&gt;303 || y+i&gt;303 || z+i&gt;303)break;\r\n\t\ttab3[x+i][y+i][z+i]=0;\r\n\t}\r\n\tfor(int i=0;i&lt;303;i++)\r\n\t{\r\n\t\ttab3[x][y][i]=0;\r\n\t\ttab3[x][i][z]=0;\r\n\t\ttab3[i][y][z]=0;\r\n\t}\r\n\ttab3[x][y][z]=1;\r\n}\r\n\r\nvoid inital3()\r\n{\r\n\tmemset(tab3,-1,sizeof(tab3));\r\n\t\/\/tab2[0][0]=1;\r\n\tfor(int i=0;i&lt;303;i++)\r\n\t  for(int j=0;j&lt;303;j++)\r\n\t    for(int k=0;k&lt;303;k++)\r\n\t\t  {\r\n\t\t  \tif(tab3[i][j][k]!=-1)continue;\r\n\t\t  \tif(check3(i,j,k))\r\n\t\t  \t{\r\n\t\t  \t\tmark3(i,j,k);\r\n\t\t  \t\tmark3(i,k,j);\r\n\t\t  \t\tmark3(k,i,j);\r\n\t\t  \t\t\r\n\t\t  \t\tmark3(j,i,k);\r\n\t\t  \t\tmark3(j,k,i);\r\n\t\t  \t\tmark3(k,j,i);\r\n\t\t  \t}\r\n\t\t  }\r\n\t\/*\r\n\tfor(int i=0;i&lt;10;i++)\r\n\t{\r\n\t    cout&lt;&lt;i&lt;&lt;endl;\r\n\t  for(int k=0;k&lt;10;k++)\r\n\t   {\r\n\t\t  for(int j=0;j&lt;10;j++)\r\n\t\t    cout&lt;&lt;tab3[i][k][j]&lt;&lt;&quot; &quot;;\r\n\t\t  cout&lt;&lt;endl;\r\n\t   }\r\n\t   cout&lt;&lt;endl;\r\n\t}\r\n\t*\/\r\n}\r\n\r\nint main()\r\n{\r\n\tint n;\r\n\tint a[5];\r\n\tcin&gt;&gt;n;\r\n\tif(1==n)\r\n\t{\r\n\t\tcin&gt;&gt;a[0];\r\n\t\tif(a[0])cout&lt;&lt;&quot;BitLGM&quot;&lt;&lt;endl;\r\n\t\telse cout&lt;&lt;&quot;BitAryo&quot;&lt;&lt;endl;\r\n\t}\r\n\telse if(2==n)\r\n\t{\r\n\t\tinital2();\r\n\t\tcin&gt;&gt;a[0]&gt;&gt;a[1];\r\n\t\t\/\/cout&lt;&lt;tab2[a[0]][a[1]]&lt;&lt;endl;\r\n\t\tif(tab2[a[0]][a[1]])cout&lt;&lt;&quot;BitAryo&quot;&lt;&lt;endl;\r\n\t\telse cout&lt;&lt;&quot;BitLGM&quot;&lt;&lt;endl;\r\n\t}\r\n\telse if(3==n)\r\n\t{\r\n\t\tinital3();\r\n\t\tcin&gt;&gt;a[0]&gt;&gt;a[1]&gt;&gt;a[2];\r\n\t\tif(tab3[a[0]][a[1]][a[2]])cout&lt;&lt;&quot;BitAryo&quot;&lt;&lt;endl;\r\n\t\telse cout&lt;&lt;&quot;BitLGM&quot;&lt;&lt;endl;\r\n\t}\r\n\treturn 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; D. Yet Another Number Game time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Since most contestants do not read this part, I have to repeat that Bitlandians are quite &hellip; <a href=\"https:\/\/blog.rexdf.org\/en\/2013\/03\/codeforces-round-173-div-2-yet-another-number-game\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3],"tags":[125],"class_list":["post-1411","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-codeforces"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/posts\/1411","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/comments?post=1411"}],"version-history":[{"count":0,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/posts\/1411\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/media?parent=1411"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/categories?post=1411"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/tags?post=1411"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}