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

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

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

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

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

silent_1991 · 12.01.2011, 22:07

Хм... Странно... Скажите, например, в таком тесте ответ должен быть 7:

Code
1
2
10
1 2 3 2 5 6 2 8 9 2

?

valeriikozlov · 12.01.2011, 22:12

silent_1991, Да, ответ 7, мой код тоже выдал этот ответ.

silent_1991 · 12.01.2011, 22:14

valeriikozlov, ну это я просто пример привёл, чтобы понять, правильно ли понял задание... Вообще что-то не могу у себя найти ошибку... Всё вроде по заданию.

valeriikozlov · 12.01.2011, 22:17

silent_1991, Вот контрпример:
6
1 24 2 26 3 4
У Вас выдает 3.
А нужно 4:
1 2 3 4

@Mayonez · 12.01.2011, 22:19

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 <fstream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
   ifstream fin ("input.txt");
   ofstream fout ("output.txt");
   
    int n;
   fin >> n;
    vector <int> m; 
    for (int i = 0; i < n; i++)
    {
        int temp;
        fin >> temp;
        m.push_back(temp);
   }
 
    vector <int> a(n, 1);
    a[0] = 1;
    for (int i=1; i<n; i++)
        for (int j=0; j<i; j++)
            if (m[j] < m[i])
                if (a[j]+1 > a[i])
                    a[i] = a[j]+1;
 
    fout << *max_element (a.begin(), a.end()) << endl;
 
    return 0;
}

первый тест точно проходит

Добавлено через 1 минуту
и второй

valeriikozlov · 12.01.2011, 22:20

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

@Mayonez · 12.01.2011, 22:24

valeriikozlov, а откуда задачка? (у меня просто решение есть)

valeriikozlov · 12.01.2011, 22:25

Mayonez, отсюда: http://acmp.ru/?main=task&id_task=122
кстати у меня похожее решение, только я делал тоже самое с конца, а не с начала.

silent_1991 · 12.01.2011, 22:26

valeriikozlov, да, тут по-другому надо решать... Походу, через динамику...

valeriikozlov · 12.01.2011, 22:28

silent_1991, через динамику точно получится.

silent_1991 · 12.01.2011, 22:43

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
#include <iostream>
#include <fstream>
 
int main()
{
    std::ifstream fin("input.txt");
 
    int nums[1000];
    int lens[1000] = {0};
    int N;
 
    fin >> N;
 
    for (int i = 0; i < N; ++i)
        fin >> nums[i];
 
    fin.close();
 
    for (int i = 0; i < N; ++i)
        for (int j = i - 1; j >= 0; --j)
            if (nums[j] < nums[i] && lens[j] + 1 > lens[i])
                lens[i] = lens[j] + 1;
 
    int max_len = lens[0];
 
    for (int i = 1; i < N; ++i)
        if (max_len < lens[i])
            max_len = lens[i];
 
    std::ofstream fout("output.txt");
 
    fout << max_len + 1;
 
    return 0;
}

valeriikozlov · 12.01.2011, 22:49

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

silent_1991 · 12.01.2011, 22:51

valeriikozlov, честно говоря, пришлось чуток в код Mayonezа подсмотреть, я всё-таки в динамике ещё не очень хорошо ориентируюсь

valeriikozlov · 12.01.2011, 23:59

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

я всё-таки в динамике ещё не очень хорошо ориентируюсь

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

Добавлено через 1 час 2 минуты
Разбор задачи Максимальная подпоследовательность
Я для решения этой задачи применил такой алгоритм:
Сначало каждому числу последовательности сопоставил число 1 (эти числа в дальнейшем будут обозначать - максимальную длину возрастающей подпоследовательности начинающейся с этого числа). Т.е изначально получилось (привожу пример из задачи):
3 29 5 5 28 6
1 1 1 1 1 1 (для удобства числа этой строки назовем max_len)
Затем начинаем со второго числа с конца (в данном случае с 28) и идем к начальному числу. Для каждого числа делаем проверку так:
- перебираем все числа, которые находятся справа от проверяемого числа. Если проверяемое число оказывается меньше числа которое перебираем и max_len у проверяемого числа меньше чем max_len+1 числа которое перебираем, то max_len (проверяемого числа) делаем (max_len числа которое перебираем) + 1.
По сути мы очередное проверяемое число таким образом прикрепляем к самой длинной уже существующей подпоследовательности и эту длину сохраняем в переменной max_len для этого числа.
После такого перебора осталось только найти максимальное max_len. Это и будет результат.

