Saudi IOI Day 4

asphalting_roads.cpp

#include <bits/stdc++.h>

#define rep(x, s, e) for (int x = int(s); x < int(e); ++x)

using namespace std;

int main() {
  int n;
  cin >> n;

  vector<bool> ashpaltedVertical(n, false);
  vector<bool> ashpaltedHorizontal(n, false);

  rep(i, 0, n * n) {
    int h, v;
    cin >> h >> v;
    h--, v--;
    if (!ashpaltedVertical[v] && !ashpaltedHorizontal[h]) {
      // We need to do work
      cout << i + 1 << " ";
      ashpaltedVertical[v] = ashpaltedHorizontal[h] = true;
    }
  }

  cout << endl;

  return 0;
}

dzy_loves_strings.cpp

#include <bits/stdc++.h>

#define rep(x, s, e) for (int x = int(s); x < int(e); ++x)

using namespace std;

int main() {
  string s;
  int k;
  cin >> s >> k;

  int maxValue = 0;
  map<char, int> value;
  for (char c = 'a'; c <= 'z'; ++c) {
    cin >> value[c];
    maxValue = max(maxValue, value[c]);
  }

  int score = 0;
  rep(i, 0, s.size()) {
    // Calculate value of s
    score += (i + 1) * value[s[i]];
  }

  rep(i, 0, k) {
    // Add k of the most valuable letter to the end
    score += (s.size() + i + 1) * maxValue;
  }

  cout << score << endl;

  return 0;
}

filename.cpp

#include <bits/stdc++.h>

#define rep(x, s, e) for (int x = int(s); x < int(e); ++x)

using namespace std;

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  int ret = 0;

  // Detect groups of xs
  char prev = -1;
  int xs = 0;
  for (char c : s) {
    if (c != prev) {
      if (xs >= 3) {
        ret += xs - 2;
      }
      xs = 0;
    }

    prev = c;
    if (c == 'x') xs++;
  }

  // Make sure we catch a group of xs right at the end
  if (xs >= 3) {
    ret += xs - 2;
  }

  cout << ret << endl;

  return 0;
}

find_divisible.cpp

#include <bits/stdc++.h>

#define rep(x, s, e) for (int x = int(s); x < int(e); ++x)

using namespace std;

int main() {
  int t;
  cin >> t;
  rep(test, 0, t) {
    int l, r;
    cin >> l >> r;

    rep(num, l, r) {
      if (num * 2 <= r) {
        cout << num << " " << num * 2 << endl;
        break;
      }
    }
  }
  return 0;
}

perfect_number.cpp

#include <bits/stdc++.h>

#define rep(x, s, e) for (int x = int(s); x < int(e); ++x)

using namespace std;

bool isPerfect(int x) {
  int sum = 0;
  while (x > 0) {
    sum += x % 10;
    x /= 10;
  }
  return sum == 10;
}

int main() {
  int k;
  cin >> k;

  int found = 0;
  int x = 1;
  while (true) {
    if (isPerfect(x)) {
      found++;
    }
    if (found == k) {
      cout << x;
      break;
    }

    x++;
  }

  return 0;
}

supermarket.cpp

#include <bits/stdc++.h>

#define rep(x, s, e) for (int x = int(s); x < int(e); ++x)

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  double bestPrice = 1e18;
  rep(i, 0, n) {
    double a, b;
    cin >> a >> b;
    bestPrice = min(bestPrice, a / b);
  }

  cout << fixed << setprecision(12) << m * bestPrice << endl;

  return 0;
}