DISTX - Distance
In this task let's consider distance between two positive integers defined as below.
Single operation is : multiplying some number by prime number or dividing some number by prime number ( we can divide only when remainder is equal to 0 )
Distance d between two numbers a, b is minimum number operations to convert one number to another.
For example d(69,42)=3
This distance is very similar to well-known term "distance" in real human life:
d(a,a) = 0 , distance number to itself is 0
d(a,b) = d(b,a) distance from a->b is equal to b->a
d(a,b)+d(b,c) >= d(a,c) triangle equation is true too
With given n number you have to determine for each i-th of those numbers closest number aj from set that i != j and if there is many numbers with equal, smallest distance, you have to pick number with smallest index
Input
In first line - number n <=10^5.
In next n lines - i-th number. Every number is not greater than 10^6
Output
You have to output n lines.
I-th line should contain index of closest number ( if there is many answers, please output smallest index )
Example
Input: 6
1
2
3
4
5
6
Output: 2
1
1
2
1
2
hide comments
Krzysztof Lewko:
2011-11-23 12:40:32
yup, you are right. |
|
Thomas Dybdahl Ahle:
2011-11-23 12:40:22
The triangle inequality in the description should be using a >= rather than a >. |
|
Krzysztof Lewko:
2011-11-23 12:40:22
Sorry, was translating it in night, now it's corrected. |
|
[Rampage] Blue.Mary:
2011-11-23 12:40:22
The range of N & the numbers?
|
Added by: | Krzysztof Lewko |
Date: | 2011-11-15 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | 19th POI 1st stage |