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


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

Ви не зайшли.

#26 2011-11-18 18:17:05

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

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

LVV написав:

// создаём и обнуляем массив танков (0 - значит исправный)
    bool TC[201][201]={{0,0}};

Зачем 201? По моему достаточно 200.


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

Поза форумом

 

#27 2011-11-18 18:19:14

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

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

Тому що масив нумерується з нуля, тобто 201 елементу не буде, а буде 200 (з нуля по 200)

Поза форумом

 

#28 2011-11-18 18:23:55

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

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

VIRUS написав:

LVV написав:

// создаём и обнуляем массив танков (0 - значит исправный)
    bool TC[201][201]={{0,0}};

Зачем 201? По моему достаточно 200.

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

Поза форумом

 

#29 2011-11-18 18:25:30

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

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

Unknown написав:

Тому що масив нумерується з нуля, тобто 201 елементу не буде, а буде 200 (з нуля по 200)

ні, всього буде 201 елемент smile
на проміжку [0;201) - 201 ціле число. Можете в цьому переконатися для якоїсь меншої константи(скажімо, для [0;5) - тут 5 індексів: 0, 1, 2, 3, 4).

Відредаговано Dim_ov (2011-11-18 18:26:59)

Поза форумом

 

#30 2011-11-18 18:26:59

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

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

Хоч це я знав smile


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

Поза форумом

 

#31 2011-11-18 18:38:48

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

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

Dim_ov, я не казав що "всього буде 200 елементів", я казав, що елементу з індексом 201 не буде, і це не важко зрозуміти після мого додатку у дужках..

Поза форумом

 

#32 2011-11-18 18:42:33

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

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

Unknown, тоді не зрозумів вашого кометаря.

Зауваження VIRUS’а було саме про те, що масив більшого розміру, ніж потрібно.

Поза форумом

 

#33 2011-11-18 18:42:59

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

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

/*Calculation подробное решение с
пояснениями и промежуточными выводами*/
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    setlocale (0,"");
    int a;
long long m, n,mm;
double nn, nnn;
cin >> m >> n;
/*для нахождения числа цифр в десятичной записи нужно от этого числа
вычислить десятичный логарифм и округлить в большую сторону
или добавить единицу, если логарифм - целое число.*/
nn=log10(double(abs(n)));
nnn=ceil(nn);
if (nnn==nn)
nnn=nn+1;
cout << "второе число состоит из "
    << nnn << " цифр" << endl;

// создаём массив цифр второго числа
int z[19];
for (int i=int(nnn); i>=1; i--)
{
    z[i]=long long(n)%10;
    n=n/10;
}
cout << "цифры второго числа: ";
for (int i=1; i<=nnn; i++)
cout << z[i] <<" ";

/*определяем начало просмотра диапазона
оснований системы счисления зная, что, если число nn
записано в а-ичной системе счисления, и имеет nnn цифр,
то а^(nnn-1) < nn < a^nnn    */
for (int i=2; i<10; i++)
    if (pow(i,nnn)>m){a=i;break;}
cout << endl << "первое возможное основание системы счисления: " << a << endl;


/*находим нужное основание системы счисления:
начиная с а, находим остатки от деления
десятеричного числа на j, затем частного и т.д */
int b,j,p;

for (j=a; j<10; j++)
{mm=m;
    for (p=1; p<=nnn; p++)
{
    b=int(mm%j);
   
/* если остаток b не подходит, переходим к следующему j
основанию системы счисления*/
    if (b!=z[int(nnn)-p+1])
    {
        cout << "основание " << j
            << " не подходит, так как цифры "
            << b << " во втором числе нет" << endl;   
        break;
    }
    mm=mm/j;
    }
/* если все остатки совпали, то основание найдено */
    if(p>nnn) {cout << endl <<"второе число  записано в " << j << "-(р)ичной системе счисления"<< endl;return 0;}
}

return 0;
}


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

Поза форумом

 

#34 2011-11-18 18:43:26

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

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

Virus думав, що є 201 елемент, а за умовою макс. танків 200, ось я і сказав, що якщо б був масив [200][200] його не вистачило б.

Відредаговано Unknown (2011-11-18 18:44:45)

Поза форумом

 

#35 2011-11-18 18:48:28

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

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

Масиву 200*200 цілком достатньо.
LVV, просто, зовсім не використовує 0-ві рядок та стовпчик.
Можу навіть кинути 20-бальну реалізацію однокласника, якщо цікаво

