چند سال پیش، هارون مدرسه قدیمی خود را ترک کرد و به دلایل امنیتی در مدرسه دیگری ثبت نام کرد. حالا او آرزو دارد جین، یکی از همکلاسی ها و دوستان خوبش را پیدا کند.
n مدرسه با شماره 1 تا n وجود دارد. با خرید بلیط می توان بین هر جفت مدرسه رفت و آمد کرد. بلیط بین مدارس i و j هزینه (i + j) % (modlue) (n + 1) دارد و می توان چندین بار از آن استفاده کرد. به آرون کمک کنید حداقل هزینه کل بازدید از همه مدارس را پیدا کند. او می تواند در هر مدرسه ای شروع کند و به پایان برساند.
Range : 1 ≤ n ≤ 106
A few years ago, Aaron left his old school and registered at another due to security reasons. Now he wishes to find Jane, one of his schoolmates and good friends.
There are n schools numbered from 1 to n. One can travel between each pair of schools by buying a ticket. The ticket between schools i and j costs (i + j) modulo (n + 1) and can be used multiple times. Help Aaron find the minimum total cost to visit all schools. He can start and finish at any school.
Range : 1 ≤ n ≤ 106
public class Kata {
public static int findJane(final int n) {
return (n-1)/2;
}
}
/*
1,2,3,...,n
cost = (a+b) % (n+1)
best association is:
b = n+1-a -> cost=0
1 2 3 4 5 -> 1 <-> 5
2 <-> 4
to link ("L") those two, the best remaining way is:
b = n+1-a+1 -> cost=1
1 2 3 4 5 -> 1 <-> 5: 0
L: 5 <-> 2: 1
2 <-> 4: 0
L: 4 <-> 3: 1
--------------
total cost = 2
1 2 3 4 -> 1 <-> 4: 0
L: 4 <-> 2: 1
2 <-> 3: 0
--------------
total cost = 1
And so on...
Since you consume 2 towns for each 0 cost travel, you pay 1 for each "link" travel and you have to travel between:
* n/2 pairs if n is even, meaning you make n/2 - 1 actual links
* (n-1)/2 pairs + the center town if n is odd, meaning you make (n-1)/2 - 1 + 1 = (n-1)/2 actual links
Combining those two with integer division, you get it straight with (n-1)/2
*/
