Task DescriptionDiscussion (0)

The first line of the standard input contains character

To the first line of the standard ouput you should print

Explanation:

All possible paths, sorted lexicographically, are: 000, 001, 010, 011, 100, 101, 110 and 111.

Paths 001 (A -> C -> A -> B), 010 (A -> C -> D -> B), 100 (A -> B -> D -> B) and 111 (A -> B -> A -> B) are those that finish at B. Second one is 010.

Explanation:

It is not possible to get in D in only one move.

Task :: z-01paths

Little Z is positioned in one of four a bit strange set of rooms with a teleport machine in each of them. Rooms are named A, B, C and D. In each room there are two buttons, which we will label as 0 and 1. Pressing 0 in the room A teleports you to the room C and vice versa; pressing 0 in the room B teleports you to the room D and vice versa. Pressing 1 in the room A teleports you to the room B and vice versa; pressing 1 in the room C teleports you to the room D and vice versa. These teleports are also shown on the image below.

Pressing exactly

Little Z will always start at room A.

Pressing exactly

**n**times button 0 or button 1 we will call*. It is obvious that after each***n**-length 01-path*Little Z will end in some room. Little Z would like to finish at some of the four given rooms by pressing buttons 0 and buttons 1. He is interested in***n**-length 01-path**K**-th lexicographically smallest*such that he ends up in the room***n**-length 01-path**R**.Little Z will always start at room A.

**INPUT:**

The first line of the standard input contains character

**R**, one of the upper-case letters A, B, C or D, and two space-separated integers

**n**(1 <=

**n**<= 50) and

**K**(1 <=

**K**<= 10<sup>9</sup>).

**OUTPUT:**

To the first line of the standard ouput you should print

**K**-th lexicographically smallest

*if such exists, else print "impossible" (without quotes).*

**n**-length 01-pathInput:

Output:

**B 3 2**

Output:

**010**

Explanation:

All possible paths, sorted lexicographically, are: 000, 001, 010, 011, 100, 101, 110 and 111.

Paths 001 (A -> C -> A -> B), 010 (A -> C -> D -> B), 100 (A -> B -> D -> B) and 111 (A -> B -> A -> B) are those that finish at B. Second one is 010.

Input:

Output:

**D 1 1**

Output:

**impossible**

Explanation:

It is not possible to get in D in only one move.

Submit Solution

Available Languages

Task info

Name: | z-01paths |

Time: | 0.05 sec. |

Memory: | 4 MB |

#Tests: | 25 |

AddedBy: | boba5551 |

Source: | Slobodan MitroviÄ‡ |

Task Ratings

Difficulty: | 3 (18 votes) |

Quality: | 3.6 (16 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

nemanja1990 | 0.002 s. |

veljkovranic | 0.003 s. |

eordano | 0.004 s. |

halil | 0.005 s. |

annesa11 | 0.005 s. |

picsel | 0.006 s. |

fushar | 0.006 s. |

MarioYC | 0.006 s. |

oduleodule | 0.006 s. |

ayakut | 0.006 s. |

Solved By