Daily Programming Dose Day 7

Hello Folks,

Sorry for the very very long interruption between the daily dose.I will be regular from now.

The following is the day 7 question.

You are given a list of  numbers and you will have a continuous flow of numbers coming in the list.

For every new number you need to tell that whether that number could be made using the numbers previously available in the list.

INPUT

The first line contains number m (1 ≤ m ≤ 2000), showing how many numbers are there goo be in the list.

The next m lines contain the numbers in the order in which the numbers are being put in the list. Each number is a positive integer strictly less than 10600 that doesn’t contain leading zeroes.

Output

For each number either print a 0 on the corresponding line, if the number cannot be represented as a XOR sum of numbers that are in the list, or print integer k showing how many numbers are in the representation and the indexes of these numbers. Separate the numbers by spaces. Each number can occur in the representation at most once.

Assume that the list was initially empty.

Sample test(s)
Input
7
7
6
5
4
3
2
1
Output
0
0
0
3 0 1 2
2 1 2
2 0 2
2 0 1
Input
2
5
5
Output
0
1 0

Comment any ideas or your way of approach to the question.

Advertisements

Daily Programming Dose Day 5

How many specific orders do you know? Ascending order, descending order, order of ascending length, order of ascending polar angle… Let’s have a look at another specific order: d-sorting. This sorting is applied to the strings of length at least d, where d is some positive integer. The characters of the string are sorted in following manner: first come all the 0-th characters of the initial string, then the 1-st ones, then the 2-nd ones and so on, in the end go all the (d - 1)-th characters of the initial string. By the i-th characters we mean all the character whose positions are exactly i modulo d. If two characters stand on the positions with the same remainder of integer division by d, their relative order after the sorting shouldn’t be changed. The string is zero-indexed. For example, for string ‘qwerty‘:

Its 1-sorting is the string ‘qwerty‘ (all characters stand on 0 positions),

Its 2-sorting is the string ‘qetwry‘ (characters ‘q‘, ‘e‘ and ‘t‘ stand on 0 positions and characters ‘w‘, ‘r‘ and ‘y‘ are on 1 positions),

Its 3-sorting is the string ‘qrwtey‘ (characters ‘q‘ and ‘r‘ stand on 0 positions, characters ‘w‘ and ‘t‘ stand on 1 positions and characters ‘e‘ and ‘y‘ stand on 2 positions),

Its 4-sorting is the string ‘qtwyer‘,

Its 5-sorting is the string ‘qywert‘.

You are given string S of length n and m shuffling operations of this string. Each shuffling operation accepts two integer arguments k and dand transforms string S as follows. For each i from 0 to n - k in the increasing order we apply the operation of d-sorting to the substringS[i..i + k - 1]. Here S[a..b] represents a substring that consists of characters on positions from a to b inclusive.

After each shuffling operation you need to print string S.

Input

The first line of the input contains a non-empty string S of length n, consisting of lowercase and uppercase English letters and digits from 0 to 9.

The second line of the input contains integer m – the number of shuffling operations (1 ≤ m·n ≤ 106).

Following m lines contain the descriptions of the operations consisting of two integers k and d (1 ≤ d ≤ k ≤ n).

Output

After each operation print the current state of string S.

Sample test(s)
input
qwerty
3
4 2
6 3
5 2
output
qertwy
qtewry
qetyrw
Note

Here is detailed explanation of the sample. The first modification is executed with arguments k = 4, d = 2. That means that you need to apply 2-sorting for each substring of length 4 one by one moving from the left to the right. The string will transform in the following manner:

qwerty  →  qewrty  →  qerwty  →  qertwy

Thus, string S equals ‘qertwy‘ at the end of first query.

The second modification is executed with arguments k = 6, d = 3. As a result of this operation the whole string S is replaced by its 3-sorting:

qertwy  →  qtewry

The third modification is executed with arguments k = 5, d = 2.

qtewry  →  qertwy  →  qetyrw

Daily Programming Dose Day 4 Solutions

Due to the small restrictions, the problem could be solved with the straightforward O(n*m*(n+m)) algo of finding for each symbol whether there is other such symbol in the corresponding row or column. More fast approach is to count for each symbol how many times it appears in any row/column, and do corresponding checks in O(1) instead.

