Найти количество способов расставить книги

@ILUHA_PRIKOLUHA · Регистрация: 10.01.2020

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста решить задачу:

В начале учебного года в одном Великом Университете библиотека выдавала книги своим студентам, чтобы они использовали их для получения познаний в течении года. Студентка Олечка, отстояв огромную очередь и получив книги в библиотеке, с великим трудом донесла их до своего дома. Теперь Олечка хочет расставить эти научные труды на свою книжную полку.

К сожалению, с восприятием содержимого книжной полки своей хозяйкой не так все просто — Олечку приводят в уныние книги, стоящие на полке по соседству и имеющие в общей сложности количество страниц, превышающее некоторое значение.

Говоря более точно, Олечка сильно расстраивается, если существует пара книг, стоящих на местах i и (i+1) полки, и общее число страниц в этих двух книгах превышает ai.

Помогите бедной Олечке понять, сколько способов существует расставить книги на полке так, чтобы она не расстраивалась.

В первой строке входного файла записано число n (1 ≤ n ≤ 9) "— число Олечкиных книг. В второй строке находится n чисел pi (1 ≤ pi ≤ 109) "— количество страниц в каждой из книг. В третьей строке находится n-1 число ai (1 ≤ ai ≤ 2 ⋅ 109) "— допустимое общее количество страниц в книгах, стоящих на местах i и i+1 полки.

ввод
3
1 2 1
2 3

вывод

2

ввод
3
1 1 2
1 2

вывод
0

Байт · 10.01.2020, 15:21

ILUHA_PRIKOLUHA, а без сказочки про Олечку можете суть задачи изложить?

@Kuzia domovenok · 10.01.2020, 15:33

C++
1
2
3
4
5
6
7
8
9
10
used[n]={false}
func solve(i, prev=0)
  if (i==n) return 1;
  count=0;  
  for (j=0; j<n; ++j)
    if (!used[j] && p[j]+prev<a[i-1])
        used[j]=true;
        count+=solve(i+1, p[j]);
        used[j]=false;
  return count;

@ILUHA_PRIKOLUHA · 10.01.2020, 20:05 **[ТС]**

Ну давай чо, если тесты пройдёт, то ты красава

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@ILUHA_PRIKOLUHA 0 / 0 / 0 Регистрация: 10.01.2020 Сообщений: 2

	Найти количество способов расставить книги 10.01.2020, 14:09. Показов 1588. Ответов 3 Метки комбинаторика (Все метки) Помогите пожалуйста решить задачу: В начале учебного года в одном Великом Университете библиотека выдавала книги своим студентам, чтобы они использовали их для получения познаний в течении года. Студентка Олечка, отстояв огромную очередь и получив книги в библиотеке, с великим трудом донесла их до своего дома. Теперь Олечка хочет расставить эти научные труды на свою книжную полку. К сожалению, с восприятием содержимого книжной полки своей хозяйкой не так все просто — Олечку приводят в уныние книги, стоящие на полке по соседству и имеющие в общей сложности количество страниц, превышающее некоторое значение. Говоря более точно, Олечка сильно расстраивается, если существует пара книг, стоящих на местах i и (i+1) полки, и общее число страниц в этих двух книгах превышает ai. Помогите бедной Олечке понять, сколько способов существует расставить книги на полке так, чтобы она не расстраивалась. В первой строке входного файла записано число n (1 ≤ n ≤ 9) "— число Олечкиных книг. В второй строке находится n чисел pi (1 ≤ pi ≤ 109) "— количество страниц в каждой из книг. В третьей строке находится n-1 число ai (1 ≤ ai ≤ 2 ⋅ 109) "— допустимое общее количество страниц в книгах, стоящих на местах i и i+1 полки. ввод 3 1 2 1 2 3 вывод 2 ввод 3 1 1 2 1 2 вывод 0 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	10.01.2020, 15:21
	ILUHA_PRIKOLUHA, а без сказочки про Олечку можете суть задачи изложить? 0

@ILUHA_PRIKOLUHA 0 / 0 / 0 Регистрация: 10.01.2020 Сообщений: 2
	10.01.2020, 20:05 [ТС]
	Ну давай чо, если тесты пройдёт, то ты красава 0