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


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

Ви не зайшли.

#1 2011-11-17 21:30:35

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

Мої розв'язки

Дуже хочеться знайти свої помилки, але смостійно це зробити не можу, може тут хтось мені допоможе.
Calculation

Код:

#include <iostream>

using namespace std;

unsigned long long int a, b, result = 0;
short int c[18];
short int numbers = 0;

int rekuw_pow(short int number, short int power);

int main()
{
    //cout << "Input numbers: ";
    cin >> a >> b;

    for(short int i = 0; b != 0; i++, b=b/10)
    {
        c[i] = b%10;
        numbers++;
    }

    for(short int j = 0; j < numbers; j++)
    {
    //    cout << c[j];
    }
    //cout << endl;

    for(short int n = 2; n < 10; n++)
    {
        result = 0;
        //cout << "For module " << n << endl;
        for(short int i = numbers-1, j=1; i >= 0; i--, j++)
        {
            result = result + c[i] * rekuw_pow(n, numbers-j);
            //cout << c[i] * rekuw_pow(n, numbers-j) << " ";
        }
        //cout << endl;
        if(result == a)
        {
            cout //<< endl 
                << n;
            break;
        }
    }

    return 0;
}

int rekuw_pow(short int number, short int power)
{
    unsigned long long int tempNum = 1;
    for(int i = 0; i < power; i++)
    {
        tempNum = tempNum * number;
    }
    return tempNum;
}

Rec5

Код:

#include <iostream>

using namespace std;

int main()
{
    int x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6 = 0;
    //cout << "Input: ";
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> x3 >> y3 >> x4 >> y4;

    x5 = max(x1, x3); 
    y5 = min(y1, y3); 
    x6 = min(x2, x4); 
    y6 = max(y2, y4);
    if(x5 >= x6 && y5>=y6)
        cout << "0";
    else
    cout << abs (x6 - x5) *  abs (y6 - y5);
    
    return 0;
}

Wall

Код:

#include <iostream>

using namespace std;

short int N, M, K, rul = 1, ost= 0;

int main()
{
    //cout << "Input N, M, K: ";
    cin >> N >> M >> K;

    short int tempK = K;
    while(M>0)
    {
        if(tempK >= N)
        {
            tempK = tempK - N;
            M--;
        }
        if(tempK < N && tempK >= 0)
        {
            rul++;
            ost = tempK + ost;
            tempK = K - N;
            M--;
        }
        if(M == 0)
            ost = tempK + ost;
    }
    cout << rul << " " << ost;

    return 0;
}

TC100

Код:

#include <iostream>

using namespace std;

bool tanks[200][200];
short int N, M, K, MAX = 0;
short int c = 0;

int main()
{
    //cout << "Input M, N, K: ";
    cin >> M >> N >> K;

    for(short int i = 0; i < M; i++)
    {
        for(short int j = 0; j < N; j++)
            tanks[i][j] = true;
    }

    for(int i = 0; i < K; i++)
    {
        short int tempX, tempY;
    //    cout << "Input X, Y: " << i+1 << endl;
        cin >> tempX >> tempY;
        tanks[tempX-1][tempY-1] = false;
    }
///Right
    for(short int m = 0; m < M; m++)
    {
        for(short int n = 0; n < N; n++)
        {
            if(tanks[m][n] == false)
                break;
            c++;
        }
    }
    if(c > MAX)
        MAX = c;
//Left
    c = 0;
    for(short int m = 0; m < M; m++)
    {
        for(short int n = N-1; n >= 0; n--)
        {
            if(tanks[m][n] == false)
                break;
            c++;
        }
    }
    if(c > MAX)
        MAX = c;
//Up
    c = 0;
    for(short int n = 0; n < N; n++)
    {
        for(short int m = 0; m < M; m++)
        {
            if(tanks[m][n] == false)
                break;
            c++;
        }
    }
    if(c > MAX)
        MAX = c;
//Down
    c = 0;
    for(short int n = 0; n < N; n++)
    {
        for(short int m = M-1; m >= 0; m--)
        {
            if(tanks[m][n] == false)
                break;
            c++;
        }
    }
    if(c > MAX)
        MAX = c;
        
    cout << MAX;
    return 0;
}

Figure

Код:

#include <iostream>

using namespace std;

