Олимпиадная задача по информатике 1997 год

@Jordan_Belford · Регистрация: 06.08.2014

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

Доброго времени суток. Попалась олимпиадная задача по информатике за 97 год.

Возьмем клетчатую доску MxN (1<=M,N<=4). Воткнем в каждую клеточку штырек. В нашем распоряжении есть K (0<K<20) абсолютно одинаковых колечек, каждое из которых можно нанизывать на штырек, причем на один штырек можно надеть несколько колечек. Подсчитать, сколькими способами можно распределить все эти колечки по штырькам. Два распределения считаются разными, если на каком-то из штырьков находится разное количество колечек, и одинаковыми в противном случае.
Входные данные : M N K
Пример : Входные данные : 2 2 2 Результат : 10

Нашёл реализацию почти такой задачи на языке PASCAL, но мне нужно на Си. Прошу помочь переделать из PASCAL на Си. Задачка очень занимательная и сложная. Заранее спасибо.

к программе прилагается ещё план

Кликните здесь для просмотра всего текста

Заполняем нулями массив двоичного числа
Пока не получено последнее двоичное число, делать
Получить очередное двоичное число и сразу посчитать
минимальную сумму
Если минимальная сумма меньше или равна L, то
Массив Числа заполнить единицами в соответствии с массивом
двоичного числа
Если полученная минимальная сумма равна L, то массив Числа
вывести на экран, так как это искомый результат
Вызывать рекурсивную процедуру дополнения массива Числа

листинг программы на PASCAL

Кликните здесь для просмотра всего текста

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
program example;
 uses crt;
 var
  b,a:array[1..100] of word;
  num,i,n,l,sum:word;
function final:boolean;
var
 i:integer;
 q:boolean;
begin
 q:=false;
 for i:=1 to n do
  if b[i]=0 then q:=true;
 final:=q;
end;
procedure Init;
var
 i:integer;
begin
 for i:=1 to n do
   if (b[i]=1) then a[i]:=1  else a[i]:=0;
end;
procedure print;
var
 i:integer;
begin
 num:=num+1;
 write(num,') ');
 for i:=1 to n do
  write(a[i],' ');
 write('     ');
 for i:=1 to n do write(b[i],' ');
 writeln;
end;
procedure Plus_1(sum,x:integer);
var
 i:integer;
begin
 if (x<=n) and (sum<l) then
   for i:=x to n do
          if b[i]=1 then
      begin
       a[i]:=a[i]+1;
       sum:=sum+1;
       if sum=l then print;
       if sum<l then  Plus_1(sum,i);
       a[i]:=a[i]-1;
       sum:=sum-1;
      end;
end;
function digit:word;
var
 i,k,m:integer;
begin
 i:=1;
 while (b[i]=1) and (i<=n) do i:=i+1;
 b[i]:=1;
 for k:=1 to i-1 do b[k]:=0;
 m:=0;
 for i:=1 to n do
  if b[i]=1 then m:=m+1;
 digit:=m;
end;
begin
 clrscr;
 read(n,l);
 n:=n*n;
 num:=0;
 for i:=1 to n do b[i]:=0;
 while final do
  begin
   sum:=digit;
   if sum<=l then
    begin 
     Init;
     if sum=l then print;
     Plus_1(sum,1);
    end;
  end;
end.

@gng · 21.11.2014, 22:15

Простым перебором всех (N*M)-значных чисел по основанию (K+1)

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main() {
  int M, N, K, n, k, i, min, max, sum, count= 0;
  scanf ("%d %d %d", &M, &N, &K);
  n= M * N;
  min= K; max= min;
  for (i= 1; i < n; i++) max*= (K+1);
 
  for (i= min; i <= max; i++) {
    for (k= i, sum= 0; k> 0; k/= K+1) sum+= (k % (K+1));
    if (sum == K) ++count;
  }
  printf ("%d\n", count);
}

@Jordan_Belford · 03.12.2014, 19:54 **[ТС]**

спасибо большое

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@Jordan_Belford 0 / 0 / 0 Регистрация: 06.08.2014 Сообщений: 8
	03.12.2014, 19:54 [ТС]
	спасибо большое 0

Олимпиадная задача по информатике 1997 год

Решение