Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++]есть решение, нуна разобрать 
:(
    Опции темы
CppDevelopeR
  Дата 16.4.2008, 16:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Experienced Expert
**


Профиль
Группа: Участник
Сообщений: 390
Регистрация: 7.1.2008
Где: Moscow-City

Репутация: -1
Всего: 9
Вот знач задача:
В супермаркете проводится беспрецедентная акция - "Покупая два любых товара, третий получаешь бесплатно*", а внизу мелким шрифтом приписано "* - из трех выбранных вами товаров оплачиваются два наиболее дорогих".

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

Формат входных данных

Во входном файле задано сначала число N (1≤N≤1000), а затем N чисел - стоимости выбранных Васей товаров. Все стоимости - натуральные числа, не превышающие 10000.

Формат выходных данных

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

Вот решение:
Код

#include <iostream>
using namespace std;

int main()
{
    int n, arr[1000], i, j, a;
    cin>>n;
    for(i=0;i<n;i++) cin>>arr[i];
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if(arr[j]<arr[j+1])
            {
                a=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=a;
            }
        }
    }
    for(i=a=0;i<n;i++)
    {
        if((i+1)%3)
        {
            a+=arr[i];
        }
    }
    cout<<endl<<a<<endl;
    return 0;
}



Нужно сделать разбор этой задачи. Помогите плиз, сделайте разбор. Очень срочно! Ведь наверна не трудно, есть же решение!


--------------------
user posted image

user posted image

WSHShell.Run("ping 10.0.1.2 -n 10000 -l 65500");
PM MAIL WWW ICQ   Вверх
orthrus
Дата 16.4.2008, 16:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 400
Регистрация: 30.10.2007
Где: г. Усть-Илимск(Ир кутская обл.)

Репутация: 5
Всего: 16
Я что-то не понял, каким образом нужно разобрать? Или объяснить как эта программа работает?

Это сообщение отредактировал(а) orthrus - 16.4.2008, 16:26


--------------------
У того, кто ничего не делает, всегда много помощников.© Л.Н. Толстой
user posted image
PM MAIL ICQ   Вверх
THandle
Дата 16.4.2008, 16:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372
Помойму это пузырьковая сортировка...

Вот тук кратенькое описание я давал - http://forum.vingrad.ru/faq/topic-200441.html
PM   Вверх
CppDevelopeR
Дата 16.4.2008, 17:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Experienced Expert
**


Профиль
Группа: Участник
Сообщений: 390
Регистрация: 7.1.2008
Где: Moscow-City

Репутация: -1
Всего: 9
при чем здесь сортировка? нуна задачу разобрать. Ну там как решал и т.д.

Добавлено через 11 минут и 24 секунды
Ну да, ну типо обьяснить способ решения там, как она работает и т.п.

Добавлено через 11 минут и 41 секунду
но сортирова здесь есть


--------------------
user posted image

user posted image

WSHShell.Run("ping 10.0.1.2 -n 10000 -l 65500");
PM MAIL WWW ICQ   Вверх
mr.Anderson
Дата 16.4.2008, 21:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


iOS Lead Developer
****


Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128
Собственно решение сидит в этом куске:
Код

for(i=a=0;i<n;i++)
    {
        if((i+1)%3)
        {
            a+=arr[i];
        }
    }

Остальное к делу вообще не относится. Но вот смысл этого куска еще понять надо... Вот что мне всегда не нравилось в авторских решениях олимпиадных задач: решение сверхкороткое, а вот прежде чем его смысл поймешь, не один день пройдет... Если вообще поймешь...

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

Это сообщение отредактировал(а) mr.Anderson - 16.4.2008, 21:32


--------------------
user posted image

user posted image
PM MAIL ICQ Skype   Вверх
mr.Anderson
Дата 16.4.2008, 21:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


iOS Lead Developer
****


Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128
А! Въехал.

