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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2011-11-17 17:27:45

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Розв’язки задач

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

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;
}

Calculation:
Загальна ідея: Просто перебираємо всі можливі основи системи числення, в якій може бути записано друге число, переводимо друге число в десяткову систему і порівнюємо з першим. Якщо вони рівні - значить ми знайшли відповідь.

Код:

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

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

ull convert(vector<int> &v,ul base)         //Функція, що переводить число, записане
{                                           //"задом-наперед" із системи числення з
    vector<int>::iterator i;                //основою base в десяткову.
    ull res=0,temp=1;                       //принцип роботи описувати, думаю, не має
    for(i=v.begin();i!=v.end();++i)         //сенсу - будь-яка стаття з основ систем
    {                                       //числення має торкнутися теми переведення 
        res+=(*i)*temp;
        temp*=base;
    }
    return res;
}

int main()
{
    int max=-100;
    ull n,m;                                //оскільки дані числа додатні і можуть містити до 18
    cin>>n>>m;                              //знаків - використовуємо 64-бітний беззнаковий тип.
    vector<int> v;                          //(Хоча, в принципі, знаковий теж має працювати)
    while(m)
    {
        v.push_back(m%10);                  //дописуємо останню цифру другого числа в масив
        
        m/=10;                              //прибираємо останню цифру другого числа
        
        if(v.back()>max)                    //запам’ятовуємо найбільшу цифру другого числа, адже основа с.ч.
            max=v.back();                   //не може бути меншою, ніж найбільша цифра числа.
    }
    for(int i=max+1;i<10;i++)               //власне перебір с.ч.
    {
        if(convert(v,i)==n)                 //якщо числа співпали - відповідь знайдено, і далі не перевіряємо
        {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

Figure:
Загальна ідея: Знову "в лоб" моделюємо шахову дошку матрицею 8*8, яка спочатку заповнена нулями. Після прочитання чергової пари координат збільшуємо число у відповідній ячейці матриці на одиницю. Відповіддю буде максимальне число цієї матриці.

Код:

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

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

int main()
{
    ul m[8][8];                         //Заводимо та обнуляємо нашу "дошку"
    memset(m,0,sizeof(m));
    int n,x,y;
    ul max=0;
    cin>>n;
    while(n--)
    {
        cin>>x>>y;
        x--;y--;                        //масиви в С/С++ індексуються з нуля, тож декрементуємо координати
        m[x][y]++;                      //для даної клітинки збільшуємо "рахівалку" фігур, що там побували
        if(m[x][y]>max)max=m[x][y];     //і одразу ж оновлюємо максимум, якщо це потрібно.
    }
    cout<<max<<endl;
}

Wall:

Код:

#include <iostream>
using namespace std;

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

int main()
{
   int N,M,K,k,sum,remainder;
    cin>>N>>M>>K;
    k=K/N;                          //k - кількість смуг, які можна повнімтю заклеїти одним рулоном
    
    sum=M/k+(M%k?1:0);
    /*
      Ділимо кількість смуг, які необхідно заклеїти на кількість смуг, які захоплює один рулон. Таким чином отримуємо кількість рулонів.
      Але це число зараз показує кількість рулонів, які будуть використані ПОВНІСТЮ, тому нам потрібно округлити його догори.
    */
    remainder=sum*K-N*M;            //Для підрахунку "зайвих" шпалер віднімаємо площу стіни від загальної площі шпалер.
    cout<<sum<<" "<<remainder<<endl;
}

TC100:
Заводимо 4 масива, у яких будемо зберігати кількість танків кожнго стовпчика, що можуть поїхати вгору, чи вниз, та кількість танків кожного рядка, що можуть поїхати вліво, чи вправо. Спочатку кожному елементу масивів up та down присвоюємо N, а кожному елементу масивыв left і right - M. Після додавання кожного "зламаного" танку з координатами x, та y він блокує x танків, у разі руху колони вниз, або ж n-x+1 танків, у разі руху вгору. Аналогічно для руху праворуч та ліворуч. Тому в циклі ми відповідним чином оновлюємо значення наших масивів.
В кінці роботи програми сума елементів кожного з масивів показує кількість танків, які можуть поїхати вгору, вниз, ліворуч, чи праворуч. Тож нам залишається знайти максимум серед цих чотирьох сум.

Код:

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

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

int main()
{
    int n,m,k,x,y;
    int up[200],down[200],right[200],left[200];
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)right[i]=left[i]=m;
    for(int i=0;i<m;i++)down[i]=up[i]=n;
    for(int i=0;i<k;i++)
    {
        cin>>x>>y;
        up[y-1]=min(x-1,up[y-1]);
        down[y-1]=min(n-x,down[y-1]);
        left[x-1]=min(y-1,left[x-1]);
        right[x-1]=min(m-y,right[x-1]);
    }
    cout<<max(max(accumulate(up,up+m,0),accumulate(down,down+m,0)),max(accumulate(left,left+n,0),accumulate(right,right+n,0)))<<endl;
}

П.С. Зараз ще трохи покоментую код, якщо потрібно буде докладніше - пишіть.

Відредаговано Dim_ov (2011-11-17 20:18:32)

Поза форумом

 

#2 2011-11-17 18:30:37

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Розв’язки задач

Публикация одних решений без описания идей решений никакой пользы не приносит - более того - вредна!

Это проверено многолетней практикой.

Так что если хотите, чтобы вышеизложенное Вами пошло на пользу подрастающим поколениям - желательно подредактировать и дополнить в надлежащих местах соответствующими комментариями: до, во время и после решения.

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#3 2011-11-17 19:32:04

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Розв’язки задач

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

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

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#4 2011-11-17 19:37:10

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

А можете, будь ласка, докладніше розписати ідею з одним масивом в ТС100?

Поза форумом

 

#5 2011-11-17 19:44:03

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Розв’язки задач

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#6 2011-11-17 19:51:06

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

Якщо я правильно зрозумів, то Ваш масив двомірний?
Тоді у він займатиме 200*200=40000 байт пам’яті.
Тоді як у мене - 4 лінійних масива 4*sizeof(int)*200=3200 байт.

Відредаговано Dim_ov (2011-11-17 19:51:47)

Поза форумом

 

#7 2011-11-17 19:57:52

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Розв’язки задач

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

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#8 2011-11-17 20:31:09

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

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

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


І ще питання, чи потребує код ТС100 якихось коментарів, крім словесного опису?

Поза форумом

 

#9 2011-11-17 20:31:18

Andrey1998
Новий користувач
Зареєстрований: 2011-11-17
Повідомлень: 17

Re: Розв’язки задач

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

Поза форумом

 

#10 2011-11-17 20:39:53

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

Andrey1998 написав:

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

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

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

Поза форумом

 

#11 2011-11-17 20:45:32

Andrey1998
Новий користувач
Зареєстрований: 2011-11-17
Повідомлень: 17

Re: Розв’язки задач

Dim_ov написав:

Andrey1998 написав:

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

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

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

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

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

Поза форумом

 

#12 2011-11-17 20:51:10

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

Andrey1998 написав:

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

це аналогічно коду

Код:

if M mod k <> 0 then 
    sum:=M div k +1;
else
    sum:=M div k;
end;

тобто, якщо М не ділиться на К націло - ми додаємо ще один рулон. Хоча використаний він буде не повністю.

Відредаговано Dim_ov (2011-11-17 20:53:25)

Поза форумом

 

#13 2011-11-17 21:13:06

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Розв’язки задач

Dim_ov написав:

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

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

Поза форумом

 

#14 2011-11-17 21:22:06

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Розв’язки задач

Ilya Porublyov написав:

Dim_ov написав:

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

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

І я категорично підтримую!
Причина одна не потрібно копіювати - потрібно у даному випадку для кожного напрямку писати з нуля - у цьому випадку ймовірність допустити помилку значно менша.
Механічне копіювання призводить до підсвідомої впевненості у вірності свого коду, який був вірний, але за інших умов.

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

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#15 2011-11-17 22:29:15

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Розв’язки задач

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));


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

