crossplatform.ru

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

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


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

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

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




Репутация:   12  


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


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

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

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




Репутация:   3  


Цитата(Iron Bug @ 19.5.2014, 23:07) *
Цитата(ilyabvt @ 18.5.2014, 21:40) *
Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 } :)
я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.

Обновил еще :)
На этот раз тоже проверял на случайных последовательностях.
Раскрывающийся текст
int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, middle, 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; }
    }

    while (left < right) {
        for (middle=left+1;  middle < right;  ++middle) {
            if (x[middle] > x[middle-1]  &&  x[middle+1] <= x[middle]) {
                bool needbreakCycle = true;
                for (int i=middle+1; i<=right; ++i) {
                    if (x[i] > x[middle]  &&  x[middle] <= x[left]) {
                        middle = i-1;       //-1 т.к. на каждой итерации ++middle
                        needbreakCycle = false;
                        break;
                    }
                }
                if (needbreakCycle) { break; }
            }
        }
        level = std::min(x[left], x[middle]);   //min на случай middle==right
        for (int i=left; i<middle; ++i) {
            if (level-x[i] > 0) { result += level-x[i]; }
        }
        left = middle;
    }

    return result;
}


Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Сообщений в этой теме
- Iron Bug   Вода между стен   7.5.2014, 21:46
- - ilyabvt   Решил так: Раскрывающийся текстint calcWaterVolume...   8.5.2014, 20:13
- - Iron Bug   а как насчёт последовательностей типа { 3, 1, 2, 1...   8.5.2014, 20:28
- - ilyabvt   Цитатаа как насчёт последовательностей типа { 3, 1...   8.5.2014, 20:40
|- - Iron Bug   Цитата(ilyabvt @ 8.5.2014, 23:40) Цитатаа...   15.5.2014, 20:58
- - Алексей1153   просканировать стенки, начиная снизу, интегрироват...   12.5.2014, 8:11
- - Iron Bug   у меня идея в том, чтобы "срезать" нижни...   15.5.2014, 22:24
- - Влад   Коллеги, а вы обратили внимание, что в точном соот...   16.5.2014, 12:14
|- - Iron Bug   Цитата(Влад @ 16.5.2014, 15:14) Коллеги, ...   16.5.2014, 17:16
- - Алексей1153   я щас глянул - исправил у себя явный глюк - вместо...   18.5.2014, 11:28
|- - Iron Bug   Цитата(Алексей1153 @ 18.5.2014, 14:28) Ir...   19.5.2014, 19:31
- - ilyabvt   Цитатаа для { 3, 1, 2, 1, 4, 1, 2, 1, 4 } неправил...   18.5.2014, 18:40
|- - Iron Bug   Цитата(ilyabvt @ 18.5.2014, 21:40) Обнови...   19.5.2014, 20:07
- - Алексей1153   Iron Bug, наверное, в самом городе из-за зданий не...   20.5.2014, 6:53
- - Алексей1153   ещё оптимизация для муравья - ему не обязательно с...   20.5.2014, 7:47
- - ilyabvt   Цитата(Iron Bug @ 19.5.2014, 23:07) Цитат...   20.5.2014, 18:24


Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


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




RSS Текстовая версия Сейчас: 29.3.2024, 11:44