• Post Reply Bookmark Topic Watch Topic
  • New Topic

can anyone explain me the problem  RSS feed

 
praveen kumaar
Ranch Hand
Posts: 461
22
Android Chrome Eclipse IDE Google App Engine Java Notepad Oracle Ubuntu Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You work for a large company, and your job is to design sorting devices. Devices are built from:

n inputs,
n outputs,
gates which have two inputs and send to output the minimum ("min gates") or maximum ("max gates") of the two numbers given at their input,
connecting wires.
You are competing in a bid for a Bytelandian Ministry of Information contract to design the smallest possible device (in terms of the number of gates) which sorts any input. Each device will go through a rigorous test process on a number of data sets. However, through some Good Friends in High Places you have managed to acquire some additional information concerning the exact data sets (permutations) your device will be tested on. Make use of this, and of course your superior programming skills, to win the bid!

Input

First, two numbers, 2≤n≤20, 1≤k≤1000, the number of inputs and the number of different permutations for which your device will be tested. The next k lines contain permutations of the numbers 1 .. n.

Output

First, output p, the number of gates in your device (0≤p≤106). The next p lines should contain definitions of the gates used, in the form of a pair of integers, xi,yi, and exactly one of the strings "min" or "max". To be able to use the output of a gate as the input of a subsequent gate, we use the following convention. First of all, the range for inputs xi and yi is as follows: 1 ≤ xi,yi < n+p. The output of the i-th gate is assumed to be input n+i.

Finally, a sequence of exactly n integers in the range 1..n+p should follow, describing which of the "inputs" should be hard-wired to successive outputs of the device.

Scoring

If your program does not produce a sorting machine which works for every input (sorting it in ascending order), it will be deemed incorrect. Otherwise, you will score p penalty points for each test case solved.

Example

Input:
3 2
1 2 3
1 3 2

Output:
2
2 3 min
2 3 max
1 4 5

Score:
0.5
 
Knute Snortum
Sheriff
Posts: 4091
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you have a specific question?
 
praveen kumaar
Ranch Hand
Posts: 461
22
Android Chrome Eclipse IDE Google App Engine Java Notepad Oracle Ubuntu Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:Do you have a specific question?

no,actually i dont understand the problem what it means?
 
Paul Clapham
Sheriff
Posts: 22527
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's not a very helpful question. If we were to take it literally we would have to deconstruct the entire question and explain it in horrible detail. For example the word "you" at the beginning of the question: we would have to explain the context behind the word and what it actually applies to in real life. And so on.

But I suspect you already know what "you" means in that context and what it refers to. So saying that you don't understand the question is inaccurate, for obviously you do understand some parts of it. So your job here is to identify parts of the question which you don't understand and point to those parts.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!