0087. Two Instructions

Input file name:	2instr.in
Output file name:	2instr.out
Time limit:	500 ms
Memory limit:	64 megabytes

Probably, the most important instruction in 8086 is "pop sp" which takes the stack pointer value from the stack.

In addition, in 80486 processor Intel has added a second instruction, also very important for working with stack pointer register – "bswap sp". It swaps the high and the low bytes of this register.

• "bswap sp" has the instruction code 0F CC;
• "pop sp" has the instruction code 5C;
• memory segment is 65536 bytes long;
• memory is considered looped, that is after the cell FFFF goes cell 0000;
• "pop sp" takes a big-endian 16-bit word from the memory pointed by sp and loads it into sp;

You are given some initial sp value and the contents of the memory. Find the shortest possible program such that after its execution the value of stack pointer is equal to another given value.

Input file

The first line of the input file contains two hexadecimal 16-bit numbers from 0000 to FFFF – the starting and ending values of sp register. The next 4096 lines contain hex dump of the segment.

Hex dump is displayed in format [8 bytes][2 spaces][8 bytes] where [8 bytes] are ([byte][space]*7)[byte]; [byte] is a hexadecimal number from 00 to FF with exactly two digits.

Output file

In the first line output the number of code bytes in the shortest program (in decimal notation). Then you should output the hex dump of the resulting program in the same format as in input. The last (possibly incomplete) line of hexdump must be immediately terminated by the end-of-line character after the last byte output.

If there are several possible shortest programs, output the lexicographically smallest one.

If it is impossible to solve task for a given dump and values, write a single line containing the word IMPOSSIBLE.

Examples:

2instr.in	2instr.out
0003 00EF 00 00 EF 00 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 above line repeats 4094 times more	4 5C 0F CC 5C

Source: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08

Discuss       Submit a solution



Printable version