Форум Всеукраїнської інтернет-олімпіади NetOI

3. При розв'язанні цієї задачі багато учасників отримали неповний бал із-за того, що не зуміли вірно врахувати, якого максимального значення може набувати відповідь до задачі.

5. Як нюанс - у ТС100 достатньо і одного масиву. Використання 4-х описаних вище, є не раціональним використанням пам'яті. Хоча на 100% розв'язок задачі це, звичайно, не впливає. Типовою помилкою із-за чого багато учасників "недорахувались" повної кількості балів було або  неакуратне поводження з індексами, або "зубудькуватість" у необхідності обнулення проміжних змінних.

Відредаговано Присяжнюк А.В. (2011-11-17 19:33:35)

ТС-100 з одним масивом.
Заводимо один масив (можна і булівський), де 1 (true)  - це танк пошкоджено, а 0 (false) - танк робочий.
Робимо 4-ри проходи кожен раз з відповідної сторони дивлячись від "диктатора", рахуючи усі непошкоджені (0) танки, поки не зустрінемо пошкоджений. У випадку зустрічі з пошкодженим далі по цьому рядку (стовбцю), у залежності від того у якому напрямку ми в даний час розглядаємо рух, можна не йти.
Серед 4-х кількостей вибираємо (у процесі розгляду) максимальний.
Ось так коротко - здається усе.

Булівський масив займе ще менше, про що я і написав.
Дилема "виграш у пам'яті чи часі" завжди стояла, стоїть і буде стояти перед програмістами. У даному випадку більш раціональним є як раз цей підхід.
При значному збільшенні обмежень на задачу більш раціональним буде запропонований Вами.
Ось Вам і відповідь: відповідь неоднозначна, оскільки залежить від обмежень.
Але алгоритм, запропонований мною, у даному випадку більш раціональний.
Взагалі, робота з булівськими змінними та масивами варта окремої розмови...

Відредаговано Присяжнюк А.В. (2011-11-17 19:58:26)

Может у кого нибудь есть решение на паскале, не все же c++ понимают

Dim_ov написав:

Andrey1998 написав:

Может у кого нибудь есть решение на паскале, не все же c++ понимают

Ну, як писав Анатолій Васильович - код сам по собі має значно меншу цінність, ніж словесний опис алгоритму. Спробуй якось зрозуміти, що там робиться по коментарях.
Але думаю, скоро з’явиться хтось із паскалістів, тож можеш почекати.

Ну і раджу навчитися хоч на базовому рівні розуміти C-подібні мови. Вони значно ширше використовуються, ніж паскаль та делфі.

Согласен объяснения - более важно, но сравнить свою программу(где не можешь найти ошибки) на PAS с программой на C(+/++) и т.п. сложновато
Если циклы и объявления таблиц, переменных и т.п. паскалисты понимают, а например такую запись:
(M%k?1:0)
понять сложно даже зная базу
Увидев такую запись, я бы понял её так: M*k[1],0
если можно расшифруйте пожалуйста

Відредаговано Andrey1998 (2011-11-17 20:47:15)

Dim_ov написав:

Як на мене, чотириразове копіювання майже ідентичного коду для чотирьох напрямків має значно більше місця для потенційних помилок, в основному, через неуважність.

Категорично підтримую!!!

Dim_ov написав:

Буду першим...
Викладаю повнобальні рішення.

Rec5:
Загальна ідея: щоб знайти площу спільної частини прямокутників треба перемножити довжини спільних частин проекцій прямокутників на вісі Х та У.

Код:

#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

struct point                                                                    //просто зручніша обгортка для роботи з точками.
{
    ll x,y;
    friend istream& operator>>(istream &in,point &rhs){return in>>rhs.x>>rhs.y;}
};