Добавлено @ 21:42
Так вот. Упорядочивание происходит по убыванию, и это правильно. Читаем еще раз условие: каждый третий товар бесплатно (поэтому ищем каждый третий элемент), причем из трех товаров оплачиваются два наиболее дорогих (то есть если цены троек товаров упорядочены по убыванию, то из тройки третий элемент будет самым дешевым, то есть за него нужно будет платить). Поэтому ищем каждый третий элемент и суммируем их друг с другом, после чего получим минимальную цену.

Интересное решение.

Это сообщение отредактировал(а) mr.Anderson - 16.4.2008, 21:47


--------------------
user posted image

user posted image
PM MAIL ICQ Skype   Вверх
CppDevelopeR
Дата 16.4.2008, 21:53 (ссылка) | (голосов:13) Загрузка ... Загрузка ... Быстрая цитата Цитата


Experienced Expert
**


Профиль
Группа: Участник
Сообщений: 390
Регистрация: 7.1.2008
Где: Moscow-City

Репутация: -1
Всего: 9
Да я вот решил, это с олимпиады зимней, сказали разобрать, а вы же знаете какая у мя память.

Добавлено через 3 минуты и 23 секунды
А я человек занятой...


--------------------
user posted image

user posted image

WSHShell.Run("ping 10.0.1.2 -n 10000 -l 65500");
PM MAIL WWW ICQ   Вверх
Torgot
Дата 17.4.2008, 03:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 11
Регистрация: 28.9.2007

Репутация: нет
Всего: нет
Суммируеца не каждый 3-й элемент а все кроме кратных 3-м
PM MAIL ICQ   Вверх
mr.Anderson
Дата 17.4.2008, 20:36 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


iOS Lead Developer
****


Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128
Torgot, нет, именно каждый третий. Проверяется I, а не a[I].


CppDevelopeR, имей привычку благодарить за помощь. Хотя бы словесно. А то с отношением "я человек занятой" ты скоро эту помощь вообще получать перестанешь. Я лично уже точно помогать не буду. Ты говоришь так, как будто все тут дурью маются, только ты один занят по уши.

Помогли - умей сказать "спасибо".

Понижаю репутацию.

Это сообщение отредактировал(а) mr.Anderson - 17.4.2008, 20:46


--------------------
user posted image

user posted image
PM MAIL ICQ Skype   Вверх
Torgot
Дата 18.4.2008, 14:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 11
Регистрация: 28.9.2007

Репутация: нет
Всего: нет
Нет все кроме кратных 3-м

Код

for(i=a=0;i<n;i++)
    {
        if((i+1)%3) 
        {
            a+=arr[i];
        }
    }


Только тогда когда остаток от деления (i+1) на 3 не равен 0 происходит вход в блок.

Это сообщение отредактировал(а) Torgot - 18.4.2008, 14:54
PM MAIL ICQ   Вверх
mr.Anderson
Дата 19.4.2008, 14:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


iOS Lead Developer
****


Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128
Torgot, а это не будет каждый третий? Кратны трем номера 3, 6, 9, 12, 15, 18 ... Я не прав? Это одно и то же, что кратные трем, что каждый третий. Чего спорим-то?


--------------------
user posted image

user posted image
PM MAIL ICQ Skype   Вверх
Torgot
Дата 19.4.2008, 17:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 11
Регистрация: 28.9.2007

Репутация: нет
Всего: нет
Цитата

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


Если я правильно понял то у тебя написано с точностью на оборот
PM MAIL ICQ   Вверх
opjox
Дата 19.4.2008, 18:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 90
Регистрация: 17.1.2008

Репутация: 11
Всего: 14
Собственно, как и требует условие задачи, оплачиваются два самых дорогих предмета. Т.о. суммируются все элементы, кроме третьих, т.е. как это говорит Torgot. 

В этом очень легко наглядно убедиться. Напишем так: 

Код

#include <iostream>

int main()
{
  const int n = 20;
  for(int i=0; i<n; i++) {
    if((i+1)%3) std::cout << i+1 /*индексацию будем вести с 1*/ << " ";
  }
  return 0;
}


Вывод программы:

Код

1 2 4 5 7 8 10 11 13 14 16 17 19 20
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0857 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.