I am attaching my solution link below :

http://ideone.com/G3YKqo

Daily Programming Dose Day 4

Given a n*m grid of characters you have to perform following operations:

1.Cross out the common letters in a particular row.

2.Cross out the common letters in a particular column.

Now make a string according to the following rule:

1.The letters that occupy a higher position follow before the letters that occupy a lower position.

2.If the letters are located in one row, then the letter to the left goes first.

The resulting string is the answer.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100). Next n lines contain m lowercase  letters each.

Output

Print the encrypted word on a single line. It is guaranteed that the answer consists of at least one letter.

Sample test(s)
input
3 3
cba
bcd
cbc
output
abcd
input
5 5
fcofd
ooedo
afaoa
rdcdf
eofsf
output
codeforces

Daily Programming Dose Day 3 Solutions

You will surely appreciate the simplicity of the problem once you get the solution.

Let’s draw a straight line between the two centers.

8JmxYQ0

Clearly to move the center with maximum distance we need to rotate it around the intersection of the line and the circle with 180 degrees. So the maximum distance we can move the center each time is 2 * R. Let’s continue moving the center with 2 * R distance each time until the two circles intersects. Now obviously we can make the center moves into its final position by rotating it around one of the intersection points of the two circles until it reaches the final destination.

Every time we make the circle moves 2 * R times except the last move it’ll be  ≤ 2 * R. Assume that the initial distance between the two points is d So the solution to the problem will be

You can have  a look at my code below:

http://ideone.com/j4MFfL

Daily Programming Dose day 3

You have a circle of radius r and center in point (x, y). You want the circle center to be in new position (x‘, y‘).

In one step you can put a pin to the border of the circle in a certain point, then rotate the circle around that pin by any angle and finally remove the pin.

What are the minimum number of steps in which the goal could be achieved?

Input

Input consists of 5 space-separated integers r, x, y, x y (1 ≤ r ≤ 105,  - 105 ≤ x, y, x‘, y‘ ≤ 105), circle radius, coordinates of original center of the circle and coordinates of destination center of the circle respectively.

Output

Output a single integer — minimum number of steps required to move the center of the circle to the destination point.

Sample test(s)
input
2 0 0 0 4
output
1
input
1 1 1 4 4
output
3
input
4 5 6 5 6
output
0
Note

In the first sample test the optimal way is to put a pin at point (0, 2) and rotate the circle by 180 degrees counter-clockwise (or clockwise, no matter).

2531a11297bd51456534008e7aef3800a936f20d

Daily Programming Dose Day 2 Solutions

In order to calculate the minimum possible lifted weight, we should find the initial stack first. Let’s find the positions one by one.

  • First, let’s decide the position of book b1. After day 1, book b1 will be on the top of the stack, regardless of the order of the initial stack. Therefore, in order to minimize the lifted weight during day 1, book b1 must be on the top of the initial stack. (so actually, in day 1, you won’t lift any book)
  • Next, let’s decide the position of book b2. (assume that b1 ≠ b2 for simplicity) Currently, b1 is on the top of the stack, and it cannot be changed because of the procedure. Therefore, in order to minimize the lifted weight during day 2, book b2 must be immediately below book b1.

Considering this, we can find the optimal strategy to create the initial stack: Scan b1, b2, …, bm step by step. Let’s assume that I am handling bi now. If bi has appeared before (formally, if ), erase bi from the sequence. Otherwise, leave bi. The resulting sequence will be the optimal stack.

You should note that it is not necessary for you to read all the books during 2015, which means the size of the resulting sequence may be smaller than n. The books which doesn’t appear in the resulting sequence must be in the bottom of the initial stack (obviously). However, this problem doesn’t require us to print the initial stack, so it turned out not to be important.

In conclusion, finding the initial stack takes O(n + m) time.

After finding the initial stack, we can simulate the procedure given in the statement naively. It will take O(nm) time.

  • Time: O(nm)
  • Memory: O(n + m)

You could also check out my solution at :

http://ideone.com/Ji4WHx