Блог пользователя stould

Автор stould, 12 лет назад, По-английски

Hi, more one time I need your help. Look the first example, I don't know how the answer is 656100, My best result is 682600 calculation using paper and pen.

I wanna help to UNDERSTAND the problem, my guess appear be wrong.

Paul works for a large company called Abacus Computers and Maintenance (ACM). Your job is to provide computer maintenance customer of the ACM, located in various parts of the country. For this reason, Paul is usually a good number of hours per week in airplanes. Obviously, Paul always carries his laptop, so that even when you're traveling by plane can perform many tasks related to their work.

Because laptop batteries do not usually last long, Paul has been studying ways to increase the lifetime of the battery during flight. He found that modern processors can operate at different frequency levels, offering a compromise between performance and power consumption. The initial idea was Paul just set your laptop on the lower frequency. However, he noted that it was not very useful, since the tasks performed very slowly on the laptop, and there was no time to perform all the tasks, so that the remaining battery power would be useless.

Paul noted, however, that the influence of frequency on the performance level varies from application to application, depending on whether they are limited by memory, CPU or I / O. Additionally, as modern processors allow the frequency level is changed by software, Paul plans to use this mechanism to increase the usage time of battery your laptop, so still maintaining a reasonable performance. To take into account both the energy and performance, Paul decided to use a well-known metric called Power × Time (EDP -> Energy × Delay Product).

Paul has a list of programs that should be executed sequentially, and all information on the time and energy needed to run each program at each frequency level, as well as information on how much energy is expended to change the processor frequency. However, to test his new idea, Paul still has a problem: like most system administrators, he does not like to program. He is asking for your help, since you're a great friend and an expert in algorithms and programming, to determine the level of frequency in which each of its programs should be implemented in order to minimize the total EDP.

Input: The entry contains a number of test cases. The first line of a test case contains four integers F, P, E, and A, respectively identifying the number of frequency levels supported by the processor of the laptop of Paul (1 = F = 20), the number of programs to be executed sequentially (1 = P = 5000), the necessary energy in Joules, to switch between any two levels of frequency (1 = E = 100) and time (in ms) to switch between any two levels of frequency (1 = A = 100). The frequency levels are identified by integers from 1 to F, and programs are identified by integers from 1 to P.

The F x P next lines describles the programs, with F lines for each program (the first F lines correspond to the first program, next F lines correspond to the program 2, and so on). The Fi line correspond to the program p with two numbers Ep,f e Ap,f, representing respectively the amount of energy (in Joules) and time (in ms) to run the program p on the frequency level f (1 = Ep,f = 1000 e 1 = Ap,f = 1000). At the beginning of each test case the processor is at 1 of frequency. The end of the input is indicated by F = P = E = A = 0.

Output: For each test case entry, its program to produce a line in the output containing the minimum EDP to sequentially execute the series of programs from 1 to P (in the order they appear on 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

Look my code to test the first example using the frequency 2 in both programs (max frequency):

ll f, p, e, a, tmpE, tmpJ;

struct Task{
    ll energy, time;

    Task(ll _energy, ll _time){
        energy = _energy;
        time = _time;
    }
};

ll f, p, e, a, tmpE, tmpJ;

int main(void) {
    freopen("in.in", "r", stdin);
    ios::sync_with_stdio(0);
    while((cin >> f >> p >> e >> a) && (f + p + e + a)){
        vector<Task> tasks[p + 1];
        for(int i = 0; i < p; i++){
            for(int j = 0; j < f; j++){
                cin >> tmpE >> tmpJ;
                tasks[i].push_back(Task(tmpE, tmpJ));
            }
        }
        ll ret = 0;
        for(int i = 0; i < p; i++){
            for(int j = 0; j < f; j++){
                Task tmp = tasks[i][j];
                ret += (tmp.time * (tmp.energy / f));
            }
        }
        cout << ret << "\n";
        break;
    }
    return 0;
}

Thanks so much.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

so many text

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For the first test case from sample input the optimal solution will be:

1) Run the first and the second program with the first (initial) frequency:
50 * 120 + 500 * 600 = 306,000

2) Switch to the second frequency:
10 * 10 = 100

3) Run the third program with the second frequency:
500 * 700 = 350,000

So, now, minimum EDP will be:
306,000 + 100 + 350,000 = 656,100

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, ok, I understand. Look the second test case, how the result is 145 ?! I've no idea how it output this result.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      1) Switch from the first (initial) to the second frequency:
      2 * 5 = 10

      2) Do the first program with the second frequency:
      8 * 5 = 40

      3) Do the second program with the second frequency:
      5 * 11 = 55

      4) Do the third program with the second frequency:
      8 * 5 = 40

      Minimum EDP:
      10 + 40 + 55 + 40 = 145