oj.uz

Submission #12097

# Submission time Handle Problem Language Result Execution time Memory
12097 2014-12-21T05:43:31 Z ainu7 Min-cost GCD (GA9_mcg) C++
57 / 100
 725 ms 1720 KB 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

struct state {
  long long a, b, cost;
  state(long long _a, long long _b, long long _cost) {
    cost = _cost;
    a = _a;
    b = _b;
  };
  bool operator < (const state & another) const {
    if (cost != another.cost) return cost < another.cost;
    if (a != another.a) return a < another.a;
    return b < another.b;
  }
};

int main()
{
  int T;
  cin >> T;
  for (int i=0; i<T; i++) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    set<state> S;
    S.insert(state(a, b, 0));
    long long res = 1LL<<62;

    long long c1 = 0, c2 = 0;
    if (a > b) c2 = 1LL<<62;
    if (a < b) c1 = p, swap(a, b);

    while (b) {
      long long c = a / b;
      long long d = a % b;
      long long d1 = c1+p;
      long long d2 = 1LL<<62;
      if (1.0*c*q < (1LL<<61))
        d2 = min(d2, c1+c*q);
      if (1.0*c*q < (1LL<<61))
        d1 = min(d1, c2+c*q);

      d1 = min(d1, d2+p);

      a = b;
      b = d;
      c1 = d1;
      c2 = d2;
    }
    cout << min(c1, c2) << endl;
  }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1720 KB Output is correct
2 Correct 0 ms 1720 KB Output is correct
3 Correct 0 ms 1720 KB Output is correct
4 Correct 1 ms 1720 KB Output is correct
5 Correct 0 ms 1720 KB Output is correct
6 Correct 0 ms 1720 KB Output is correct
7 Correct 1 ms 1720 KB Output is correct
8 Correct 0 ms 1720 KB Output is correct
9 Correct 0 ms 1720 KB Output is correct
10 Correct 0 ms 1720 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 1720 KB Output is correct
2 Correct 451 ms 1720 KB Output is correct
3 Correct 416 ms 1720 KB Output is correct
4 Correct 448 ms 1720 KB Output is correct
5 Correct 435 ms 1720 KB Output is correct
6 Correct 418 ms 1720 KB Output is correct
7 Correct 408 ms 1720 KB Output is correct
8 Correct 408 ms 1720 KB Output is correct
9 Correct 383 ms 1720 KB Output is correct
10 Correct 416 ms 1720 KB Output is correct
11 Correct 458 ms 1720 KB Output is correct
12 Correct 443 ms 1720 KB Output is correct
13 Correct 393 ms 1720 KB Output is correct
14 Correct 0 ms 1720 KB Output is correct
15 Correct 8 ms 1720 KB Output is correct
16 Correct 0 ms 1720 KB Output is correct
17 Correct 10 ms 1720 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1720 KB Output is correct
2 Correct 6 ms 1720 KB Output is correct
3 Correct 0 ms 1720 KB Output is correct
4 Correct 0 ms 1720 KB Output is correct
5 Correct 2 ms 1720 KB Output is correct
6 Correct 6 ms 1720 KB Output is correct
7 Correct 0 ms 1720 KB Output is correct
8 Correct 6 ms 1720 KB Output is correct
9 Correct 3 ms 1720 KB Output is correct
10 Correct 0 ms 1720 KB Output is correct
11 Correct 8 ms 1720 KB Output is correct
12 Correct 2 ms 1720 KB Output is correct
13 Correct 0 ms 1720 KB Output is correct
14 Correct 0 ms 1720 KB Output is correct
15 Correct 0 ms 1720 KB Output is correct
16 Correct 0 ms 1720 KB Output is correct
17 Correct 0 ms 1720 KB Output is correct
18 Correct 0 ms 1720 KB Output is correct
19 Correct 0 ms 1720 KB Output is correct
20 Correct 0 ms 1720 KB Output is correct
21 Correct 6 ms 1720 KB Output is correct
22 Correct 0 ms 1720 KB Output is correct
23 Correct 0 ms 1720 KB Output is correct
24 Correct 0 ms 1720 KB Output is correct
25 Correct 11 ms 1720 KB Output is correct
26 Correct 8 ms 1720 KB Output is correct
27 Correct 8 ms 1720 KB Output is correct
28 Correct 7 ms 1720 KB Output is correct
29 Correct 4 ms 1720 KB Output is correct
30 Correct 4 ms 1720 KB Output is correct
31 Correct 0 ms 1720 KB Output is correct

Subtask #4
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 1720 KB Output is correct
2 Correct 599 ms 1720 KB Output is correct
3 Correct 709 ms 1720 KB Output is correct
4 Correct 697 ms 1720 KB Output is correct
5 Correct 643 ms 1720 KB Output is correct
6 Correct 693 ms 1720 KB Output is correct
7 Correct 638 ms 1720 KB Output is correct
8 Correct 692 ms 1720 KB Output is correct
9 Correct 678 ms 1720 KB Output is correct
10 Correct 717 ms 1720 KB Output is correct
11 Correct 650 ms 1720 KB Output is correct
12 Correct 651 ms 1720 KB Output is correct
13 Incorrect 656 ms 1720 KB Output isn't correct - wrong output format : File not found: "/var/www/temp/12097/outputRpJ4_1"
14 Halted 0 ms 0 KB -
15 Correct 665 ms 1720 KB Output is correct
16 Correct 568 ms 1720 KB Output is correct
17 Correct 581 ms 1720 KB Output is correct
18 Correct 707 ms 1720 KB Output is correct
19 Correct 543 ms 1720 KB Output is correct
20 Correct 537 ms 1720 KB Output is correct
21 Correct 576 ms 1720 KB Output is correct
22 Correct 556 ms 1720 KB Output is correct
23 Correct 572 ms 1720 KB Output is correct
24 Correct 614 ms 1720 KB Output is correct
25 Correct 569 ms 1720 KB Output is correct
26 Correct 603 ms 1720 KB Output is correct
27 Correct 593 ms 1720 KB Output is correct
28 Correct 637 ms 1720 KB Output is correct
29 Correct 587 ms 1720 KB Output is correct
30 Correct 725 ms 1720 KB Output is correct
31 Correct 624 ms 1720 KB Output is correct
32 Correct 658 ms 1720 KB Output is correct
33 Correct 591 ms 1720 KB Output is correct
34 Correct 612 ms 1720 KB Output is correct
35 Correct 606 ms 1720 KB Output is correct