int main()
{
    point lb[2],rt[2];
    ll x,y;
    for(int i=0;i<2;i++)                                                        //читаємо координати двох точок кожного з прямокутників
    {                                                                           //і за необхідності обмінюємо значення координат так, щоб
        cin>>lb[i]>>rt[i];                                                      //у нас були ліва-нижня та права верхня точки.
        if(lb[i].x>rt[i].x)swap(lb[i].x,rt[i].x);
        if(lb[i].y>rt[i].y)swap(lb[i].y,rt[i].y);
    }
    //↓Відстань між двома самими дальніми       ↓довжина проекції   ↓довжина проекції
    //↓по вісі Х точками.                       ↓першого            ↓другого
    //↓                                         ↓прямокутника на    ↓прямокутника на 
    //↓                                         ↓вісь Х             ↓вісь Х
    x=max(rt[0].x,rt[1].x)-min(lb[0].x,lb[1].x)-((rt[0].x-lb[0].x)+(rt[1].x-lb[1].x));
    /*
      В результаті таких маніпуляцій ми або отримали від’ємну довжину перетину проекцій прямокутників на вісь Х, або
      додатню відстань між проекціями, якщо вони не перетинаються. Оскільки нас цікавить лише перше - обнуляємо Х у разі, 
      якщо він додатній, а потім змінюємо знак.
    */
    if(x>0)x=0;
    else x=-x;
    /*
      Для ігрека все аналогічно.
    */
    y=max(rt[0].y,rt[1].y)-min(lb[0].y,lb[1].y)-((rt[0].y-lb[0].y)+(rt[1].y-lb[1].y));
    if(y>0)y=0;
    else y=-y;
    cout<<x*y<<endl;//ну і вивід результату
    return 0;
}

Не розумію, що таке struсt і ці рядки  y=max(rt[0].y,rt[1].y)-min(lb[0].y,lb[1].y)-((rt[0].y-lb[0].y)+(rt[1].y-lb[1].y));

Все одно не розумію цей код. Напевне тому що я не знайом з бібліотекою яку ви використовуете.

Так. Треба знайти довжини проекцій по осям і знайти довжину їх перетину. Це як би розширення до задачі, що була на тестовому турі. Але я все одно не розумію як це реалізувати.

Я дуже дивуюся, що Ви мені так допомагаєте...

Если стороны прямоугольников параллельны осям координат (а по условию это так), а (x1, y1) и (x2, y2) - координаты левого нижнего и правого верхнего угла первого прямоугольника, (x3, y3) и (x4, y4) - координаты левого нижнего и правого верхнего угла второго прямоугольника.  (по условию это не так)
Тогда площадь пересечения равна
max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0)

Итак задача сводится к решению двух проблем.
1-    установить координаты левых нижних и правых верхних углов прямоугольников:
if (x1>x2) swap(x1,x2);
if (y1>y2) swap(y1,y2);
if (x3>x4) swap(x3,x4);
if (y3>y4) swap(y3,y4);
2-    заставить работать выражение в С++
max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0)
для больших чисел (10^6)


Вот как это сделал я (возможно и корявенько, но на 20 баллов сработало   )
//Rec5
#include <iostream>
using namespace std;
int main(){
long long x1,y1,x2,y2,x3,y3,x4,y4,a,b;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
if (x1>x2) swap(x1,x2);
if (y1>y2) swap(y1,y2);
if (x3>x4) swap(x3,x4);
if (y3>y4) swap(y3,y4);
//формула max((min(x2, x4) - max(x1, x3)), 0) * max((min(y2, y4) - max(y1, y3)), 0);
// работает только для int)
// поэтому заменим:
// min(x2, x4) на x2
if (x2>x4) swap(x2,x4);
//max(x1, x3) на x3
if (x1>x3) swap(x1,x3);
//min(y2, y4) на y2
if (y2>y4) swap(y2,y4);
//max(y1, y3)  на y3
if (y1>y3) swap(y1,y3);

a=x2-x3;
    b=y2-y3;
if ((a>0)&&(b>0)) cout<<a*b; else cout <<0;
return 0;
}

Відредаговано LVV (2011-11-18 19:23:37)

// Wall
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n,m,k,l,r;
cin >> n >> m >> k;
/* l=k/n (остаток отбрасываем)-на сколько полосок по вертикали хватает одного рулона*/
l=k/n;
/*r=m/n (округлённое вверх) количество рулонов, для покрытия всей стены */
r=int(ceil(double(m)/l));
/*площадь рулонов минус площадь стены = остатки*/
cout << r <<" "<<r*k-n*m;;;
return 0;
}

Відредаговано LVV (2011-11-18 19:25:14)