Информатика

4 314 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: успешные, неуспешные.
Громозека играет в одиночную игру, используя числовую прямую и N фишек. Каждая из фишек расположена в некоторой целочисленной координате. Заметьте, несколько фишек могут быть размещены в одной и той же координате.
Цель игры: посетить фишками все M координат X1, X2, ..., XM, повторив следующий ход.
Ход: выберите фишку с координатой X. Поместите эту фишку в координату X+1 или X-1.
Обратите внимание, что координаты, где мы первоначально размещены фишки, уже считаются посещенными.
Найдите минимальное количество ходов, необходимое для достижения цели.

Входные данные
В первой строке программа получает на вход два целых числа: N и M (1 <= N, M <= 105). Во второй строке записаны M целых чисел X1, X2, ..., XM (-105 <= Xi <= 105). Все числа Xi различны.

Выходные данные
Выведите на экран ответ на задачу.
 
Примеры
Входные данные Выходные данные Пояснение
1 2 5
10 12 1 2 14
5 Цель может быть достигнута за пять ходов следующим образом, и это минимально необходимое количество ходов.
Сначала поместите две фишки в координаты 1 и 10.
Переместите фишку с координатой 1 на 2.
Переместите фишку с координатой 10 на 11.
Переместите фишку с координатами 11 на 12.
Переместите фишку с координатами 12 на 13.
Переместите фишку с координатами 13 на 14.
2 3 7
-10 -3 0 9 -100 2 17
19  
3 100 1
-100000
0  
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город И?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
 
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, но не проходящих через город И?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, но не проходящих через город Е?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, но не проходящих через город Г?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, но не проходящих через город З?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, но не проходящих через город Д?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, но не проходящих через город Б?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город К?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Г?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Ж?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Г?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Ж?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город В?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город В?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)

 
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город Ж?
(Картинку можно увеличить, кликнув по ней. Откроется в новом окне)
Поделиться
Класснуть