#16 2011-11-18 13:12:04

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

За проханням VIRUS’а викладаю картинку
http://dl.dropbox.com/u/29516714/Screenshot%20at%202011-11-18%2012%3A57%3A23.png

відповіддю буде добуток довжин червоних відрізків.


Як моя програма отримує ці відрізки(на прикладі ікса - для У все аналогічно):
спочатку беремо відстань між двома найвіддаленішими(по Х, ігреки ніяк не враховуємо) точками:

Код:

a=max(rt[0].x,rt[1].x)-min(lb[0].x,lb[1].x);

потім обчислюємо довжини проекцій кожного з прямокутників:

Код:

X_1=rt[0].x-lb[0].x;
X_2=rt[1].x-lb[1].x;

далі можна записати таке рівняння:

Код:

a=X_1+X_2-X_intersect;
-X_intersect=a-X_1-X_2;
X_intersect=X_1+X_2-a;

Таким чином, ми знайшли довжину перетину проекцій. Залишилось тільки перевірити, щоб ця довжина була >0. У випадку, коли це не так - потрібно обнулити змінну X_intersect, бо це означає, що проекції наших прямокутників не перетинаються.

Поза форумом

 

#17 2011-11-18 15:15:56

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Розв’язки задач

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


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

#18 2011-11-18 15:29:40

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

А сама ідея розв’язку зрозуміла?

Відредаговано Dim_ov (2011-11-18 15:29:52)

