1

Тема: Кількість прямокутників

Допоможіть вирішити таку задачу: Порахувати, скільки існує прямокутників, площа яких знаходиться в межах від А до В, а периметр від С до D.
Простим перебором набирається 42 відсотки тестів. Потрібна якась математина уловка. Дякую.

2 Востаннє редагувалося koala (06.01.2020 13:49:28)

Re: Кількість прямокутників

По-перше, надайте повну умову і свій код. Ми не телепати відгадувати, "від ... до ..." - це включно чи ні, і помилки в коді без коду не побачимо.
По-друге, таких прямокутників 0 (якшо умови несумісні), 1(якщо межі периметра однакові) або нескінчено багато. Як ви нескінченість перебором збираєтеся отримувати? Питання лише про прямокутники з цілочисленими сторонами? Чи з парними? Чи ще якимось?

3 Востаннє редагувалося koala (06.01.2020 14:01:00)

Re: Кількість прямокутників

І на якому сайті ви перевіряли? Всі числа значенням до 10 в 9.

program fff;

var
  a, b, c,d, s, p, n,k,g: int64;
  l, i,j,k1,max: int64;

begin
  readln(a, b, c, d);
  n := 0;
  k1:=trunc(sqrt(b));
  g:=d div 2-1;
if k1<=g then max:=k1 else max:=g;
  for l := 1 to max do
    for k := l  to d div 2-1 do
    begin
      s := l * k;
       p := (l + k) * 2;
         if (s >= a) and (s <= b) and (p >= c) and (p <= d) then begin
         n := n + 1;
      end;
           end;
    
  writeln(n);
 
end.

4

Re: Кількість прямокутників

Теги code наступного разу самі додавайте.
Моя перша відповідь була прозорим натяком на відсутність тут телепатів, але, схоже, я правильно її замінив, бо натяку ви не зрозуміли.

5

Re: Кількість прямокутників

Загальні поради:
- Давайте змінним людські назви; звісно, в умові a,b,c,d, але s_min, s_max, p_min, p_max значно легше сприймати.
- Вирівнюйте код. if k1<=g у вас поза функцією блоком begin-end? А другий end; - він до якого begin? Чому треба читати весь код, щоб зрозуміти, де закінчується блок? Структурне програмування придумали для того, щоб не треба було лізти в непотрібні деталі. Ви самі себе (і нас теж) відволікаєте від задачі.
- Складні порівняння ліпше записувати через < та <=.

(a<=s) and (s<=b)

читається краще, ніж у вас.

Тепер - по задачі. Я виходитму з того, що код не проходить через часові обмеження (а це не факт, треба дивитися, але ваш код просто неможливо читати). Ви не підтвердили, що питання про цілі значення сторін; поки що припущу, що це саме так. Якщо ви візьмете по вісі x один бік, а по вісі y - другий, то в кожній точці можна буде встановити площу, а лінії, утворені прямокутниками з рівною площею, утворюватимуть криві xy=c, тобто гіперболи. Вам треба полічити цілі точки між гіперболами xy=c та xy=d та прямими x+y=a/2, x+y=b/2. Якщо важко це уявити - візьміть таблицю Піфагора і проведіть лінії, не знаю, xy=40 та xy=60.

6

Re: Кількість прямокутників

Межі включно. Цілі числа. Всі числа до 10 в 9.

7

Re: Кількість прямокутників

igors66 написав:

10 в 9.

Десять в дев'ятому степені? Це дійсно багато, і треба думати про способи прискорити обрахунки.

8 Востаннє редагувалося koala (07.01.2020 09:35:33)

Re: Кількість прямокутників

Ось графіки: https://www.desmos.com/calculator/pqip6ohqes
Нас цікавить кількість цілих чисел між цими лінями.
На перший погляд, не бачу нічого кращого за приблизно таке:
- Знаходимо перетин x+y=D та xy=A (якщо немає перетину - повертаємо 0)
- В циклі зі зменшенням по x від перетину (x1,y1) до (y1,x1) обчислюємо ліву і праву межі як максимум і мінімум відповідних ліній. Округлюємо межі вгору ліву і вниз праву, різниця + 1 - кількість цілих між ними. Сумуємо.
- Можна оптимізувати, якщо шукати лише до діагоналі x=y. Але тоді треба буде враховувати діагональ лише один раз, а всі інші точки - по два рази.

Орієнтовна складність O(n^0.5)