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

@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, Ваш код прошел все тесты.

Новые блоги и статьи Все статьи Все блоги /
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .	[golang] Worker Pool alhaos 09.06.2026 Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .	Свет внутри себя kumehtar 07.06.2026 Пусть это будет здесь lIs4oanZS9Y	Программа для com-порта Uhbif79 05.06.2026 Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .	Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .

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

	Задачи для тренировки и лучшего понимания 15.07.2010, 05:53. Показов 513072. Ответов 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