{"id":3258,"date":"2012-04-12T04:12:44","date_gmt":"2012-04-12T04:12:44","guid":{"rendered":"http:\/\/wp.binus.ac.id\/?p=3258"},"modified":"2012-04-12T04:12:44","modified_gmt":"2012-04-12T04:12:44","slug":"contoh-soal5128-to-add-or-to-multiply","status":"publish","type":"post","link":"https:\/\/simprug.binus.sch.id\/id\/2012\/04\/12\/contoh-soal5128-to-add-or-to-multiply\/","title":{"rendered":"[contoh soal]5128 – To Add or to Multiply"},"content":{"rendered":"

\t\t\t\tThe Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer needs. Processors of the\u00a0a<\/em>-C-m<\/em>\u00a0family (such as the 1-C-2 and the 5-C-3) have an instruction set with only two different operations:
\nA<\/tt>\u00a0add\u00a0a<\/em><\/p>\n

M<\/tt>\u00a0multiply by\u00a0m<\/em>
\nThe processor receives an integer, executes a sequence of\u00a0A<\/tt>\u00a0and\u00a0M<\/tt>\u00a0operations (the program) that modifies the input, and outputs the result. For example, the 1-C-2 processor executing the program\u00a0AAAM<\/tt>\u00a0with the input 2 yields the output 10 (the computation is\u00a02\u00a0\"$\u00a03\u00a0\"$\u00a04\u00a0\"$\u00a05\u00a0\"$\u00a010), while the 5-C-3 processor yields 51 with the same program and input (\u00a02\u00a0\"$\u00a07\u00a0\"$\u00a012\u00a0\"$\u00a017\u00a0\"$\u00a051).<\/p>\n

You are an\u00a0a<\/em>-C-m<\/em>\u00a0programmer assigned to a top secret project. This means that you have not been told the precise computation your program should perform. But you are given particular values\u00a0p<\/em>,\u00a0q<\/em>,\u00a0r<\/em>, and\u00a0s<\/em>\u00a0and the following conditions:<\/p>\n

 <\/p>\n

    \n
  1. The input is guaranteed to be a number between\u00a0p<\/em>\u00a0and\u00a0q<\/em>.<\/li>\n
  2. The output must be some number between\u00a0r<\/em>\u00a0and\u00a0s<\/em>.<\/li>\n<\/ol>\n

    Given an\u00a0a<\/em>-C-m<\/em>\u00a0processor and the numbers\u00a0p<\/em>,\u00a0q<\/em>,\u00a0r<\/em>, and\u00a0s<\/em>, your job is to construct the shortest\u00a0a<\/em>-C-m<\/em>\u00a0program which, for every input\u00a0x<\/em>\u00a0such that\u00a0p<\/em>\"$x<\/em>\"$q<\/em>, yields some outputy<\/em>\u00a0such that\u00a0r<\/em>\"$y<\/em>\"$s<\/em>. If there is more than one program of minimum length, choose the one that come first lexicographically, treating each program as a string of\u00a0A<\/tt>s and\u00a0M<\/tt>s.<\/p>\n

     <\/p>\n

    <\/a>Input\u00a0<\/span><\/h2>\n

    The input contains several test cases. Each test case is given by a line with the six integersa<\/em>,\u00a0m<\/em>,\u00a0p<\/em>,\u00a0q<\/em>,\u00a0r<\/em>, and\u00a0s<\/em>\u00a0as described above (\u00a01\"$a<\/em>,\u00a0m<\/em>,\u00a0p<\/em>,\u00a0q<\/em>,\u00a0r<\/em>,\u00a0s<\/em>\"$109<\/sup>\u00a0,\u00a0p<\/em>\"$q<\/em>\u00a0and\u00a0r<\/em>\"$s<\/em>).<\/p>\n

    The last test case is followed by a line with six zeros.<\/p>\n

     <\/p>\n

    <\/a>Output\u00a0<\/span><\/h2>\n

    For each test case, display its case number followed by the best program as described above. Display the word “empty<\/tt>” if the best program uses no operations. Display the word “impossible<\/tt>” if there is no program meeting the specifications.<\/p>\n

    Display the program as a sequence of space-separated strings, alternating between strings of the form “n<\/em>A<\/tt>” and strings of the form “n<\/em>M<\/tt>“, where\u00a0n<\/em>\u00a0> 0. Strings of the former type indicate\u00a0n<\/em>\u00a0consecutive A operations, and strings of the latter type indicate\u00a0n<\/em>consecutive\u00a0M<\/em>\u00a0operations.<\/p>\n

    Follow the format of the sample output.<\/p>\n

     <\/p>\n

    <\/a>Sample Input\u00a0<\/span><\/h2>\n

     <\/p>\n

    1 2 2 3 10 20\n1 3 2 3 22 33\n3 2 2 3 4 5\n5 3 2 3 2 3\n0 0 0 0 0 0<\/pre>\n
     <\/p>\n
    <\/a>Sample Output\u00a0<\/span><\/h2>\n
     <\/p>\n
    Case 1: 1A 2M\nCase 2: 1M 2A 1M\nCase 3: impossible\nCase 4: empty<\/pre>\n","protected":false},"excerpt":{"rendered":"
    The Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer needs. Processors of the\u00a0a-C-m\u00a0family (such as the 1-C-2 and the 5-C-3) have an instruction set with only two different operations: A\u00a0add\u00a0a M\u00a0multiply by\u00a0m The processor receives an integer, executes a sequence of\u00a0A\u00a0and\u00a0M\u00a0operations (the program) that modifies the input, and outputs […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-3258","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/posts\/3258","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/comments?post=3258"}],"version-history":[{"count":0,"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/posts\/3258\/revisions"}],"wp:attachment":[{"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/media?parent=3258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/categories?post=3258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/simprug.binus.sch.id\/id\/wp-json\/wp\/v2\/tags?post=3258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}