int main()
{
    unsigned int N = 1000000;
    short int a[8][8] = {0};
    short int tempA, tempB = 0;
    unsigned int max = 0;
    //cout << "Input N: ";
    cin >> N;

    for(short int i = 0; i<N; i++)
    {
        cin >> tempA >> tempB;
        a[tempA-1][tempB-1]++;
    }

    for(short int i = 0; i<8; i++)
    {
        for(short int j = 0; j<8; j++)
        {
            if(max < a[i][j])
                max = a[i][j];
        }
    }
    cout << max;
    return 0;
}

Відредаговано VIRUS (2011-11-17 22:05:34)


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

Поза форумом

 

#2 2011-11-17 21:41:19

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

Re: Мої розв'язки

По figure - відповідь не влазить у 2-х-байтовий short (діапазон - [-32768;32767], тоді як за умовою N може бути до 10^6). Із змінною max проблем немає, але перед тим, як записати відповідь у мах, ця відповідь зберігається в масиві а.

Зараз подивлюсь інші задачі.

Поза форумом

 

#3 2011-11-17 21:47:20

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

Re: Мої розв'язки

По Wall

ці умови:

Код:

if(tempK < N && tempK >= 0)
        {
            rul++;
            ost = tempK + ost;
            tempK = K - N;
            M--;
        }
        if(M == 0)
            ost = tempK + ost;

треба поміняти місцями(Якщо M уже дорівнює нулю, то немає сенсу додавати ще рулон, навіть якщо (tempK < N && tempK >= 0).)

Поза форумом

 

#4 2011-11-17 21:50:07

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

Re: Мої розв'язки

Calculation - точно переповнення. Ти знову під час обчислень використовуєш 64-бітні числа, а повертаєш функціями звичайний інт.

Можливо є й ще якісь помилки - докладно не вчитувався ще.

Відредаговано Dim_ov (2011-11-17 21:50:37)

Поза форумом

 

#5 2011-11-17 21:51:05

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

Re: Мої розв'язки

Dim_ov написав:

По figure - відповідь не влазить у 2-х-байтовий short (діапазон - [-32768;32767], тоді як за умовою N може бути до 10^6). Із змінною max проблем немає, але перед тим, як записати відповідь у мах, ця відповідь зберігається в масиві а.

Це й була засада...

А по Wall цього я не догадався.


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

Поза форумом

 

#6 2011-11-17 21:51:48

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

Re: Мої розв'язки

rec5.
Взагалі не зрозумів ідею - поясни, що має означати кожна змінна.

Поза форумом

 

#7 2011-11-17 21:54:14

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

Re: Мої розв'язки

Іще порада - чисть код від дебажного виводу і т.п. перед тим, як показувати людям - дуже важко читати

Поза форумом

 

#8 2011-11-17 21:54:20

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

Re: Мої розв'язки

Dim_ov написав:

Calculation - точно переповнення. Ти знову під час обчислень використовуєш 64-бітні числа, а повертаєш функціями звичайний інт.

Можливо є й ще якісь помилки - докладно не вчитувався ще.

Можете привести приклад, бо я щось не можу знайти.
По rec5 x5, x6, y5, y6 - координаты отриманого прямокутника.


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

Поза форумом

 

#9 2011-11-17 21:57:40

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

Re: Мої розв'язки

VIRUS написав:

Можете привести приклад, бо я щось не можу знайти.

дивись на функцію

Код:

int rekuw_pow(short int number, short int power)
{
    unsigned long long int tempNum = 1;
    for(int i = 0; i < power; i++)
    {
        tempNum = tempNum * number;
    }
    return tempNum;
}

tempNum має 64-бітний тип. Але коли ти пишеш return - перші 32 біти йдуть лісом, бо rekuw_pow() має тип int.

Поза форумом

 

#10 2011-11-17 21:59:01

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

Re: Мої розв'язки

Цього я не знав. Я не думав, що це має значення. Але тепер буду знати. До речі, коли я тестував я гадаю все влізало в 32 біти. А ось тут...

Відредаговано VIRUS (2011-11-17 21:59:59)


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

Поза форумом

 

#11 2011-11-17 22:03:08

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

Re: Мої розв'язки

по TC100 - скоріш за все, якась дрібниця:

Код:

---------- input.txt ----------
200 200 0

---------- output.txt ----------
0

коли правильна відповідь - 40000.



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

Поза форумом

 

#12 2011-11-17 22:05:48

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

