Решение задачи А 2 квалификационного раунда Russian Code Cup 2015 на С++


Турникеты в метро

Вася и Петя каждый день ездят на метро, поэтому они решили купить себе проездные карты, чтобы каждый раз не покупать жетон. Каждая карта может использоваться в течение определенного количества дней, после чего она становится неактивной.

При каждом проходе через турникет высвечивается, сколько еще дней карта может быть использована (включая текущий день). Но, к сожалению, табло, на котором это количество дней отображается, может показывать только однозначные и двузначные числа. Если же в отображаемом числе хотя бы три цифры, на табло покажется число 99. Например, если на карте осталось 5 дней, то на турникете покажется число 5, если 12 дней, то число 12, а если 123 дня, то на турникете покажется число 99. Если на карте остается 0 дней, она становится неактивной и по ней больше нельзя проходить через турникет.

Сейчас у Васи на карте осталось a дней, а у Пети — b. Они каждый день ездят на метро и каждый день смотрят на числа, которые отображаются на турникете. И им стало интересно: через сколько дней в первый раз число на турникете у одного из них будет ровно в k раз больше, чем число на турникете у другого. Помогите друзьям выяснить ответ на этот вопрос.

Формат входных данных

Первая строка входных данных содержит одно число t (1 ≤ t ≤ 100000) — количество тестов. Следующие t строк содержат по тесту каждая. Каждый тест задается тремя целыми числами: a, b, k (1 ≤ a, b ≤ 2·109, 1 ≤ k ≤ 100) — количество оставшихся дней на карточках у Васи и Пети и требуемое отношение.

Формат выходных данных

Для каждого набора данных выведите единственное число: через сколько дней у одного из друзей на турникете будет показано в k раз больше поездок, чем у другого. Если такого не произойдет до того дня, когда у одного из друзей карта станет неактивной, выведите «-1».

Примеры

Входные данные

5
2 1 2
100 99 2
17 13 10
3 3 1
1 1 2

Выходные данные

0
98
-1
0
-1
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int TMAX = 99; //максимально возможное число на турникете

int tablo(int number){
  return min(TMAX, number);
}

int main(){
  int T;
  cin >> T;
  string line;
  getline(cin, line);
  int pos1;
  int pos2;
  int a, b, k;
  int mn, mx; //мин. и макс. числа на турникете в какой-либо день
  int days;
  int at, bt; //числа на турникете
  int minab;
  for (int i = 1; i <= T; i++)
  {
    days = 0;
    getline(cin, line);
    pos1 = line.find(" ");
    a = atoi(line.substr(0, pos1).c_str());
    pos2 = line.find(" ", pos1 + 1);
    b = atoi(line.substr(pos1 + 1, pos2 - pos1).c_str());
    k = atoi(line.substr(pos2 + 1).c_str());
    if (k == 100){
      cout << -1 << endl;
      continue;
    }
    while ((a > 0) && (b > 0)){
      at = tablo(a);
      bt = tablo(b);
      mn = min(at, bt);
      mx = max(at, bt);
      if (((mx / mn) == k) && ((mx % mn) == 0)){
        cout << days << endl;
        break;
      }
      minab = min(a, b);
      if (minab > TMAX){
        days = minab - TMAX;
        a -= days;
        b -= days;
      }
      else {
        a--;
        b--;
        days++;
      }
    }
    if ((a == 0) || (b == 0))
      cout << -1 << endl;
  }
}
Реклама
Запись опубликована в рубрике программирование с метками , . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s