silent_1991 · 13.01.2011, 08:44

Не по теме:

valeriikozlov, нет, я всё же нагло копипастить код у Mayonezа не стал, просто посмотрел одну вещь, а так разобрался, как решается задача, иначе не стал бы выкладывать код.

valeriikozlov · 13.01.2011, 18:15

Туристическое агентство
(Время: 5 сек. Память: 32 Мб Сложность: 80%)

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

Антон заметил, что некоторые планеты используются в качестве промежуточных чаще, чем другие. Он решил провести исследование – для каждой планеты A он хотел бы узнать, сколько существует пар различных планет (B,C), таких что любой путь с планеты B на планету C проходит через планету A.

Помогите Антону!
Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа: N и M – количество планет и количество рейсов космических кораблей, соответственно (2 <= N <= 20 000, 1 <= M <= 200 000). Следующие M строк описывают рейсы космических кораблей. Каждый рейс связывает две планеты, и им можно воспользоваться в любом из двух направлений. С любой планеты можно добраться до любой другой.
Выходные данные

В выходной файл OUTPUT.TXT выведите N целых чисел – для каждой планеты A выведите количество пар различных планет, таких что любой путь с одной планеты на другую проходит через A.

Пример:
INPUT.TXT
7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7
OUTPUT.TXT
18
6
6
6
6
6
6

От себя: Это очень сложная задача. Она по сложности не сравнима с предыдущими задачами. Я сам ее пытался решить применив несколько различных алгоритмов. Вся сложность была в том что бы уложиться по времени.
Я выкладываю условие этой задачи на 10 дней. Если кто-то решит ее в течении этого срока, то я обещаю что пройдусь по всем темам где этот человек писал посты и нажму ему по максимуму кнопку "спасибо" (насколько хватит ограничения сайта) (если честно, то отдал бы ему все свои очки репутации не задумываясь). По истечении 10 дней обязательно выложу свой алгоритм решения задачи (чуствую придется потрудится, порисовать, но эта задача этого заслуживает).
Условие задач попроще все равно буду стараться выкладывать и в течении этих 10 дней.

@Хохол · 13.01.2011, 19:23

Мда, O(NM) не катит.

valeriikozlov · 15.01.2011, 16:13

Сообщение от Хохол

Мда, O(NM) не катит.

точно. (но кстати вариант который я сдал на самом долгом тесте имел время 0,638 секунды).

Добавлено через 22 часа 55 минут

Сообщество роботов
(Время: 1 сек. Память: 16 Мб Сложность: 30%)

Сообщество роботов живет по следующим законам:
- один раз в начале года они объединяются в группы по три или пять роботов;
- за год группа из трех роботов собирает 5 новых, а группа из 5 роботов – 9 новых;
- роботы объединяются так, чтобы собрать за год наибольшее количество новых роботов;
- каждый робот живет ровно три года после сборки.

В начале первого года было K роботов и все они были только что собраны.

Требуется написать программу, которая найдет количество роботов в начале N-го года.
Входные данные

Входной файл INPUT.TXT содержит записанные через пробел числа K (1 <= K <= 500) и N (1 <= N <= 100).
Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно число - количество роботов в начале N-го года. Количество роботов меньше, чем 2^31.

Пример:
INPUT.TXT
3 2
OUTPUT.TXT
8

Пример:
INPUT.TXT
8 2
OUTPUT.TXT
22

