Задача про праздничный ужин - Turbo Pascal
Формулировка задачи:
Задача 6. Праздничный ужин
Автор: Центральная предметно-методическая комиссия по информатике
Входной файл: dinner.in Ограничение времени на тест: 2 сек
Выходной файл: dinner.out Ограничение памяти на тест: 256 Мб
Максимальная оценка: 100 баллов
Условие
Рядом с офисом компании, в которой работает программист Джон, открылось новое кафе. Директор компании решил провести там новогодний ужин.
Меню праздничного новогоднего ужина в кафе состоит из k типов блюд. Для каждого типа блюда есть несколько вариантов на выбор. Всего есть a1 вариантов для первого типа блюда, a2 вариантов для второго типа блюда, и так далее, ak вариантов для k-го типа блюда. Всего, таким образом, предлагается a1 × a2 × … × ak различных заказов праздничного ужина.
Всего на ужине будут присутствовать m сотрудников компании. Каждый сотрудник должен заказать ровно один вариант блюда каждого типа на выбор. Таким образом, ужин каждого сотрудника будет состоять из k блюд. Для того чтобы ужин каждого сотрудника компании был уникален, администратор кафе придумал следующую схему. Сотрудники делают заказ ужина из меню один за другим. Каждый сотрудник выбирает k блюд, по одному варианту каждого типа. После выбора заказа из меню, сотрудник указывает один их типов блюд, и выбранный этим сотрудником вариант блюда этого типа больше не предлагается тем сотрудникам, которые делают заказ после него.
Каждый сотрудник компании запомнил, сколько возможных заказов ужина ему было предложено. Выяснилось, что директору, который выбирал первым, было предложено на выбор n1 = a1 × a2 × … × ak заказов. Тому, кто выбирал вторым, досталось лишь n2 < n1 заказов, поскольку один из вариантов одного из типов блюд уже не был доступен, и так далее. Джону, который выбирал последним, был предложен выбор лишь из nm заказов. Джон заинтересовался, а какое количество вариантов каждого типа блюд было на выбор у директора компании.
Требуется написать программу, которая по заданным числам k, m и n1, n2, …, nm выяснит, какое количество вариантов каждого типа блюд изначально предлагалось на выбор.
Пояснения к примеру
События в примере могли развиваться, например, следующим образом. Исходно количество заказов ужина было равно 3 × 2 × 2=12. Директор, выбрав свой заказ, указал блюдо первого типа, поэтому второму сотруднику осталось лишь два варианта блюда первого типа. Количество заказов для него сократилось до 2 × 2 × 2 = 8. Он также указал на свое блюдо первого типа, и Джон уже мог выбирать лишь из 1 × 2 × 2 = 4 заказов ужина.
Формат входного файла
Первая строка входного файла содержит два целых числа k и m, разделенных ровно одним пробелом. Вторая строка содержит m чисел: n1, n2, …, nm.
Формат выходного файла
Выходной файл должен содержать k чисел: a1, a2, …, ak. Если возможных вариантов решения поставленной задачи несколько, требуется вывести любой. Соседние числа должны быть разделены ровно одним пробелом. Гарантируется, что хотя бы одно решение существует.
Ограничения
1 ≤ k ≤ 20; 2 ≤ m ≤ 100; ∀ i ∈ 1..m: 1 ≤ ni ≤ 109
Примеры тестов
№ Входной файл
3 3
12 8 4
Выходной файл 3 4 1
Решение задачи: «Задача про праздничный ужин»
textual
Листинг программы
var a:array[1..100] of integer; b:array[1..20] of integer; i,k,m,j,nb,fl,t:integer; function Nod(a,b:integer):integer; begin while (a<>0) and (b<>0) do if a >= b then a:= a mod b else b:= b mod a; if a>0 then Nod:=a else Nod:=b; end; begin read(k,m); for i:=1 to m do read(a[i]); for i:=m-1 downto 1 do begin t:=Nod(a[i],a[i+1]); fl:=0; for j:=1 to nb do if b[j]=(a[i+1] div t) then begin fl:=j; break; end; if fl>0 then b[fl]:=b[fl]+1 else begin inc(nb); b[nb]:=a[i+1] div t+1; end; end; i:=1; while i<=nb do begin a[1]:=a[1] div b[i]; write(b[i],' '); inc(i); dec(k); end; if k>0 then begin write(a[1],' '); dec(k); end; while k>0 do begin dec(k); write(1,' '); end; end.
Объяснение кода листинга программы
- Создается переменная
a
типаarray[1..100] of integer
. Это массив из 100 целых чисел. - Создается переменная
b
типаarray[1..20] of integer
. Это также массив из 20 целых чисел. - Создаются переменные
i
,k
,m
,j
,nb
,fl
иt
. Все они являются целыми числами. - Определяется функция
Nod
, которая принимает два целых числаa
иb
в качестве параметров и возвращает наибольший общий делитель этих чисел. - В цикле
while
происходит сравнениеa
иb
. Если оба числа не равны нулю, то выполняется проверкаif a >= b then
иelse if b >= a then
. Если первое условие истинно, тоa
делится наb
без остатка, и в противном случаеb
делится наa
без остатка. Затем выполняется вызов функцииNod
для пары чиселa
иb
, и результат присваивается переменнойNod
. Еслиa
больше нуля, тоNod
будет равноa
, иначеNod
будет равноb
. - Если
a
больше нуля, то вызывается функцияNod
, и результат присваивается переменнойt
. Затем выполняется циклfor
отi=1
доm
с шагом 1, и для каждого значенияi
считывается числоa[i]
из массиваa
. - В цикле
for
выполняется проверкаif b[j]=(a[i+1] div t)
тогдаfl=j
. Если это условие истинно, то значениеj
сохраняется в переменнойfl
, и цикл прерывается командойbreak
. Если условие ложно, то значениеj
увеличивается на 1, и цикл продолжается. Если значениеfl
больше нуля, то значениеb[fl]
увеличивается на 1, иначеnb
увеличивается на 1. - Если
fl
больше нуля, то значениеb[fl]
увеличивается на 1, иначе выполняется командаinc(nb)
. Затем значениеa[i+1]
делится наb[i]
из массиваb
, и результат записывается вb[i]
. - Цикл
while
продолжается до тех пор, покаi
меньше или равноnb
, и после каждой итерации значениеi
увеличивается на 1. - Если
k
больше нуля, то значениеa[1]
делится наb[i]
из массиваb
, и результат записывается вb[i]
. Затем значениеi
увеличивается на 1, иdec(k)
выполняется до тех пор, покаk
не станет меньше нуля. Значениеk
затем записывается вa[1]
. - Если
k
меньше нуля, то выполняется командаdec(k)
. Затем значениеk
записывается вa[1]
. - Цикл
while
продолжается до тех пор, покаk
меньше нуля, и после каждой итерации значениеk
уменьшается на 1.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д