ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2008 > задача:


D. Bit Decoder

Задачи сборника

• A. Math and Soldiers
• B. Roads
• C. Brackets
• D. Bit Decoder
• E. Points
• F. Division
• G. String Multiplication
• H. Lawyers Council

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/6000/6000/6000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Дмитрий Шевченко, ВлГУ.

Currently you are working for a famous computer company "Rivest C". The main computer has a very complicated password to login. It is kept in the CEO's safe. The password is very long and very strong from the mathematical point of view. Unfortunately, the safe was not that strong, and someone has stolen the password. Now you have to change it, but in order to do so you have to enter the old password, and your CEO does not remember it.

However, there is a way out. You can restore a password from key that was used to generate it. The key consists of the following parts:

It has N positive integer numbers A1, A2,.. AN, which make the source row.
It has N pairs of positive integer numbers (B1, C1), (B2, C2),.. (BN, CN), which make the transformation puzzle.
It has one positive integer number K which is the time security key.

Now let's show, how this key is used to generate code. From the original source row A we generate a new source row A' according to the following system:

1. Aj is called correlated to Ai if |j-Bi| mod Ci = 0.
2. A'i is calculated as the sum of all elements in original source row that are correlated to Ai.

For example, suppose that N=5 and for A4 we have pair (3,2). In that case elements A1, A3, A5 are correlated to A4 and the new source row element A'4 is calculated as sum (A1 + A3 + A5).

The code is generated like this. You calculate the new source row A' and replace the old source row A with this one. You perform this K times. After you are done with that, you write down the code from final source row in the following way: the code is concatenation of S1, S2,.. SN where Si are the first twenty five bits in binary representation of Ai, starting from the least significant bit. For example, suppose, that after K iterations you have the following source row: {31,15,63}.
Then the code is this:
111110000000000000000000011110000000000000000000001111110000000000000000000.

Help your CEO and write a program that will generate the code from the given key.

Input
In the first input row, numbers N and K are written separated by a space (1 ≤ N ≤ 100, 1 ≤ K ≤ 109).
The next N rows contain three numbers each: (i+1)-th row contains numbers Ai, Bi, Ci (1 ≤ Ai ≤ 230, 1 ≤ BiN, 1 ≤ CiN).
Output
Your output should contain a string representing the code. The string should be 25*N characters long and should contain only symbols '0' and '1'.

Input Output
3 25
31 1 3
15 2 3
63 3 3
111110000000000000000000011110000000000000000000001111110000000000000000000
Input Output
3 25
31 2 1
15 3 1
63 1 2
101100010010101111010001110110001001010111101000110111101111100111000100101

Для отправки решений необходимо выполнить вход.

www.contester.ru