Задачи для тренировки и лучшего понимания

@ForEveR · Регистрация: 24.06.2010

Author24 — интернет-сервис помощи студентам

Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо.

Список задач, решение которых присутствует в данной теме:

valeriikozlov · 17.01.2011, 22:24

asics, Я думаю что Горгона здесь могла бы получить и все 7,500000

@asics · 18.01.2011, 00:36

valeriikozlov, Вроде 3 теста прошол

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
 
int main()
{
    int a_[] = {1, 3, 2};
    std::vector<int> a(a_, a_ + sizeof(a_) / sizeof(a_[0]));
    std::vector<double> b, c;
    double res = 0.0;
    double gorg_money = 0.0, _g = gorg_money;
 
    std::sort(a.begin(), a.end());
    for(int i = 0; i < a.size(); ++i)
    {
        double tmp =  (a[i] + gorg_money) / 2;
        b.push_back((a[i] + gorg_money) / 2);
        gorg_money = tmp;
    }
 
    for(int i = 0; i < a.size(); ++i)
        c.push_back((a[i] + _g) / 2);
 
    std::cout << std::fixed << std::setprecision(6) << std::max(*std::max_element(b.begin(), b.end()), *std::max_element(c.begin(), c.end()));
    return 0;
}

Зделать з файлами или сам будеш тестить ?

valeriikozlov · 18.01.2011, 08:14

asics, Ваш код не прошел 3-ий тест. Вот еще один контрпример:
3
2 10 20
5
Должно получится 13,75
Ваш код выдает 13,375.
Все намного проще, чем Вы вычисляете.
Вот например последний контрпример:
Максимальную сумму денег Горгона наберет так:
- сначало выходит замуж и разводится с тем у кого 10. В сумме у них получается 15. После развода у Горгоны остается половина - 7,5
- затем Горгона выходит замуж и разводится с тем у кого 20. В сумме у них получается 27,5. После развода у Горгоны остается половина - 13,75

@ForEveR · 18.01.2011, 14:17 **[ТС]**

valeriikozlov, Но ведь она по сути может и со всеми выйти замуж и развестись или один в любом случае не у дел?)
То есть я это вчера видел как - сначала считаем только с одним, то есть например
2
5 10
5

Считаем как. (5+5)/2 - записываем в массив. (5+10)/2 - записываем в массив.
А затем по обоим

@asics · 18.01.2011, 15:40

valeriikozlov, А так ? Ваш контр-пример вроде прошол

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
 
int main()
{
    int a_[] = {2, 10, 20};
    std::vector<int> a(a_, a_ + sizeof(a_) / sizeof(a_[0]));
    std::vector<double> b, c;
    double res = 0.0;
    double gorg_money = 5.0, _g = gorg_money;
 
    std::sort(a.begin(), a.end());
    for(int i = 0; i < a.size(); ++i)
    {
        if(a[i] > gorg_money)
        {
            double tmp =  (a[i] + gorg_money) / 2;
            b.push_back((a[i] + gorg_money) / 2);
            gorg_money = tmp;
        }
    }
 
    for(int i = 0; i < a.size(); ++i)
        c.push_back((a[i] + _g) / 2);
 
    std::cout << std::fixed << std::setprecision(6) << std::max(*std::max_element(b.begin(), b.end()), *std::max_element(c.begin(), c.end()));
    return 0;
}

Добавлено через 30 минут
Еще бы не полохо, если бы Вы дали сылку на тестирующую систему.

valeriikozlov · 18.01.2011, 16:02

ForEveR,

Сообщение от ForEveR

Но ведь она по сути может и со всеми выйти замуж и развестись или один в любом случае не у дел?)

Она может выйти и развестись со всеми, или с некоторыми. Для нее главное добыть максимальное количество денег.

Сообщение от ForEveR

2
5 10
5

В этом случае она максимально может заработать 7,5
Изначально Горгона имеет 5.
Женится на первом и разводится нет смысла - денег неприбавится (останется то же количество).
Поэтому она женится на втором - общая сумма денег становится 15. Разводится с ним и у нее получается - 7,5
Это и есть ответ.

@ForEveR · 18.01.2011, 16:08 **[ТС]**

valeriikozlov, Ну аналогично она женится и на первом получается 5, и на втором получается 7.5. Оба ответа верны.

@no0ker · 18.01.2011, 16:25

а что означает эти 30%. если я решу три таких задачи - я стопроцентный программист что ли? =)

C

#include <stdlib.h>
#include <stdio.h>
 
 
int compare(const void *a,const void *b){
    const int * x;
    const int * y;
    x = (const int *) a;
    y = (const int *) b;
    return (*x-*y);
}
 