Відредаговано Dim_ov (2011-11-18 18:50:38)

Поза форумом

 

#36 2011-11-18 18:49:53

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

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

Напевно ж у випадку LVV ні..

Перечитайте його код, і тоді вже читайте коментарі.

Поза форумом

 

#37 2011-11-18 18:56:26

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

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

Годі.

Взагалі-то я пояснював VIRUS'у, чому масив у випадку LVV саме [201][201], а ви не розумієте мої пости..
Я й не запитував, чи можна по іншому, я це і так розумію.

Відредаговано Unknown (2011-11-18 18:56:36)

Поза форумом

 

#38 2011-11-18 19:18:26

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

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

// Figure
#include <iostream>
using namespace std;
int main()
{
    int n,x,y;
    cin >> n;
/* определяем и обнуляем линейный массив stat
индексы элементов которого соответствуют
координатам на доске от 11 до 88  */

long stat[89]={0};

/* наращиваем значения в ячейках массива stat,
индексы которых - это считанные с консоли
координаты, превращенные в десятичное число */

    for(long i = 1,XY; i<=n; i++)
    {
        cin >>     x >> y;
        XY=x*10+y;
        stat[XY]++;
    }
// находим максимум в stat (максимум повторений)
    int max=1;
    for (int i = 11; i < 89; i++)
if (max < stat[i]) max=stat[i];
    // выводим результат
    cout << max;
    return 0;
}

P.S. здесь (как и в ТС100) массив задан с запасом, поскольку ячейки, индексы которых содержат цифры 0 и 9 не используются. Но так проще, и это не наказуемо. smile

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


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

Поза форумом

 

#39 2011-11-18 20:13:32

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

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

Взагалі то нумерація масиву починаеться з 0 тому масив a[200] має 200 елементів від 0 до 199 це цілком зручно.

Відредаговано VIRUS (2011-11-18 20:14:55)


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

Поза форумом

 

#40 2011-11-18 20:29:04

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

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

VIRUS написав:

Взагалі то нумерація масиву починаеться з 0 тому масив a[200] має 200 елементів від 0 до 199 це цілком зручно.

Ну, мені, наприклад, зручніше рахувати не від нуля, а від одиниці (тим більше, коли це співпадає з логікою завдання). І щоб не заморочуватись, я просто не зважаю на те, що в масиві існують елементи з індексами нуль. Вважаю, що неможливість у С++ під час визначення масивів вказувати початкові значення індексів, є недоліком. Здається і в Паскалі, і в Делфі, і в ВіжуалБейсіку така можливість є.


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

Поза форумом

 

#41 2011-11-18 20:51:42

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

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

LVV написав:

і в ВіжуалБейсіку така можливість є.

Кажется там такой возможности тоже нет.

Поза форумом

 

#42 2011-11-18 23:01:28

maxtram
Новий користувач
Зареєстрований: 2007-01-12
Повідомлень: 13

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

LVV написав:

Вважаю, що неможливість у С++ під час визначення масивів вказувати початкові значення індексів, є недоліком.

Что мешает для этого написать класс?


laptop login: root
Password:
Last login: Thu Jan  1 00:00:00 UTC 1970
root@[laptop:~]# eix-sync && emerge -atuvDN world

Поза форумом

 

#43 2011-11-18 23:06:27

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

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

По моему, достаточно просто принять это. А большого минуса в этом нет так как и плюса.


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

Поза форумом

 

#44 2011-11-19 08:44:00

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

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

Unknown написав:

LVV написав:

і в ВіжуалБейсіку така можливість є.

Кажется там такой возможности тоже нет.

Да, действительно, нижний индекс массива в VisualBasic и С++ всегда равен нулю. В Паскале, он легко задаётся:
var a: array [1..200] of integer;

