Задача A. НЖМД Имя входного файла: harddrive.in
Имя выходного файла: harddrive.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Бедному НЖМД уже много лет. И все эти годы он непрестанно трудится в недрах старого ПК.
НЖМД — это ни что иное как обычный жесткий диск на котором хранится один большой Очень
Важный Файл. И НЖМД очень устал непрестанно крутиться, чтобы обеспечивать постоянный
доступ к этому Файлу.
Как известно, для хранения файлы разбиваются на много блоков одинакового размера, которые
могут хранится в различных местах жесткого диска, не обязательно последовательно — это
называется фрагментацией. Вот и сейчас получилось, что Очень Важный Файл занимает весь
НЖМД, но блоки, на которые он разбит, расположены не последовательно.
Данные с жесткого диска могут считываться специальной считывающей головкой, причем
для доступа к различным местам жесткого диска считывающая головка вращается относительно
жесткого диска, но всегда в одну и ту же сторону. Блоки можно считывать только в той
последовательности, в которой они образуют файл, то есть сначала необходимо переместить
головку на место расположения первого блока, считать его, далее переместить головку на место
расположения второго блока, считать его и так далее. Таким образом, из-за непоследовательности
расположения данных получается, что за один оборот жесткого диска, возможно, не получится
считать весь файл.
Вам известно в каком порядке на НЖМД расположены блоки, на которые разбит файл. Ваша
задача состоит в том, чтобы найти минимальное число полных оборотов считывающей головки
относительно жесткого диска, которые ей придется сделать, чтобы прочитать весь файл от первого
до последнего блока.
Формат входного файла
Первая строка входного файла содержит единственное натуральное число n (1 ≤ n ≤ 105
) —
количество блоков, на которые разбит файл.
Следующая строка содержит n различных натуральных чисел pi (1 ≤ pi ≤ n) — перестановку
чисел от 1 до n, задающую в какой последовательности хранятся блоки файла. pi — номер блока,
который хранится на i-ом месте в сторону вращения жесткого диска.
Изначально считается, что считывающая головка находится перед первым блоком. Считается,
что головка делает полный оборот, когда ей приходится проходить между n-ым и первым блоком.
Формат выходного файла
В выходной файл выведите единственное целое число — минимальное количество оборотов,
которое необходимо совершить считывающей головке, чтобы прочитать весь Очень Важный Файл
от первого до последнего блока.
Примеры
harddrive.in harddrive.out
3
3 1 2
1
2
1 2
0
4
4 3 2 1
3
нужно решить на паскале
Информационный объем I = 44100 Гц * 5 * 60 с * 16 бит = 211680000 бит = 26460000 байт = 25839,84375 Кбайт = 25,23422241210938 Мбайт
Задание 2
I = 1,3 Мбайт t = 1 мин Частота дискретизации v = 1,3 * 1024 * 1024 * 8 бит / 60 с / 8 бит = 22719,147 Гц
Задание 3
I = 5.1 Мбайт, t = 2 минуты, v = 22050 Гц Разрядность аудиоадаптера i = 5.1 * 1024 * 1024 * 8 бит / (2 * 60) с / 22050 Гц = 16,1685 бит (округленно 16 бит)
Задание 4
I = 0.01 Гбайт, i = 16 бит, v = 44100 Гц Время t = 0,01 * 1024 * 1024 * 1024 * 8 бит / 16 бит / 44100 Гц = 121 с (округляем до 120 с)
int main(){
int div[10001];
int i,d,n,x;
long int p = 1;
for(i = 0; i < 10000; i++)
div[i] = 1;
scanf("%d",&n);
for(i = 0; i < n; i++){
scanf("%d",&x);
d = 2;
while(d <= x){
while(x%d == 0){
x /= d;
div[d]++;
}
d++;
}
}
for(i = 0; i < 10000; i++)
p *= div[i];
printf("%ld",p);
return 0;
}
/*
Небольшое пояснение:
Идея решения заключается в том, что любой делитель результата представим как произведение простых чисел в определенных степенях. Тогда набор этих степеней однозначно определяет соответствующий делитель. Максимальная степень, с которой может быть взято простое число, является суммой степеней, с которыми оно входит в множители.
Для простоты массив вхождений делителей задан от 0 до 10000, но т.к. перебор делителей множителей идет по возрастанию, учтены будут только простые делители.
Пример:
10 * 8 * 9 = 720
10 = 2^1*5^2
8 = 2^3
9 = 3^2
Т.е. число 2 входит в произведение в четвертой степени, 3 - во второй, 5 - в первой.
Значит любой делитель числа 720 представим (единственным образом) в виде
2^(d2) * 3^(d3) * 5^(d5), где d2 = 0..4, d3 = 0..2, d5 = 0..1
Например, 1 = 2^0 * 3^0 * 5^0, 720 = 2^4 * 3^2 * 5^1
Есть выбрать выбрать d3 и выбрать d5 --> всего 5 * 3 * 2 = 30 возможных наборов --> 30 делителей у числа 720
(если какое-то число не появляется среди делителей множителей, то его можно взять только одним со степенью 0 - что не влияет на ответ)
*/