logo AlgoBeat OnlineJudge
登录 注册

#10298. [BalticOI 1995] taxi 出租车

内存限制:1024 MiB 时间限制:30000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: AlgoBeat 官方账号

题目描述

早期题目时限较长,卡评测直接封号。

在一条长街上,快速出租车的运行方式如下:
每相隔 1 公里设有一个停靠站。出租车从每个停靠站出发,可以连续行驶 公里而不停车。

对于这 10 种距离,分别有固定的价格,并在表中标出,例如:

距离 价格
1 12
2 21
3 31
4 40
5 49
6 58
7 69
8 79
9 90
10 101

一位乘客想要行驶 )公里。
他应选择哪些行驶距离段,才能使总费用最低?并输出最低总费用。

输入格式

输入文件包含两行:

  • 第一行有 10 个整数,分别表示行驶 公里的价格。
  • 第二行有一个整数

输出格式

输出文件,除最后一行外,每行包含两个整数:行驶距离和该段车票价格
最后一行输出整个旅程的总费用
如果有多种最优方案,输出任意一种即可。

样例

样例输入 #1

12 21 31 40 49 58 69 79 90 101
15

样例输出 #1

3 31
6 58
6 58
147

(注:样例中 ,总价