Добавлено через 20 часов 38 минут
Разбор задачи Сообщество роботов.
В целом вся задача заключается в том как за год собрать наибольшее количество роботов.
Если провести небольшой анализ, то получится что нужно делать так:
- имеющееся число роботов (на данный год) разбиваем на пятерки.
- количество оставшихся роботов (не вошедших в число пятерок), делим на тройки.
- если количество оставшихся роботов после такого деления на пятерки и тройки равно нулю, то вычисляем сколько роботов было собрано в этом году этими пятерками и тройками.
- если количество оставшихся роботов после такого деления на пятерки и тройки не равно нулю, то удаляем по одной каждую пятерку (пока нам это позволяет количество пятерок) и пытаемся с имеющимися остатками роботов разбить их на тройки, что бы не было остатков роботов вообще. После этого тоже вычисляем сколько роботов было собрано в этом году этими пятерками и тройками.

@no0ker · 16.01.2011, 14:17

может быть вот так

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
 
 
int new_d(int n){
    int i,j,res=0;
    
    for(i=n/5, j=(n-5*i)/3; i>=0; i--, j=(n-5*i)/3){
        if ( i*5+j*3==n ) {
            res=i*9+j*5;
            return res;
        }
        else {
            if (res < i*9 + j*5) res = i*9 + j*5;
        };
    };
 
    return res;
}
 
 
 
main(){
    
    __int64 n;
    int year,year_end;
    int d=0, dd=0, ddd=0, dddd=0;
    
    FILE *fin,*fout;
    fin=fopen("INPUT.TXT","r");
    fout=fopen("OUTPUT.TXT","w");
    fscanf(fin,"%I64d %d",&n,&year_end);
    
    
    d=n;
    
    if(n<3 && year_end<4){
        fprintf(fout,"%d",n);
    
        fclose(fin);
        fclose(fout);
        return 0;
    }
    
    if(n<3 && year_end>4){
        fprintf(fout,"%d",0);
    
        fclose(fin);
        fclose(fout);
        return 0;
    }
    
    
    for(year=1; year<year_end; year++){
        dddd=ddd;
        ddd=dd;
        dd=d;
        d=new_d(n);
        n+=d;
        n-=dddd;
    }
    
    
    printf("%I64d",n);
    fprintf(fout,"%I64d",n);
    
    fclose(fin);
    fclose(fout);
    
}

valeriikozlov · 16.01.2011, 17:21

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

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. 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 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

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

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

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	12.01.2011, 22:12
	silent_1991, Да, ответ 7, мой код тоже выдал этот ответ. 1

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	12.01.2011, 22:14
	valeriikozlov, ну это я просто пример привёл, чтобы понять, правильно ли понял задание... Вообще что-то не могу у себя найти ошибку... Всё вроде по заданию. 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	12.01.2011, 22:17
	silent_1991, Вот контрпример: 6 1 24 2 26 3 4 У Вас выдает 3. А нужно 4: 1 2 3 4 1

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	12.01.2011, 22:20
	Mayonez, Все тесты прошел Ваш код. 1

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	12.01.2011, 22:24
	valeriikozlov, а откуда задачка? (у меня просто решение есть) 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	12.01.2011, 22:25
	Mayonez, отсюда: http://acmp.ru/?main=task&id_task=122 кстати у меня похожее решение, только я делал тоже самое с конца, а не с начала. 1

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	12.01.2011, 22:26
	valeriikozlov, да, тут по-другому надо решать... Походу, через динамику... 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	12.01.2011, 22:28
	silent_1991, через динамику точно получится. 0

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

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	12.01.2011, 22:51
	valeriikozlov, честно говоря, пришлось чуток в код Mayonezа подсмотреть, я всё-таки в динамике ещё не очень хорошо ориентируюсь 0

silent_1991
	13.01.2011, 08:44
	Не по теме: valeriikozlov, нет, я всё же нагло копипастить код у Mayonezа не стал, просто посмотрел одну вещь, а так разобрался, как решается задача, иначе не стал бы выкладывать код. 1

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	13.01.2011, 19:23
	Мда, O(NM) не катит. 0

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