Поза форумом

 

#19 2011-11-18 15:35:44

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Розв’язки задач

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


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

#20 2011-11-18 15:40:10

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач

те-ж-саме, але без структур і докладніше розписаний пошук проекцій

Код:

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

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

int main()
{
    ll lbx[2],lby[2],rtx[2],rty[2];
    for(int i=0;i<2;i++)                        //читаємо координати, і за потреби
    {                                           //обмінюємо їх так, щоб (lbx[i];lby[i])
        cin>>lbx[i]>>lby[i]>>rtx[i]>>rty[i];    //були координатами лівого-нижнього кута і-го
        if(lbx[i]>rtx[i])swap(lbx[i],rtx[i]);   //прямокутника, а (rtx[i];rty[i]), відповідно,
        if(lby[i]>rty[i])swap(lby[i],rty[i]);   //правого.
    }
    ll a,X_1,X_2,X_intersect,b,Y_1,Y_2,Y_intersect;
    a=max(rtx[0],rtx[1])-min(lbx[0],lbx[1]);    //відстань по іксу між найвіддаленішими точками
    X_1=rtx[0]-lbx[0];                          //проекція першого прямокутника
    X_2=rtx[1]-lbx[1];                          // --//-- другого --//--
    X_intersect=X_1+X_2-a;                      //спільна частина проекцій
    if(X_intersect<0)X_intersect=0;             //обнуляємо, якщо пр-ки не перетинаються по іксу.
    b=max(rty[0],rty[1])-min(lby[0],lby[1]);
    Y_1=rty[0]-lby[0];
    Y_2=rty[1]-lby[1];
    Y_intersect=Y_1+Y_2-b;
    if(Y_intersect<0)Y_intersect=0;
    cout<<X_intersect*Y_intersect<<endl;
    return 0;
}

Відредаговано Dim_ov (2011-11-18 15:58:01)

Поза форумом

 

#21 2011-11-18 15:50:42

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Розв’язки задач

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


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

#22 2011-11-18 17:01:37

Andrey1998
Новий користувач
Зареєстрований: 2011-11-17
Повідомлень: 17

Re: Розв’язки задач

Присяжнюк А.В. написав:

Ilya Porublyov написав:

Dim_ov написав:

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

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

І я категорично підтримую!
Причина одна не потрібно копіювати - потрібно у даному випадку для кожного напрямку писати з нуля - у цьому випадку ймовірність допустити помилку значно менша.
Механічне копіювання призводить до підсвідомої впевненості у вірності свого коду, який був вірний, але за інших умов.

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

Пишіть будемо раді.

Поза форумом

 

#23 2011-11-18 17:05:54

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач

Если стороны прямоугольников параллельны осям координат (а по условию это так), а (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 баллов сработало smile  )
//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)


Вік живи - вік навчайся.

Поза форумом

 

#24 2011-11-18 17:25:14

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач

//TC100 (с одним двумерным массивом)
#include <iostream>
using namespace std;
int main()
{
    int    M,N,K,x,y;
// создаём и обнуляем массив танков (0 - значит исправный)
    bool TC[201][201]={{0,0}};
    cin >> M >> N >> K;
// обозначаем сломанные танки, как true (1)
    for (long i=1; i<=K; i++)
{
    cin >> x >> y;
    TC[y][x]=1;
}

/* rez - это итоговый результат: максимальное количество подвижных танков */
/* r - число подвижных танков в определённом направлении */
    long rez=0, r=0;

//вверх
for(int n=1; n<=N; n++)
{
    for(int m=1; m<=M; m++)
    {
        if (TC[n][m]==1)
        {
            rez=rez+m-1;
            goto a;
        }
            }
rez=rez+M;
a:;
}

//влево
for(int m=M; m>=1; m--)
{
    for(int n=1; n<=N; n++)
    {
        if (TC[n][m]==1)
        {
            r=r+n-1;
            goto b;
        }
            }
    r=r+N;
b:;
}
if (rez<r) rez=r;
r=0;

// вниз
for(int n=N; n>=1; n--)
{
    for(int m=M; m>=1; m--)
    {
        if (TC[n][m]==1)
        {
            r=r+(M-m);
            goto c;
        }
        }
    r=r+M;
c:;
}
if (rez<r) rez=r;
r=0;

// вправо
for(int m=1; m<=M; m++)
{
    for(int n=N; n>=1; n--)
    {
        if (TC[n][m]==1)
        {
            r=r+(N-n);
            goto d;
        }
        }
    r=r+N;
d:;
}
if (rez<r) rez=r;
r=0;

cout <<rez;
return 0;
}


Вік живи - вік навчайся.

Поза форумом

 

#25 2011-11-18 17:31:40

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач

// 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)


Вік живи - вік навчайся.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt