ICODER - Instruction Decoder

Mathews uses a brand new 16-bit instruction processor. (Yeah i am being sarcastic!). It has one register (say R) and it supports two instructions:

  • ADD X; Impact: R = (R + X) mod 65536
  • MUL X; Impact: R = (R * X) mod 65536
  • [For both instructions 0 <= X <= 65535]
Mathews sees a segment of code, but does not know what value the register had before the code was being executed. How many possible values can the register have after the segment completed execution?


Input Format:
The input file consists of multiple testcases.
The first line of each testcase contains one integer, N. (1 <= N <= 100,000).
The following N lines contain one instructions each.
Input terminates with a line containing N=0, which must not be processed.

Output Format:
For each testcase print one integer in a single line, denoting the number of different values the register can take after code execution.

Sample Input:
1
ADD 3
1
MUL 0
5
MUL 3
ADD 4
MUL 5
ADD 3
MUL 2
8
ADD 32
MUL 5312
ADD 7
MUL 7
ADD 32
MUL 5312
ADD 7
MUL 7
0
Sample Output:
65536
1
32768
16

Added by:Prasanna
Date:2007-10-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:NITT ACM ICPC Local Contest 2007 [Self]

hide comments
2022-06-13 19:47:31 David
For the final program, the 16 possible values are [1393, 5489, 9585, 13681, 17777, 21873, 25969, 30065, 34161, 38257, 42353, 46449, 50545, 54641, 58737, 62833].
2016-03-18 11:46:59 minhthai
can someone explain the result "16". I thought the equation in that test is not solvable ???
2014-04-20 05:00:37 Kishlay Raj


Last edit: 2014-04-22 16:45:24
2013-03-09 13:42:40 napster
can u tell me how the 3rd test case getting 32768??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.