Задача
Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.
В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от $1$ до $N$, и будем исключать каждого $k$-ого до тех пор, пока не уцелеет только один человек. (Например, если $N=10$, $k=3$, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним — 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)
Входные данные
Во входном файле даны натуральные числа $N$ и $k$. $1 ≤ N ≤ 500, 1 ≤ k ≤ 100$.
Выходные данные
Выходной файл должен содержать единственное число — номер уцелевшего человека.
Тесты
| Входные данные | Выходные данные |
| 10 3 | 4 |
| 17 5 | 11 |
| 76 32 | 58 |
Код решения
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), k = in.nextInt(); ArrayList<Integer> ns = new ArrayList<Integer>(n); for (int i = 1; i <= n; i++) ns.add(i); int i = 0, j = 0; while(n > 1) { j = (++j) % k; if(j == 0) { n--; ns.remove(i); } else { i = (++i) % n; } } System.out.println(ns.get(0)); } } |
Решение задачи
Все делается по алгоритму: убирается каждый $k$-тый человек до тех пор, пока не останется один.
Ссылки
Условие задачи на e-olymp.com
Решение задачи на ideone.com