IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Кубики, задача
sheka
сообщение 18.01.2010 0:19
Сообщение #1


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


Вот задача с олимпиады. (переводил переводчиком...вот оригинал Прикрепленный файл  1.rar ( 36.24 килобайт ) Кол-во скачиваний: 323
)
Цитата
1. Кубики (автор - Александр Рыбак)
Максимальная оценка: 100 баллов
Ограничение по времени: 1 сек.
Ограничение по памяти: 32 MБ
Входной файл: cubes.in
Исходный файл: cubes.out
Приложение: cubes .*
Несмотря на то, что Петрик Пяточкина ходит в школу, он все еще продолжает играть с кубиками.С одинаковых кубиков он излагает ступени вдоль стены. Для этого составляет столбики из кубиков следующим образом:
● первый столбик стоит вплотную к стене;
● второй столбик стоит вплотную к стене и вплотную к первой колонки справа от него;
● третий столбик стоит вплотную к стене и вплотную к второй колонки справа от него и так далее ...
Высоты столбиков не растут при рассмотрении ступенек слева направо. Иначе говоря, если hi - высота i го столбца, то h1 ≥ h2 ≥ h3 ≥ ... .
Петрик устанавливает кубики в некоторой последовательности. Он установил для себя такие правила:
(1) кубик, расположен не на полу, можно поставить только после кубика, на котором он должен стоять. Иначе говоря, нельзя подсовывать кубики под уже поставлены;
(2) кубик, который находится не в первой колонке, можно поставить лишь после установления кубика, расположенного слева от него.
Задачи
Найти количество различных способов последовательного установления кубиков, в результате которых возникнут лестница с заданными высотами столбцов h1, h2, ..., hk.Учитывают только те способы, удовлетворяющих условиям (1) и (2).
Входные данные
Первая строка входного файла содержит натуральное число k - количество столбцов (1 ≤ k ≤ 6).
Вторая строка входного файла содержит k натуральных чисел h1, h2, ..., Hk - количества кубиков соответственно в первый, второй, ..., k м столбце лестницы (6 ≥ h1 ≥ h2 ≥ ... ≥ hk ≥ 1).
Входные данные
Единственная строка выходного файла должна содержать количество различных способов расположения кубиков в заданную конфигурацию согласно указанным правилам (1) и (2) при данных высотах столбцов.

Примеры в архиве(в 1.док)-там табличками просто.
Я ее с горем пополам сделал. Только считает очень долго. Так же не все ответы помещаются в тип Лонгинт, но пока не в этом проблема. Подскажите, почему так долго считает???
*В архиве условия, и указания к решению (которые я к сожалению вообще не понимаю)
а вот плоды моих мИслей) :
{ Turbo Pascal }

type
  matr=array[1..6,1..6]of shortint;

var
  k:byte;
  h:array[1..6]of byte;
  m:matr;
  i,j:byte;
  kol:longint;
  s:byte;
  f:text;

procedure find(nomer:byte;m:matr);
var
  i,j,p:byte;
  f:text;
begin
    for j:=1 to k do
      begin
        if m[1,j]=-1 then
          break;
        for i:=1 to h[j] do
          begin
            if m[i,j]=-1 then
              break;

            if m[i,j]=0 then
              begin
                if (i-1>=1)and(m[i-1,j]=0)then continue;
                inc(nomer);
                m[i,j]:=nomer;
                if i+1<=h[j] then
                  m[i+1,j]:=0;
                if (j+1<=k)and(h[j+1]>=i)and((i-1=0)or((i-1>=1)and(m[i-1,j+1]>=1))) then
                  m[i,j+1]:=0;

                find(nomer,m);
                if nomer=s then
                  inc(kol);
                if (i=1)and(j=1) then
                  begin
                    assign(f,'cubes.out');
                    rewrite(f);
                    writeln(f,kol);
                    close(f);
                    halt;
                  end;
                m[i,j]:=0;
                for p:=i+1 to h[i] do m[p,j]:=-1;
                for p:=j+1 to k do m[i,p]:=-1;

                dec(nomer);
              end;
          end;
      end;
end;



begin
  s:=0;
  assign(f,'cubes.in');
  reset(f);
  readln(f,k);
  for i:=1 to k do
    begin
      read(f,h[i]);
      inc(s,h[i]);
    end;
  close(f);
  for j:=1 to 6 do
    for i:=1 to 6 do
      m[i,j]:=-1;
  m[1,1]:=0;
  kol:=0;
  find(0,m);
end.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
sheka   Кубики   18.01.2010 0:19


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 27.07.2025 22:57
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"