Наш спор безоснователен, поскольку не имеет в данном случае (задача ТС100) никакого принципиального значения. Просто это дело вкуса и привычки каждого.  Если кому-то нравится данные для первого объекта хранить в элементе массива с индексом ноль .... а для двухсотого - с индексом 199, то и "флаг ему в руки" smile.
А, если, уж очень экономно и грамотно подходить к использованию памяти при создании массива, то следовало не только использовать его нижние нулевые индексы, но и верхний индекс задавать не по максимуму, а в соответствии с текущими данными задачи, то есть ипользовать динамический массив. Например, так:
#include <iostream>
using namespace std;
int main()
{
    int N,M;
    bool **a;
    cin >> N >> M;
/*Организация двумерного динамического
массива производится в два этапа.
Сначала создаётся одномерный массив указателей*/
    a = new bool*[N];//строки
/*а затем каждому элементу этого массива
присваивается адрес одномерного массива.
Для характеристик размеров таких массивов
не требуется константных выражений.*/

for(int i=0;i<N;i++)
    a[i]= new bool[M];//столбцы
   
/*заполнять и выводить массив
можно обычными методами*/
   
    for (int n=0; n<N; n++)
        for (int m=0; m<M; m++)
            a[n][m]=0;

for (int n=0; n<N; n++){
    for (int m=0; m<M; m++)
        cout << a[n][m] << " ";
    cout << endl;
    }
return 0;
}


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

Поза форумом

 

#45 2011-11-19 08:56:02

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

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

Ты прав. В этих задачах на 2 байта больше меньше не играет роли.


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

Поза форумом

 

#46 2011-11-19 19:30:09

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

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

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

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

Не могу согласиться. Переписывание почти идентичного кода с нуля ничем не лучше, чем копирование + изменения. Обе практики - одинаково плохие и требуют отдельного тестирования каждого из повторенных блоков кода. Я бы даже сказал, что вероятность допустить ошибку при переписывании кода с нуля выше, поскольку больше объем отредактированного руками кода.

Правильным же подходом является написание кода, который не требует механического повторения (или минимизирует механическое повторение). Повторять однотипные операции - работа компьютера, а не разработчика.

LVV написав:

Если кому-то нравится данные для первого объекта хранить в элементе массива с индексом ноль .... а для двухсотого - с индексом 199, то и "флаг ему в руки" smile.

Спасибо, флаг принял smile.


"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#47 2011-11-19 21:12:41

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

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

reiten написав:

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

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

Не могу согласиться. Переписывание почти идентичного кода с нуля ничем не лучше, чем копирование + изменения. Обе практики - одинаково плохие и требуют отдельного тестирования каждого из повторенных блоков кода. Я бы даже сказал, что вероятность допустить ошибку при переписывании кода с нуля выше, поскольку больше объем отредактированного руками кода.

Правильным же подходом является написание кода, который не требует механического повторения (или минимизирует механическое повторение). Повторять однотипные операции - работа компьютера, а не разработчика.

Как с первым так и со вторым я сталкиваюсь в постоянной практике и это зависит от уровня подготовленности, и чем выше этот уровень, тем скорее наступает тот момент, что описан во второй части Вашей цитаты - с этим я согласен.

Речь же шла, что для школьников на этапе становления и роста своего уровня, нужно начинать сначала с этапа написания, и лишь после полного осознания написанного переходить к копированию, а желательно и к оптимизации кода. Хотя и в том и другом случае всё-таки остаётся место для возможных ошибок.

Да что тут спорить - достаточно просто посмотреть на статистику по этой задаче и можно придти к выводу, что, к сожалению, ошибок допущено много и многими.

P.S.: С приездом! smile

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


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

Поза форумом

 

#48 2011-11-20 07:59:56

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

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

reiten написав:

LVV написав:

Если кому-то нравится данные для первого объекта хранить в элементе массива с индексом ноль .... а для двухсотого - с индексом 199, то и "флаг ему в руки" smile.

Спасибо, флаг принял smile.

"....
Старайтесь программировать понятно. Иногда имеет смысл пожертвовать более высокой эффективностью использования памяти или процессорного времени в пользу написания более понятной программы..."
(Х.Дейтел, П.Дейтел "Как программировать на C++")  smile

Відредаговано LVV (2011-11-20 08:16:57)


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

Поза форумом

 

#49 2011-11-20 10:47:42

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

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

Але, не дивлячись на це, новачку було незрозуміло, саме чому у вас зайві елементи в масиві, а не чому масиви індексуються з нуля smile

Взагалі, казати про неможливість задавати границі індексів у С як про недолік - все одно, що називати недоліком відсутність циклів у Хаскелі.
Просто треба писати код на С, а не на Паскалі з синтаксисом С.
Хоча, олімпіадні задачі - не найкращі приклади красивого коду, тож якщо Вам так зручніше - і вам "флаг в руки". smile

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

Поза форумом

 

#50 2011-11-20 11:55:00

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

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

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


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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt