Задача с командкой олимпиады

23.09.2012, 14:18. **Показов** 813. **Ответов** 3

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

Помогите, люди знающие, бедному программисту одолеть задачу! Заранее спасибо

Однажды утром доктор Хаус проснулся в холодном поту от того, что не смог выбраться из региона, зараженного чумой. Как вы уже догадались, в своем сне
он попал на несколько столетий назад в самый центр эпидемии. Ему нужно было как можно скорее добраться до незараженного города, который расположен за
N километров от деревни, в которой он находился.

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

Доктор Хаус встретил старую женщину, которая сообщила ему, когда именно жители каждой деревни собираются начать путешествие к городу. Он понял, что,
если немного заплатить, то жители некоторой деревни смогут подвезти его до какой-нибудь другой деревни на своем пути (или до незараженного города).
Также сразу стало очевидно, что иногда выгодно доехать до некоторой деревни с одними жителями, а потом, немного отдохнув, присоединиться к другой
группе. Отметим, что доктор Хаус может присоединиться к жителям деревни, если он сам прибыл в эту деревню не позже начала движения. Также Хаус
понимал, что с его травмой ноги он не может сам пройти расстояние от одной деревни до другой.

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

InputFile
В первой строке дано целое число N (1<= N <= 5000) - число деревень на пути к городу. В следующий строке дано N целых чисел a[i]
(1<=a[i] <= 1000000) - время отправления жителей из деревни i в минутах (в начальный момент доктор Хаус находится в первой деревне в момент
времени 1).

OutputFile
В первой и единственной строке выведите два числа через пробел: минимальный момент времени, в который Хаус сможет оказаться в городе, а также
количество пересадок, которые ему потребуется сделать.

Examples

input
4
1 2 4 8
output
7 1

input
3
1 1 1
output
7 0

valeriikozlov · 24.09.2012, 21:53

очень простая задача на динамическое программирование

24.09.2012, 22:47

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

valeriikozlov · 25.09.2012, 15:58

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

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

пора значит начинать )
На языке С++ код будет такой:

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
#include <iostream>
using namespace std;
 
int main() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int N, i, j, k;
    int a[5000], b[2][5001];
    cin>>N;
    for(i=0; i<=N; i++)
    {
        cin>>a[i];
        b[0][i]=b[1][i]=2000000000;
    }
    b[0][0]=1; b[1][0]=0;
    for(i=0; i<N; i++)
    {
        if(b[0][i]<=a[i])
        {
            k=0;
            for(j=i+1; j<N; j++)
            {
                k+=j-i;
                if(a[i]+k<=a[j] && b[1][i]+1<b[1][j])
                {
                    b[0][j]=a[i]+k; b[1][j]=b[1][i]+1;
                }
            }
            k+=j-i;
            if(b[0][N]>a[i]+k)
            {
                b[0][N]=a[i]+k;
                b[1][N]=b[1][i]+1;
            }
            else
            if(b[0][N]==a[i]+k && b[0][N]>a[i]+k)
                b[0][N]=a[i]+k;
        }
    }
    cout<<b[0][N]<<" "<<b[1][N]-1<<endl;
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
YAFU@home — распределённые вычисления для математики. На CPU Programma_Boinc 20.01.2026 YAFU@home — распределённые вычисления для математики. На CPU YAFU@home — это BOINC-проект, который занимается факторизацией больших чисел и исследованием aliquot-последовательностей. Звучит. . .	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. 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. Программа предоставляет более. . .

hbq1

	Задача с командкой олимпиады 23.09.2012, 14:18. Показов 813. Ответов 3 Метки нет (Все метки) Помогите, люди знающие, бедному программисту одолеть задачу! Заранее спасибо Однажды утром доктор Хаус проснулся в холодном поту от того, что не смог выбраться из региона, зараженного чумой. Как вы уже догадались, в своем сне он попал на несколько столетий назад в самый центр эпидемии. Ему нужно было как можно скорее добраться до незараженного города, который расположен за N километров от деревни, в которой он находился. По дороге к этому городу, через каждый километр, располагаются деревни, жители которых тоже хотят уехать подальше от зараженной территории. Поэтому они собирают всех своих лошадей и в некоторый момент времени выдвигаются в сторону незараженного города. Но каждый километр пути дается им все трудней и трудней - лошади устают, и на преодоление i-го километра своего пути тратят i минут времени. Доктор Хаус встретил старую женщину, которая сообщила ему, когда именно жители каждой деревни собираются начать путешествие к городу. Он понял, что, если немного заплатить, то жители некоторой деревни смогут подвезти его до какой-нибудь другой деревни на своем пути (или до незараженного города). Также сразу стало очевидно, что иногда выгодно доехать до некоторой деревни с одними жителями, а потом, немного отдохнув, присоединиться к другой группе. Отметим, что доктор Хаус может присоединиться к жителям деревни, если он сам прибыл в эту деревню не позже начала движения. Также Хаус понимал, что с его травмой ноги он не может сам пройти расстояние от одной деревни до другой. Запутавшись в этой системе, он проснулся. Теперь его не покидает мысль, что он смог бы поспать еще, если бы нашел выход из сложившейся ситуации. Он хочет как можно быстрее добраться до незараженного города, а из всех таких возможностей, он хочет выбрать путь, который потребовал бы наименьшее количество пересадок (ему не хочется тратить деньги, так как сон только начинается). InputFile В первой строке дано целое число N (1<= N <= 5000) - число деревень на пути к городу. В следующий строке дано N целых чисел a[i] (1<=a[i] <= 1000000) - время отправления жителей из деревни i в минутах (в начальный момент доктор Хаус находится в первой деревне в момент времени 1). OutputFile В первой и единственной строке выведите два числа через пробел: минимальный момент времени, в который Хаус сможет оказаться в городе, а также количество пересадок, которые ему потребуется сделать. Examples input 4 1 2 4 8 output 7 1 input 3 1 1 1 output 7 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	24.09.2012, 21:53
	очень простая задача на динамическое программирование 0

hbq1
	24.09.2012, 22:47
	Дайте идею, любезный сенсей. А то я пока не начал программировать, не увидел всей картины - не так-то и просто.