Сайт підготовки до олімпіади з інформатики

програмування в С++

Заняття (15.03.2017) PDF Печать E-mail
Добавил(а) Administrator   
21.03.17 10:19

Мишка і зернинки

https://www.e-olymp.com/uk/problems/15

Задача 4 «Зернинки»

Мишка збирає зернинки на шаховій дошці. Може рухатись вниз та вліво. Зібрати найбільше зернинок.

 

1

2

3

4

5

6

7

8

9

   

1

2

3

4

5

6

7

8

9

1

2

1

0

8

4

1

4

9

6

 

1

2

3

3

12

16

17

20

30

36

2

6

2

5

7

3

2

10

1

3

 

2

8

10

15

22

25

27

37

37

40

3

2

8

6

6

6

6

8

5

8

 

3

10

17

24

30

35

41

49

55

62

4

5

9

5

9

6

6

4

6

9

 

4

15

26

31

41

47

53

57

63

72

5

7

4

6

7

3

5

8

4

1

 

5

21

30

38

48

51

58

66

71

73

6

2

5

4

9

4

5

5

4

10

 

6

24

35

41

56

60

66

72

75

85

7

4

3

8

1

0

6

6

9

4

 

7

28

39

49

58

61

71

77

87

91

8

4

3

7

8

8

9

5

9

1

 

8

32

42

57

65

74

83

89

98

99

9

2

5

2

2

2

1

6

7

6

 

9

34

47

59

68

76

84

95

105

110

10

10

1

6

2

10

7

4

5

3

 

10

44

48

65

69

86

93

99

110

113

=МАКС(C3+M3;C3+N2)


Задачі 6. Купування квитків

https://www.e-olymp.com/uk/problems/799

Ім'я файлу програми:

Bilet.*

Ім'я вхідного файлу:

Bilet.dat

Ім'я вихідного файлу:

Bilet.dat

Максимальний час роботи на одному тесті:

5 секунд

Максимальна оцінка за завдання:

100 балів

За квитками на прем'єру нового мюзиклу вишикувалася черга з людей, кожний з яких хоче купити 1 квиток. На всю чергу працювала тільки одна каса, тому продаж квитків йшов дуже повільно, приводячи людей черги у відчай. Найкмітливіші швидко відмітили, що, як правило, декілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються поодинці. Тому вони запропонували декільком людям, які стоять підряд віддавати гроші першому з них, щоб він купив квитки на всіх.

Проте для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 підряд вартих людини.

Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків - Bi секунд, трьох квитків - Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли бути продані квитки для всіх людей черги.

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

Формат вхідних даних

У вхідному файлі записано спочатку число N - кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел AiBiCi. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

Формат вихідних даних

У вихідний файл виведіть одне число - мінімальний час в секундах, за яке могли бути обслужені всі покупці.

Приклади

Bilet.dat

Bilet.sol

5

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

12

2

3 4 5

1 1 1

4

N=5

i

Ai

Bi

Ci

1

5

10

15

2

2

10

15

3

5

5

5

4

20

20

1

5

20

1

1

D[i]= min ( D[i-1]+Ai,  D[i-2]+ Bi-1,  D[i-3]+ Ci-2 )

D[1]

D[2]

D[3]

D[4]

D[5]

5

7

5

6

12 - відповідь завдання

d[0]= 0;

d[1]= а[1];

d[2]= min(а[1]+a[2], b[1]);

for (i=3;i<=n;i++)  d[i]= min( d[i-1]+ а[i], min( d[i-2]+ b[i-1], d[i-3]+ c[i-2]));

 

Статистика

Пользователей : 257
Статей : 225
Просмотрено статей : 103866

Вход/Регистрация

Нет