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

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

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

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

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

valeriikozlov · 17.01.2011, 22:24

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

@asics · 18.01.2011, 00:36

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

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
#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++
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
#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
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
43
44
45
46
47
48
49
50
#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++
1
      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++
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
#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++
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
43
44
45
#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
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
43
44
45
46
47
48
49
50
51
#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++
1
2
3
4
5
    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
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
#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, Ваш код прошел все тесты.

Новые блоги и статьи Все статьи Все блоги /
Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562

	Задачи для тренировки и лучшего понимания 15.07.2010, 05:53. Показов 501421. Ответов 1272 Метки нет (Все метки) Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо. Список задач, решение которых присутствует в данной теме: Виртуальное наследование Единственное число в массиве Работа с указателями Поменять значения переменных местами без использования дополнительной Цикл и префиксная форма инкремента Выделить смайлики из последовательности Игра "Крестики-нолики" Минимальный путь в пространстве Минимальное количество ударов для убийства Змея Горыныча Передвижение шахматной фигуры без жертв Игра "Жизнь" (Conway's Game of Life) Обойти шахматную доску фигурой "конь" без повторений Разработка функции-инкремента Жучок в программе, реализующей вывод на экран Жучок с меткой Жучок в программе, использующей ссылки Зоны видимости Жучок при использовании указателя Конструктор в структуре Жучок при выводе символа в цикле Модификация задачи о Ханойской башне Минимизировать копирование(перемещение) элементов Удаление повторяющихся чисел и сортировка минимальным количеством кода Генерация последовательности из 1 000 000 строчного латинского письма с определёнными условиями Задача о повторениях Задача о сгоревших предохранителях Задача об оптимизации собственного класса String Одновременное использование префиксного и постфиксного инкремента Написание прототипа для функции Задача на нахождение факториала числа Калькулятор для вычисления выражений вводимых пользователем Области видимости Представление арабского представления числа в римское Двоичный формат в десятичный и обратно Узнать день недели по дате Вычислить результат алгоритма в псевдокоде Найти наибольшее из двух заданных чисел без использования циклов Выявить некорректность при использовании указателей Перестановка значений трёх переменных без использования вспомагательных Умножения двух чисел без использования оператора "*" Определить язык (С или С++) Альтернативное обращение к элементу массива Расчёт и проверка контрольного ключа Описать траекторию черепахи Интерпретатор языка HQ9+ Хитрости в наследовании Синтаксис языка Си: приведения указателя к типу многомерного массива Задача на подсчёт количества итераций цикла Плавающее сравнение одних и тех же чисел на "меньше" и "больше или равно" даёт один и тот же результат На корректном тесте компилятор под intel и sparc выдают разные результаты Ферзя в угол! Головоломка Бутылки Шахматная доска Произведение цифр Максимальная подпоследовательность Сообщество роботов Свадьба Телеграфный перевод Апельсины Последняя цифра N! Задача про триграфы Почему компилятор игнорирует операцию инкрементации? 44

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

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	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 0

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

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

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

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

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