crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

2 страниц V   1 2 >  
Ответить в данную темуНачать новую тему
> Вода между стен, забавный тест от программистов твиттера
Iron Bug
  опции профиля:
сообщение 7.5.2014, 21:46
Сообщение #1


Профессионал
*****

Группа: Модератор
Сообщений: 1587
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


Попалась тут забавная задачка :)
Задача:
http://qandwhat.apps.runkite.com/i-failed-...tter-interview/
Дя тех, кто не очень хорошо понимает по-английски, задача вкратце:
Представлен последовательный набор чисел. Числа указывают "высоту стен", стоящих рядом. Задача: посчитать количество воды, которая может накопиться в таком резервуаре, если пройдёт дождь. Вода через низкие препятствия утекает, как и полагается воде. С краёв она тоже утекает.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ilyabvt
  опции профиля:
сообщение 8.5.2014, 20:13
Сообщение #2


Активный участник
***

Группа: Участник
Сообщений: 297
Регистрация: 23.6.2011
Пользователь №: 2765

Спасибо сказали: 45 раз(а)




Репутация:   3  


Решил так:
Раскрывающийся текст
int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }
//    if (left == right) { return 0; }

    level = std::min(x[left], x[right]);

    for (int i=left; i<right; ++i) {
        if (level-x[i] > 0) { result += level-x[i]; }
    }

    return result;
}


Сообщение отредактировал ilyabvt - 8.5.2014, 20:39
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 8.5.2014, 20:28
Сообщение #3


Профессионал
*****

Группа: Модератор
Сообщений: 1587
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


а как насчёт последовательностей типа { 3, 1, 2, 1, 3, 1, 2, 1, 3 } ?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ilyabvt
  опции профиля:
сообщение 8.5.2014, 20:40
Сообщение #4


Активный участник
***

Группа: Участник
Сообщений: 297
Регистрация: 23.6.2011
Пользователь №: 2765

Спасибо сказали: 45 раз(а)




Репутация:   3  


Цитата
а как насчёт последовательностей типа { 3, 1, 2, 1, 3, 1, 2, 1, 3 } ?

Возвращает 10. Т.е. правильно обрабатывает.
P.S. Убрал в коде избыточную проверку.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 12.5.2014, 8:11
Сообщение #5


фрилансер
******

Группа: Участник
Сообщений: 2886
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


просканировать стенки, начиная снизу, интегрировать заметаемые закрытые с боков области на каждом шаге )

(не тестировал, мне лень :D , тут только алгоритм)

Раскрывающийся текст
    {
        //блоки для каждой координаты X
        std::vector<int> wall;
        int volume=0;

        //тестовые значения
        wall.push_back(3);
        wall.push_back(1);
        wall.push_back(2);
        wall.push_back(5);

        if(wall.size())
        {
            //найдём максимальный и минимальный уровень
            int min_level=0;
            int max_level=0;
            {
                std::vector<int> mm=wall;
                std::sort(mm.begin(),mm.end());
                min_level=*mm.begin();
                max_level=*mm.rbegin();
            }

            if(min_level>=1 && max_level>min_level)
            {
                //сканируем уровни, начиная снизу
                for(int level=min_level;level<=max_level;level++)
                {
                    //на текущем слева направо:
                    
                    //ищем первую стенку
                    int x1=0;
                    for(; x1!=wall.size(); x1++)
                    {
                        if(wall[x1]>=level)break;
                    }

                    //ищем последнюю стенку
                    int x2=wall.size()-1;
                    for(; x2>x1+1; x2--)
                    {
                        if(wall[x2]>=level)break;
                    }

                    //между стенами должен быть хотя бы 1 блок
                    if(x1+1<x2)
                    {
                        //сканируем пространство между x1 и x2 и считаем пустоту
                        for(int x=x1+1; x<x2-1; x++)
                        {
                            if(wall[x]<level)volume++;
                        }
                    }
                }
            }
        }

        //volume - результат
    }


Сообщение отредактировал Алексей1153 - 18.5.2014, 11:13
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 15.5.2014, 20:58
Сообщение #6


Профессионал
*****

Группа: Модератор
Сообщений: 1587
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


Цитата(ilyabvt @ 8.5.2014, 23:40) *
Цитата
а как насчёт последовательностей типа { 3, 1, 2, 1, 3, 1, 2, 1, 3 } ?

Возвращает 10. Т.е. правильно обрабатывает.
P.S. Убрал в коде избыточную проверку.

а для { 3, 1, 2, 1, 4, 1, 2, 1, 4 } неправильно считает.


Цитата(Алексей1153 @ 12.5.2014, 11:11) *
просканировать стенки, начиная снизу, интегрировать заметаемые закрытые с боков области на каждом шаге )

я также решила: только я на каждом уровне строила интегральные столбики с "весами", схлапывая уже "заполненные" уровни.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 15.5.2014, 22:24
Сообщение #7


Профессионал
*****

Группа: Модератор
Сообщений: 1587
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


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

Раскрывающийся текст
#include <iostream>
#include <vector>

using namespace std;

typedef struct _data
{
    int level;
    int weight;
    _data(int h,int w) : level(h), weight(w) {}
}
data;