Re: Мої розв'язки

Поприбирав


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

Поза форумом

 

#13 2011-11-17 22:09:29

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

Re: Мої розв'язки

Ага, здається зрозумів rec5.

Ти очікуєш, що тобі дадуть лівий-нижній та правий-верхній координати прямокутників, коли в умові нічого про це не сказано. А як говорить один із законів Мерфі - "Якщо щось може бути витлумачено кількома способами - воно буде витлумачено найбезглуздішим та найнеймовірнішим з них" smile

Не варто очікувати від вхідних даних більшого порядку, ніж той, що вказаний у ТУ.

Відредаговано Dim_ov (2011-11-17 22:12:26)

Поза форумом

 

#14 2011-11-17 22:12:09

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

Re: Мої розв'язки

У ТС100, здається, теж переповнення.

c має тип short, але за ТУ може приймати значення до 40000. А тип short, на жаль, тільки до 32767

Поза форумом

 

#15 2011-11-17 22:12:42

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

Re: Мої розв'язки

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


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

Поза форумом

 

#16 2011-11-17 22:13:53

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

Re: Мої розв'язки

Dim_ov написав:

У ТС100, здається, теж переповнення.

c має тип short, але за ТУ може приймати значення до 40000. А тип short, на жаль, тільки до 32767

треба було unsigned


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

Поза форумом

 

#17 2011-11-17 22:17:56

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

Re: Мої розв'язки

взагалі, не потрібно писати short. Це економія на сірниках. Ви збережете кілька байт пам’яті, але ціною правильної роботи програми.

Поза форумом

 

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

Unknown
Новий користувач
Зареєстрований: 2011-10-28
Повідомлень: 31

Re: Мої розв'язки

VIRUS написав:

Я орієнтувався на ТУ, чи Ві хочете сказати що там могли бути і лівий верхній і правий нижній? Якщо так, то як правльно вирішити?

Наприклад, якщо вам потрібні правий верхній у x1, y1 та лівий нижній у x2, y2, можна було перевірити:

Код:

if(x1<x2)swap(x1,x2);
if(y1<y2)swap(y1,y2);

Відредаговано Unknown (2011-11-17 22:18:54)

Поза форумом

 

#19 2011-11-17 22:18:51

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

Re: Мої розв'язки

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


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

Поза форумом

 

#20 2011-11-17 22:20:31

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

Re: Мої розв'язки

Unknown написав:

VIRUS написав:

Я орієнтувався на ТУ, чи Ві хочете сказати що там могли бути і лівий верхній і правий нижній? Якщо так, то як правльно вирішити?

Наприклад, якщо вам потрібні правий верхній у x1, y1 та лівий нижній у x2, y2, можна було перевірити:

Код:

if(x1<x2)swap(x1,x2);
if(y1<y2)swap(y1,y2);

(facepalm) а я використовував abs щоб не було від'ємних значень


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

Поза форумом

 

#21 2011-11-17 22:24:46

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

Re: Мої розв'язки

VIRUS написав:

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

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



Завтра я намалюю картинку, яка, можливо, трохи пояснить роботу моєї програми. Сьогодні я вже, мабуть іду в оффлайн

Добраніч smile

Поза форумом

 

#22 2011-11-17 22:30:38

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

Re: Мої розв'язки

Я перевіряв варіант коли один всередені іншого.


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

Поза форумом

 

#23 2011-11-18 07:24:21

Unknown
Новий користувач
Зареєстрований: 2011-10-28
Повідомлень: 31

Re: Мої розв'язки

Ось вам контрприклад для вашого коду Rec5:
27 -135 45 924 74 110 46 236
Відповідь 0.

Поза форумом

 

#24 2011-11-18 11:59:03

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

Re: Мої розв'язки

Ось ще один, який легше буде намалювати і перевірити:

Код:

0 0 7 5 5 1 10 7

http://dl.dropbox.com/u/29516714/Screenshot%20at%202011-11-18%2012%3A20%3A47.png


Червоним показано відповідь Вашої програми, а зеленим - вірна відповідь. Змінні х5, х6, у5, у6. показано пунктирними лініями

Відредаговано Dim_ov (2011-11-18 13:14:34)

Поза форумом

 

#25 2011-11-18 15:14:51

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

Re: Мої розв'язки

Вибачте а яку програму Ви використовуєте?


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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt