编程介的小学生 2017-02-13 14:01 采纳率: 20.5%
浏览 889
已采纳

Energy × Delay

Description

Paul works for a big company called Abacus Computers and Maintenance (ACM). His job is to provide maintenance of computers for clients of ACM, located in different parts of the country. For this reason, Paul normally spends a good number of hours each week on flights. Obviously, Paul always takes along his laptop, so that he can work on many tasks related to his job while flying.

As batteries of laptops generally won’t last long, Paul has studied alternatives to increase the duration time of the battery during flights. He found that modern processors can operate at different frequency levels, offering a compromise between performance and energy consumption. Paul’s initial idea was to simply configure his laptop at the lowest frequency. However, he noted that it was not that useful, since tasks executed very slowly on the laptop, and there wasn’t enough time to execute all the tasks, so that the energy remaining in the battery would be unused.

Paul noted, however, that the effect of frequency levels on performances varies from one application to another, depending on whether they are limited by memory, CPU or I/O. Additionally, as modern processors permit the frequency level to be modified by software, Paul plans to use this mechanism to increase the usage time of the battery of his laptop, while still maintaining a reasonable performance. In order to consider both energy and performance, Paul decided to use a metric already well-known, called Energy × Delay Product (EDP).

Paul has a list of programs that must be executed sequentially, and all the information of time and energy needed to execute each program at each frequency level, along with the information of how much energy is spent to make processor change frequency. However, to test his new idea, Paul still has a problem: like most system administrators, he doesn’t like programming. He is asking for your help, for you are a great friend of his and an expert in algorithms and programming, to determine the frequency level at which each of his programs should be executed so as to minimize the total EDP.

Input

The input contains several test cases. The first line of a test case contains four integers F, P, E, and A, identifying respectively the number of frequency levels supported by the processor of Paul’s laptop (1 ≤ F ≤ 20), the number of programs to be executed sequentially (1 ≤ P ≤ 5000), the energy needed, in Joules, to change between any two frequency levels (1 ≤ E ≤ 100) and the time (in ms) to change between any two frequency levels (1 ≤ A ≤ 100). The frequency levels are identified by integers from 1 to F, and the programs are identified by integers from 1 to P.

The following P × F lines describe the programs, with F lines for each program (the first F lines correspond to program 1, the next F lines correspond to program 2, and so on). The f-th line corresponding to program p contains two integers Ep, f and Ap, f, representing respectively the quantity of energy (in Joules) and time (in ms) to execute program p at frequency level f (1 ≤ Ep, f ≤ 1000 and 1 ≤ Ap, f ≤ 1000). At the beginning of each test case the processor is at frequency level 1. The end of the input is indicated by F = P = E = A = 0.

Output

For each test case, your program should produce one line of output, containing the minimum EDP to execute sequentially the set of programs from 1 to P (that is, in the order they appear in the input).

Sample Input

2 3 10 10
50 120
100 90
500 600
600 500
400 1000
500 700
3 3 2 5
7 10
8 5
15 4
12 4
11 5
12 4
7 10
8 5
15 4
0 0 0 0
Sample Output

656100
145

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-02-19 15:45
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题