int main(){
 
    int *p;
    int n;
    int i=0;
    int in;
    double out;
    
    
    FILE *fin,*fout;
    fin=fopen("INPUT.TXT","r");
    fout=fopen("OUTPUT.TXT","w");
    
    fscanf(fin,"%d\n",&n);
    p=(int*)calloc(sizeof(int),n);
    
    for(i=0;i<n;i++) fscanf(fin,"%d", (p+i) ); 
    qsort(p,n,sizeof(int),compare);
    
    fscanf(fin,"\n%d",&in); 
    out=in;
    
    while( in>*(p+i) && i<n ) i++;
    
    while( i<n ){
        out = ( out + *(p+i) ) /2;
        i++;
    };
    
    printf("\n %f \n",out);
    fprintf(fout,"%f \n",out);
 
    
    fclose(fin);
    fclose(fout);
    free(p);
    return 0;
}

valeriikozlov · 18.01.2011, 16:46

asics, Ваш код дает превышение на 3-ем тесте. И я по-моему нашел почему.
Еще раз общий принцип решения задачи. Горгона может выходить замуж и разводится со всеми, с некоторыми или вообще не выходить ни за кого. Главная цель набрать как можно больше денег.
Теперь алгоритм:
- выходить и разводится с человеком у которого денег меньше чем у самой Горгоны нет смысла (только денег уменьшится)
- выходить и разводится с человеком у которого денег столько же тоже нет смысла (денег останется столько же)
- остался вариант - выходить замуж и разводится только с теми у кого больше денег. Вот тут возникает вопрос: в каком порядке выходить за них замуж и разводится чтобы получить больше денег? Этот вопрос оставляю решить Вам.
Теперь почему превышение времени на 3-ем тесте:
Скорее всего в третьем тесте все женихи имеют денег меньше чем у Горгоны. Поэтому вектор b остается пустым, а Вы для ответа пытаетесь вытащить оттуда максимальное значение и сравнить его с максимальным элементом вектора c.Задача решаема без векторов b и c. Ввели значение gorg_money и далее последовательно вычисляйте изменения этой переменной. Ее значение и выводите в ответ.

Добавлено через 1 минуту
ForEveR, Полностью согласен. Правильный ответ: 7,5

Добавлено через 5 минут
no0ker, Ваш код прошел все тесты. Правда после того как я вставил после строки:

C++

      out=in;

i=0;

asics, Забыл. Даю ссылку: http://www.acmp.ru/?main=task&id_task=174

@ForEveR · 18.01.2011, 17:08 **[ТС]**

1199553 18.01.2011 17:07:41 Юдин Кирилл Сергеевич 0174 C++ Accepted 0,046 656 Кб

C++

#include <iostream>
#include <vector>
#include <fstream>
#include <functional>
#include <algorithm>
#include <iomanip>
 
int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream ofs("output.txt");
 
    std::cin.rdbuf(ifs.rdbuf());
    std::cout.rdbuf(ofs.rdbuf());
 
    int N=0;
    int gorg=0;
    std::cin>>N;
    std::vector<int> vec;
    for(int i=0; i<N; ++i)
    {
        int t=0;
        std::cin>>t;
        vec.push_back(t);
    }
    std::cin>>gorg;
    vec.insert(vec.begin(), gorg);
    vec.erase(std::remove_if(vec.begin()+1, vec.end(), std::bind2nd(std::less_equal<int>(), gorg)), vec.end());
    std::sort(vec.begin(), vec.end());
    std::vector<double> res;
    res.push_back(*vec.begin());
    double resu=gorg;
    for(size_t i=1; i<vec.size(); ++i)
    {
        resu=(resu+vec[i])/2.0;
        res.push_back(resu);
    }
    std::cout<<std::fixed<<std::setprecision(6)<<*std::max_element(res.begin(), res.end());
    return 0;
}

@asics · 18.01.2011, 17:14

Прошло

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <fstream>
 
int main()
{
    std::ifstream ifs("INPUT.TXT");
    std::ofstream ofs("OUTPUT.TXT");
    int n = 0;
    ifs >> n;
 
    std::vector<int> a(n);
    for(int i = 0; i < n; ++i)
        ifs >> a[i];
 
    double gorg_money;
    ifs >> gorg_money;
    std::vector<double> b, c;
    double res = 0.0;
    double _g = gorg_money;
 
    std::sort(a.begin(), a.end());
    for(int i = 0; i < a.size(); ++i)
    {
        if(a[i] > gorg_money)
        {
            double tmp =  (a[i] + gorg_money) / 2;
            b.push_back((a[i] + gorg_money) / 2);
            gorg_money = tmp;
        }
    }
 
    for(int i = 0; i < a.size(); ++i)
        if(a[i] > _g)
            c.push_back((a[i] + _g) / 2);
 
    if(b.empty())
        ofs << std::fixed << std::setprecision(6) << gorg_money;
 
    else
        ofs << std::fixed << std::setprecision(6) << std::max(*std::max_element(b.begin(), b.end()), *std::max_element(c.begin(), c.end()));
    return 0;
}

