Рациональное размещение плиток на плоскости

Bringoff · Регистрация: 03.11.2012

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

Сама задача

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

Задача C . Кафельная плитка
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Иннокентий устроил ремонт на кухне. Как профессиональный строитель, он прекрасно знает,
что для кухни нет ничего лучше кафельной плитки.
Кухня Иннокентия представляет собой прямоугольник W на H метров. К сожалению, нужная
плитка продается только в одном магазине. Каждая плитка имеет фиксированный размер a на b
метров, и на нее нанесен интересный узор. Для того, чтобы пол кухни выглядел красиво, плит-
ку надо класть так, чтобы каждая сторона плитки граничила максимум с одной плиткой и была
параллельна одной из сторон кухни. Узор является очень специфическим, поэтому плитки нельзя
поворачивать, даже все одновременно сторона кухни длиной W должна быть всегда параллель-
на стороне плитки длиной a.
Возможно
,
плитки придется разрезать на меньшие части с помощью прямолинейных разрезов
вдоль одной из сторон. При этом полученные части плитки можно также разрезать на меньшие
части. Иннокентий хочет замостить кухню так, чтобы в итоге было использовано минимально воз-
можное количество плиток и их частей.
Помогите Иннокентию выяснить
,
какое минимальное число целых плиток размером a на b нужно
купить, чтобы красиво замостить всю кухню.
Формат входного файла
В первой строке входных данных содержатся два целых числа W и H размеры кухни
(1 <= W, H <= 10 000) . В следующей строке содержится два целых числа a и b размеры одной
плитки (1 <= a <= W , 1 <= b <= H) .
Формат выходного файла
Выведите одно число минимальное число плиток, которое необходимо купить Иннокентию.
Помните
,
что плитки ни в коем случае нельзя поворачивать!
Примеры
stdin stdout
10 10 25
2 2

3 5 4
2 2

35 17 26
25 1

Мое решение, точнее, нерешение:

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
program C;
 var
  w,h,a,b,N,split,skyh,szayv,s,wzayv,hzayv,nwzayv,nhzayv:integer;
   begin
    readln(w,h);
    readln(a,b);
    skyh:=h*w;
    split:=a*b;
    N:=skyh div split;
    szayv:=skyh mod split;
    wzayv:= w mod a;
    hzayv:= h mod b;
    while ((wzayv)<>0) or ((hzayv)<>0) do
     begin
      if wzayv<>0 then
      begin
      nwzayv:=a div wzayv;
      wzayv:= a mod wzayv;
      N:=N+nwzayv;
      end;
      if hzayv<>0 then
       begin
       nhzayv:=b div hzayv;
       hzayv:= b mod hzayv;
       N:=N+nhzayv;
       end;
 
     end;
     if szayv>0 then N:=N+1;
    Writeln(N);
    end.

Кто мне поможет?

Добавлено через 20 часов 18 минут
Народ, где тот умник, который укажет мне на хотя бы ошибку в логике?

@kingofshadows · 08.12.2012, 20:52

у меня проходит 7 тестов из 20:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
program plitka;
var w,h,a,b,s,e:integer;
begin
readln(w,h);
readln(a,b);
if(w mod a <> 0) or (h mod b<>0) then begin
s:=w-a;
e:=h-b;
writeln(s+e);
end else if (w mod a<>0) and (h mod b<>0) then writeln((w div a+1)*(h div b+1))
else if (w mod a=0) and (h mod b =0)then  writeln((w*h) div (a*b))
else if(w mod a<>0) and (h mod b =0) then writeln((h div b)*(h div b+1))
else if (w mod a =0) and (h mod b<>0) then writeln((w div a)*(w div a+1));
end.

Не могу понять в чем ошибка.

@zalipuha · 28.09.2013, 13:25

Я прекрасно понимаю что теме уже год, но все же.Я сейчас тоже пытаюсь решить задачи из той серии.
Может быть я в чем то заблуждаюсь, но, мне кажется что 3 пример неправилен, т.к там будет 24 плитки, пруф на картинке.В каком месте я ошибаюсь?
Прямоугольник - 35х17.Плитки 1-17 ложатся параллельно друг другу.18-24 разрезаются по два раза, имеем право из условий.
Вот мое решение

C++
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
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
 
int main(){
 
    int W, H, a, b;
    ofstream I("stdin.txt");
    cin >> W >> H
        >> a >> b;
    I << W  << ' '<< H << "\n" << a << ' ' << b << endl;
    I.close();
 
    int PL;
    int del = (W*H)/(a*b);
    int ost = (W*H)%(a*b);
 
    if(ost > 0){
        PL = del+1;
    }
    else{
        PL =del;
    }
 
    ofstream O("stdout.txt");
    O << PL << endl;
    O.close();
 
getch();
}

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .