Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
#1

Как просчитать шаги от домов до магазина - C++

10.11.2012, 19:45. Просмотров 1074. Ответов 5
Метки нет (Все метки)

Готовлюсь к олимпиаде (уже будет 2 декабря) и на тренировочных курсах попалась такая задача :
Не могу понять, как просчитать шаги от домов до магазина. Может надо вычитать индексы массива?
Кто знает, пожалуйста, приведите код.

Задача C. Дома и магазины
На Новом проспекте построили подряд 10 зданий. Каждое здание может быть либо жилым
домом, либо магазином, либо офисным зданием.
Но оказалось, что жителям некоторых домов на Новом проспекте слишком далеко приходится
идти до ближайшего магазина. Для разработки плана развития общественного транспорта на
Новом проспекте мэр города попросил вас выяснить, какое же наибольшее расстояние приходится
преодолевать жителям Нового проспекта, чтобы дойти от своего дома до ближайшего магазина.

Формат входных данных
Программа получает на вход десять чисел, разделенных пробелами. Каждое число задает тип
здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0
обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом
и хотя бы один магазин.

Формат выходных данных
Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина.
Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом,
то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между
ними равно 2 и т.д.)

Пример
ввод - 2 0 1 1 0 1 0 2 1 2
вывод - 3
В примере из условия дальше всего идти до ближайшего магазина жителям четвертого дома:
ближайший к их дому магазин находится в первом доме, и им нужно пройти три дома до него.
Жителям других домов придется пройти меньшее расстояние до ближайшего магазина, поэтому
ответ 3.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2012, 19:45
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Как просчитать шаги от домов до магазина (C++):

Как просчитать число ПИ до определенного знака? - C++
Подскажите удобную формулу.

Как просчитать функцию? - Delphi
Есть например задание, нужно вывести определенное количество уровнений и условий к ним. есть система, мол x=1 если t<-b , x=t если...

Как просчитать такой НОД? - Алгебра
Как решить такого вида НОД? Курс алгебры был год назад, совершенно вылетело из головы.

Как определить исполнителей работ, и просчитать результаты? - VBA
Доброго времени суток :), Вам уважаемые форумчане. нужна помощь в решении задачи любым способом. В смысле или формулы или VBA. И так; есть...

Как просчитать кол-во строк по заданному условию? - VBA
Доброго времени суток! Возникла проблема, прошу помочь знающих решение. Мне нужно просчитать кол-во строк в стобце В, которые...

Как можно просчитать(получить) количество возможных вариантов с преставлением местами символов в строке без повторений? - Комбинаторика
Не знаю даже, сюда или не сюда написал. Но нужна помощь в составлении алгоритма(формулы). Есть строка "123456" как можно...

5
valeriikozlov
Эксперт С++
4680 / 2506 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
11.11.2012, 07:20 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int a[10][2], i, j, i_max=-1;
    for(i=0; i<10; i++)
    {
        cin>>a[i][0];
        a[i][1]=20;
    }
    for(i=0; i<10; i++)
        if(a[i][0]==2)
        {
            for(j=0; j<10; j++)
                if(a[j][0]==1 && a[j][1]>abs(i-j))
                    a[j][1]=abs(i-j);
        }
    for(i=0; i<10; i++)
        if(a[i][0]==1)
        {
            if(i_max==-1)
                i_max=i;
            else
                if(a[i][1]>a[i_max][1])
                    i_max=i;
        }
    cout<<a[i_max][1]<<endl;
 
 
    return 0;
}
1
Kandelyabr
7 / 7 / 0
Регистрация: 03.04.2012
Сообщений: 15
11.11.2012, 18:38 #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int a[10][2], i, j, i_max=-1;
    for(i=0; i<10; i++)
    {
        cin>>a[i][0];
        a[i][1]=20;
    }
    for(i=0; i<10; i++)
        if(a[i][0]==2)
        {
            for(j=0; j<10; j++)
                if(a[j][0]==1 && a[j][1]>abs(i-j))
                    a[j][1]=abs(i-j);
        }
    for(i=0; i<10; i++)
        if(a[i][0]==1)
        {
            if(i_max==-1)
                i_max=i;
            else
                if(a[i][1]>a[i_max][1])
                    i_max=i;
        }
    cout<<a[i_max][1]<<endl;
 
 
    return 0;
}
Программа составлена верно лишь в том случае, если на массиве из 10 домов 1 магазин, а в условии сказано, что хотя бы 1 магазин, соответственно при числе магазинов от одного и выше правильный результат будет выводиться для одного, последнего магазина в массиве.

Добавлено через 1 минуту
Эта программа верно считает наименьшее расстояние из наиболее отдалённых домов.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
 
int k=0, l=0, a = 10;
 
int length(int *buf1, int *buf2) {
    int n[k], m;
    for(int i=0; i<k; i++) {
        n[i] = a;
        for(int j=0; j<l; j++) {
            if(buf1[i] > buf2[j]) m = buf1[i] - buf2[j];
            else
                m = buf2[j] - buf1[i];
            if(m < n[i]) n[i] = m;
        }
    }
    m = 0;
    for(int i=0; i<k; i++) {
        if(n[i] > m) m = n[i];
    }
    return m;
}
 
int main()
{
    int a = 10, town[a], buf1[a - 1], buf2[a - 1];
    for(int i=0; i<a; i++) {
        cin >> town[i];
        if(town[i]==1) {buf1[k] = i; ++k;}
        if(town[i]==2) {buf2[l] = i; ++l;}
    }
    if(k<1) {
        cout << "Error. Number of houses k = " << k << " >= 1.\n";
        return 1;
    }
    if(l<1) {
        cout << "Error. Number of markets l = " << l << " >= 1.\n";
        return 1;
    }
    cout << length(buf1, buf2);
    return 0;
}
0
valeriikozlov
Эксперт С++
4680 / 2506 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
11.11.2012, 19:00 #4
Цитата Сообщение от Kandelyabr Посмотреть сообщение
Программа составлена верно лишь в том случае, если на массиве из 10 домов 1 магазин, а в условии сказано, что хотя бы 1 магазин, соответственно при числе магазинов от одного и выше правильный результат будет выводиться для одного, последнего магазина в массиве.
тут Вы неправы, результат учитывает абсолютно все имеющиеся магазины.
1
Kandelyabr
7 / 7 / 0
Регистрация: 03.04.2012
Сообщений: 15
11.11.2012, 19:41 #5
Прошу извинить, увидел, где ошибся с анализом, недопонял логику.
0
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
11.11.2012, 20:06  [ТС] #6
Запустил на проверку обе программы и обе прошли все 7 тестов из 7. Спасибо, разбираюсь с Вашими алгоритмами.
0
11.11.2012, 20:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2012, 20:06
Привет! Вот еще темы с ответами:

Самые первые шаги. Как сделать, чтобы заработало? - C#
Есть программа. Как сделать, чтобы она работала в MS Visual Studio ? Какой пункт выбирать при создании проекта? Там есть всякие консольные...

Просчитать убытки - MS Access
Здравствуйте! Я создаю базу данных для киоска мороженого, мне нужно просчитать убытки. У меня есть запрос на истечение срока годности и...

Упростить и просчитать - Pascal
Здравствуйте. Помогите кому не сложно сделать у этих 2 вариантов задания 3,4,5. Сам просто не очень хорошо разбираюсь сделал но там не все...

Просчитать функцию y=-3,02(x-0,2)2-3,9 в промежутке [-1;2] с шагом 0,32 - Pascal ABC
Просчитать функцию y=-3,02(x-0,2)2-3,9 в промежутке с шагом 0,32 Заранее спасибо за помощь! P.S. нужно использовать pascal ABC ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru