Back to Category
d238: [12.05] D - Tree Luck

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 0 Times | Submit :6 Times | Clicks : 395
Accepted : 0 Users | Submit : 1 Users | Accepted rate : 0%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
Update : 2012-10-27 20:34


Augur Communication Maple (ACM) is a special kind of plant on a small island. The plant starts as a single "root" bud with one leaf attached. In the first morning, the leaf falls down, and two branches grow from the bud. One branch would grow vertically upwards, and the other would grow horizontally in a random direction. The original bud is than inactive, but new buds are alive at the other end of the two new branches. Each new bud then grows a leaf during the day. The next morning, the leaves fall down; two branches grow from each bud, and the process continues. Each branch is one centimeter long and you can assume that the horizontal branches will not be interfering with each other.
The islanders do not like their ACM plant to grow too tall. So if any plant is of height K cm in the evening, the path (series of branches) from the root to any bud at height K would be pruned by physically removing the bud. When a bud is removed, the original leaf does not fall down and a new leaf still grows and falls every day, but no new branches would be coming from the bud.
For instance, an ACM plant of 3 days old and height at most 2 cm would grow like this:
  1. In the morning of the fi rst day, 1 leaf falls down; two branches (one at height 1 cm called A and the other at height 0 cm called B) grow; two leaves grow on the buds of those two branches.
  2. In the morning of the second day, 2 leaves fall down; two branches Ah and Av grow from A; two branches Bh and Bv grow from B; four leaves grow on those branches; the vertical branch Av from A is at height 2 and hence pruned. So there are only three active branches (Ah, Bh and Bv, with Ah and Bv at height 1).
  3. In the morning of the third day, 4 leaves fall down; two branches grow from Ah, Bh and Bv, respectively. The branches Ah-vertical and Bv-vertical are pruned.
In the morning of the fourth day, the leaves on Av, Ah-vertical, Ah-horizontal, Bh-vertical, Bh-horizontal, Bv-vertical, Bv-horizontal will fall down. So there are 7 leaves. The islanders use those leaves in the following way. He first takes the leaves to a wizard. The wizard would grasp all the leaves on his hand. He fi rst removes one leaf, and shouts "LUCKY!" Then, the wizard removes another leaf, and shouts "UNLUCKY!" The process continues until there are no leaves on his hand, and the last shout predicts the luckiness of the day. For instance, for the owner of an ACM plant with height at most 2 cm, it is his "LUCKY!" day because there are 7 leaves. 
Given D, the day of gathering the leaves (D = 4 in the example above), and K, the maximum height of the plant (K = 2 in the example above), can you rapidly determine the luckiness of the day?  

Technical Speci cations

  1. The number of test cases would be smaller than or equal to 20.
  2. The day D for gathering the leaves would satisfy 1  D  10000.
  3. The maximum height K of the plant would satisfy 1  K  10000. 


The rst line of the input le contains an integer indicating the number of test cases to follow. Each test case contains two integers D and K, separated by spaces.


For each test case, output LUCKY! in a line if it's a lucky day, and UNLUCKY! otherwise.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4 2
4 3

Sample Output :


Hint :

click here to download the problem solving hint

Author :

  Solve it!   Status Forum


Program running time may be affected by various factors. Check server system environment information here