int calcVolume(int count, int *x)
{

    if (count<3) return 0;

    vector<data> v;
    int x_min = x[0];
    int current_level = x[0];
    int current_weight = 1;

    for(int i=1;i<count;i++)
    {
        if(x[i]<x_min) x_min = x[i];
        if(x[i]!=current_level)
        {
            v.push_back(data(current_level,current_weight));
            current_level = x[i];
            current_weight = 1;
        }
        else
        {
            current_weight++;
        }
     }
     v.push_back(data(current_level,current_weight));

    size_t size = v.size();
    for(size_t i=0; i<size; i++)
    {
        v[i].level-=x_min;
    }

    int volume = 0;
    vector<data> v_new;

    while(size>2)
    {
        for(size_t i=0; i<size; i++)
        {
            cout << v[i].level << "(" << v[i].weight << "), ";
        }
        cout << endl;

        current_level = v[0].level;
        current_weight = v[0].weight;
        for(size_t i=1; i<size; i++)
        {
            if(i != size-1)
            {
                if((v[i].level==0)&&(v[i-1].level>0)&&(v[i+1].level>0))
                {
                    volume += v[i].weight;
                    v[i].level += 1;
                }
            }
            if(v[i].level != current_level)
            {
                v_new.push_back(data(current_level-1,current_weight));
                current_level = v[i].level;
                current_weight = v[i].weight;
            }
            else
            {
                current_weight += v[i].weight;
            }
        }
        if(current_level>0)
        {
              v_new.push_back(data(current_level-1,current_weight));
        }
        v = v_new;
        size = v.size();
        v_new.clear();
    }
    return volume;
}

int main()
{
    int x[] = { 3, 1, 2, 1, 4, 1, 2, 1, 4 };
    cout << "Volume is " << calcVolume(sizeof(x)/sizeof(int),x) << endl;
    return 0;
}


Сообщение отредактировал Iron Bug - 16.5.2014, 18:16
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Влад
  опции профиля:
сообщение 16.5.2014, 12:14
Сообщение #8


Участник
**

Группа: Участник
Сообщений: 146
Регистрация: 20.3.2009
Из: Санкт-Петербург
Пользователь №: 627

Спасибо сказали: 46 раз(а)




Репутация:   8  


Коллеги, а вы обратили внимание, что в точном соответствии с буквой оригинального условия задачи "высота" стенок может быть и отрицательной? Почему бы не протестировать и на последовательностях вида { 3, -1, -2, 8, -3, -1, 2, 0, -3 } ?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 16.5.2014, 17:16
Сообщение #9


Профессионал
*****

Группа: Модератор
Сообщений: 1587
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


Цитата(Влад @ 16.5.2014, 15:14) *
Коллеги, а вы обратили внимание, что в точном соответствии с буквой оригинального условия задачи "высота" стенок может быть и отрицательной? Почему бы не протестировать и на последовательностях вида { 3, -1, -2, 8, -3, -1, 2, 0, -3 } ?

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

поправила мелкий косячок в своём коде. а так, он и с отрицательными значениями работает: потому что всё равно сначала "выравнивает" минимальные значения на ноль.

на самом деле, можно ещё оптимизировать маленько, сразу отрезав "скаты" по краям:
Раскрывающийся текст
#include <iostream>
#include <vector>

using namespace std;

typedef struct _data
{
    int level;
    int weight;
    _data(int h,int w) : level(h), weight(w) {}
}
data;

int calcVolume(int count, int *x)
{

    if (count<3) return 0;

    int start = count-1;
    for(int i=0;i<count-1; i++)
    {
        if(x[i]>x[i+1])
        {
            start = i;
            break;
        }
    }
    int stop = 0;
    for(int i=count-1;i>0; i--)
    {
        if(x[i]>x[i-1])
        {
            stop = i;
            break;
        }
    }

    vector<data> v;
    int x_min = x[start];
    int current_level = x[start];
    int current_weight = 1;

    for(int i=start;i<=stop;i++)
    {
        if(x[i]<x_min) x_min = x[i];
        if(x[i]!=current_level)
        {
            v.push_back(data(current_level,current_weight));
            current_level = x[i];
            current_weight = 1;
        }
        else
        {
            current_weight++;
        }
     }
     v.push_back(data(current_level,current_weight));

    size_t size = v.size();
    for(size_t i=0; i<size; i++)
    {
        v[i].level-=x_min;
    }

    int volume = 0;
    vector<data> v_new;

    while(size>2)
    {
        for(size_t i=0; i<size; i++)
        {
            cout << v[i].level << "(" << v[i].weight << "), ";
        }
        cout << endl;

        current_level = v[0].level;
        current_weight = v[0].weight;
        for(size_t i=1; i<size; i++)
        {
            if(i != size-1)
            {
                if((v[i].level==0)&&(v[i-1].level>0)&&(v[i+1].level>0))
                {
                    volume += v[i].weight;
                    v[i].level += 1;
                }
            }
            if(v[i].level != current_level)
            {
                if(current_level>0)
                {
                    v_new.push_back(data(current_level-1,current_weight));
                }
                current_level = v[i].level;
                current_weight = v[i].weight;
            }
            else
            {
                current_weight += v[i].weight;
            }
        }
        if(current_level>0)
        {
            v_new.push_back(data(current_level-1,current_weight));
        }
        v = v_new;
        size = v.size();
        v_new.clear();
    }
    return volume;
}

int main()
{
    int x[] = {   3, -1, -2, 8, -3, -1, 2, 0, -3  };
    cout << "Volume is " << calcVolume(sizeof(x)/sizeof(int),x) << endl;
    return 0;
}



update: ещё маленько добавила проверку - для пущей оптимальности.

Сообщение отредактировал Iron Bug - 19.5.2014, 19:53
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 18.5.2014, 11:28
Сообщение #10


фрилансер
******

Группа: Участник
Сообщений: 2886
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


я щас глянул - исправил у себя явный глюк - вместо "x2--" было "x2++"

Iron Bug, а вчера абсолютно внезапно посетил твой город :D Симпатичный город. Но равнина (это я о ландшафте) непривычная, конечно, для глаза
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

2 страниц V   1 2 >
Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 14.10.2019, 6:40