06/04/2025 18:05:36

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

812. Дефрагментация диска FAT32

Ограничения: время – 1s/2s, память – 3MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1)

Дисковое пространство поделено на так называемые кластеры. При записи на диск файлы разделяются на части размером с кластер. Если все части файла размещены последовательно в последовательных кластерах диска, то последовательное чтение файла происходит максимально быстро. При изменении файла отдельные его части (фрагменты) могут оказаться разбросанными по всему диску в произвольном порядке, т. е. файл становится фрагментированным. При этом быстродействие компьютера снижается. Обычно дефраментация проводится, когда число фрагментированных файлов составляет 10-20% или более от числа всех файлов. Для определения степени фрагментации можно использовать таблицу размещения файлов FAT (File Allocation Table). Упрощенно ее можно описать следующим образом. Дисковое пространство делится на

$M$ кластеров, нумерующихся с 1 до

$M$ . В таблице FAT для каждого кластера диска записывается число 0, если соответствующий кластер свободен, или число

$-1$ , если это последний кластер файла, или число от 1 до

$M$ , указывающее на следующий кластер, занятый файлом.

Во входном файле в первой строке содержится количество кластеров на диске

$M$ (

$1\ ≤\ M\ ≤\ 500000$ ), в последующих

$M$ строках – таблица FAT. Данные корректны, т.е. не содержат циклов и пересечений.

В выходной файл вывести в первой строке вывести общее число файлов на диске, во второй строке – число фрагментированных файлов. Файл будем считать не фрагментированным, если для всех частей файла верно, что

$i$ часть файла занимает

$b+i-1$ кластер, где

$b$ – первый кластер файла.

Пример ввода

Пример вывода

2
1

26/02/1999	Командные соревнования университета по программированию (2)
12/03/2008	Занятие 17 (2)