@no0ker · 18.01.2011, 17:29

valeriikozlov, а я же вовремя инициализации задал значение i=0. =(

valeriikozlov · 18.01.2011, 17:42

no0ker, См. комментарии:

C

#include <stdlib.h>
#include <stdio.h>
 
 
int compare(const void *a,const void *b){
        const int * x;
        const int * y;
        x = (const int *) a;
        y = (const int *) b;
        return (*x-*y);
}
 
int main(){
 
        int *p;
        int n;
        int i=0;
        int in;
        double out;
        
        
        FILE *fin,*fout;
        fin=fopen("INPUT.TXT","r");
        fout=fopen("OUTPUT.TXT","w");
        
        fscanf(fin,"%d\n",&n);
        p=(int*)calloc(sizeof(int),n);
        
        for(i=0;i<n;i++) fscanf(fin,"%d", (p+i) ); 
        qsort(p,n,sizeof(int),compare);
        
        fscanf(fin,"\n%d",&in); 
        out=in;
        i=0;// вот здесь я и вставил эту строку, потому что без нее i==n
        
        while( in>*(p+i) && i<n ) i++;
        
        while( i<n ){
                out = ( out + *(p+i) ) /2;
                i++;
        };
        
        //printf("\n %f \n",out);
        fprintf(fout,"%f \n",out);
 
        
        fclose(fin);
        fclose(fout);
        free(p);
        return 0;
}

@no0ker · 18.01.2011, 17:59

Не по теме:

вот блин. точно. позор мне... позор... =(

valeriikozlov · 19.01.2011, 13:26

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

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

Теперь разберем последний вопрос здесь:
Если немного поразмыслить или потестировать, то приходим к выводу - все имеющиеся суммы у женихов отсортировать, а затем начиная с наименьших по значению сумм у женихов (но которые больше суммы у Гаргоны) и по возрастанию, делать так: (сумма имеющаяся у Горгоны)=((сумма имеющаяся у Горгоны)+(сумма очередного жениха))/2.
Т.е. на примере кода asics можно так:

C++

    std::sort(a.begin(), a.end());
    for(int i = 0; i < a.size(); ++i)
        if(a[i] > gorg_money)
              gorg_money=(gorg_money+a[i])/2;
std::cout << std::fixed << std::setprecision(6) << gorg_money;

valeriikozlov · 19.01.2011, 13:26

Телеграфный перевод
(Время: 1 сек. Память: 16 Мб Сложность: 29%)
Телеграфный перевод оплачивается по 7 рублей за каждую полную и неполную сотню рублей. Например, за перевод 123 рублей надо заплатить 14 рублей – 7 рублей за полную сотню и 7 рублей за 23 рубля – неполную сотню. Некто попросил переслать ему зарплату в N рублей, взяв деньги за перевод из этой зарплаты.

Требуется написать программу, которая найдет, какую максимальную сумму некто сможет получить, и сколько денег будет стоить перевод.

Входные данные
Входной файл INPUT.TXT содержит одно натуральное число N (8 ≤ N ≤ 6∙10^4).

Выходные данные
Выходной файл OUTPUT.TXT должен содержать два натуральных числа – максимальную сумму и стоимость перевода. Числа разделить одним пробелом.

Пример:
INPUT.TXT
10
OUTPUT.TXT
3 7

Пример:
INPUT.TXT
108
OUTPUT.TXT
100 7

@ForEveR · 19.01.2011, 14:14 **[ТС]**

Пример:
INPUT.TXT
108
OUTPUT.TXT
100 7

Я в ступоре. Можно как-то объяснить этот пример?
Куда 1 рубль то делся?

@asics · 19.01.2011, 14:18

ForEveR,

Сообщение от valeriikozlov

Если отсылаешь 101, то ты должен заплатить за перевод 100 рублей - 7 рублей, и еще за 1 должен тоже заплатить 7 рублей. Т.е. чтобы отправить 101 рубль, нужно заплатить еще 14 рублей. Итого нужно как минимум 115 рублей.
Есть сумма 108. Отправили 100 рублей заплатили 7 рублей, осталось 1 - которые мы не сможем никуда деть.

@no0ker · 19.01.2011, 15:58

C

#include <stdlib.h>
#include <stdio.h>
 
int main(){ 
    
    int in;
    int out=0, potr=0;
    
    FILE *fin,*fout;
    fin=fopen("INPUT.TXT","r");
    fout=fopen("OUTPUT.TXT","w");   
    fscanf(fin,"%d",&in);
    
    while(in>7){
        in -= 7;
        potr += 7;
        
        if(in>=100){
            out+=100;
            in-=100;
        }
        else{
            out+=in;
            in=0;
        };
    }
    fprintf(fout,"%d %d",out,potr);
    
        fclose(fin);
    fclose(fout);
    return 0;

valeriikozlov · 19.01.2011, 16:40

no0ker, Ваш код прошел все тесты.

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	17.01.2011, 22:24	1121
	asics, Я думаю что Горгона здесь могла бы получить и все 7,500000 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	18.01.2011, 08:14	1123
	asics, Ваш код не прошел 3-ий тест. Вот еще один контрпример: 3 2 10 20 5 Должно получится 13,75 Ваш код выдает 13,375. Все намного проще, чем Вы вычисляете. Вот например последний контрпример: Максимальную сумму денег Горгона наберет так: - сначало выходит замуж и разводится с тем у кого 10. В сумме у них получается 15. После развода у Горгоны остается половина - 7,5 - затем Горгона выходит замуж и разводится с тем у кого 20. В сумме у них получается 27,5. После развода у Горгоны остается половина - 13,75 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	18.01.2011, 14:17 [ТС]	1124
	valeriikozlov, Но ведь она по сути может и со всеми выйти замуж и развестись или один в любом случае не у дел?) То есть я это вчера видел как - сначала считаем только с одним, то есть например 2 5 10 5 Считаем как. (5+5)/2 - записываем в массив. (5+10)/2 - записываем в массив. А затем по обоим 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	18.01.2011, 16:02	1126
	ForEveR, Сообщение от ForEveR Но ведь она по сути может и со всеми выйти замуж и развестись или один в любом случае не у дел?) Она может выйти и развестись со всеми, или с некоторыми. Для нее главное добыть максимальное количество денег. Сообщение от ForEveR 2 5 10 5 В этом случае она максимально может заработать 7,5 Изначально Горгона имеет 5. Женится на первом и разводится нет смысла - денег неприбавится (останется то же количество). Поэтому она женится на втором - общая сумма денег становится 15. Разводится с ним и у нее получается - 7,5 Это и есть ответ. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	18.01.2011, 16:08 [ТС]	1127
	valeriikozlov, Ну аналогично она женится и на первом получается 5, и на втором получается 7.5. Оба ответа верны. 0

@no0ker 101 / 88 / 7 Регистрация: 17.12.2010 Сообщений: 416
	18.01.2011, 17:29	1132
	valeriikozlov, а я же вовремя инициализации задал значение i=0. =( 0

@no0ker
	18.01.2011, 17:59 #1134
	Не по теме: вот блин. точно. позор мне... позор... =( 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	19.01.2011, 13:26	1136
	Телеграфный перевод (Время: 1 сек. Память: 16 Мб Сложность: 29%) Телеграфный перевод оплачивается по 7 рублей за каждую полную и неполную сотню рублей. Например, за перевод 123 рублей надо заплатить 14 рублей – 7 рублей за полную сотню и 7 рублей за 23 рубля – неполную сотню. Некто попросил переслать ему зарплату в N рублей, взяв деньги за перевод из этой зарплаты. Требуется написать программу, которая найдет, какую максимальную сумму некто сможет получить, и сколько денег будет стоить перевод. Входные данные Входной файл INPUT.TXT содержит одно натуральное число N (8 ≤ N ≤ 6∙10^4). Выходные данные Выходной файл OUTPUT.TXT должен содержать два натуральных числа – максимальную сумму и стоимость перевода. Числа разделить одним пробелом. Пример: INPUT.TXT 10 OUTPUT.TXT 3 7 Пример: INPUT.TXT 108 OUTPUT.TXT 100 7 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	19.01.2011, 14:14 [ТС]	1137
	Пример: INPUT.TXT 108 OUTPUT.TXT 100 7 Я в ступоре. Можно как-то объяснить этот пример? Куда 1 рубль то делся? 0

@asics Freelance 2891 / 1826 / 356 Регистрация: 09.09.2010 Сообщений: 3,841
	19.01.2011, 14:18	1138
	ForEveR, Сообщение от valeriikozlov Если отсылаешь 101, то ты должен заплатить за перевод 100 рублей - 7 рублей, и еще за 1 должен тоже заплатить 7 рублей. Т.е. чтобы отправить 101 рубль, нужно заплатить еще 14 рублей. Итого нужно как минимум 115 рублей. Есть сумма 108. Отправили 100 рублей заплатили 7 рублей, осталось 1 - которые мы не сможем никуда деть. 1

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	19.01.2011, 16:40	1140
	no0ker, Ваш код прошел все тесты. 1