## Tuesday, October 7, 2014

### UVa Problem 11242 - Tour de France

Problem:

Solution:

It is a really simple problem - just compute all the drive ratios, sort them, compute all the spreads, and find the maximum.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2183

#include "UVa11242.h"

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

int UVa11242()
{
while (true)
{
int number_of_front_sprockets;
int number_of_rear_sprockets;
vector<int> front_sprockets;
vector<int> rear_sprockets;
cin >> number_of_front_sprockets;
if (number_of_front_sprockets == 0)
{
break;
}

cin >> number_of_rear_sprockets;
front_sprockets.resize(number_of_front_sprockets);
rear_sprockets.resize(number_of_rear_sprockets);
for (int f = 0; f < number_of_front_sprockets; f++)
{
int size;
cin >> size;
front_sprockets[f] = size;
}
for (int r = 0; r < number_of_rear_sprockets; r++)
{
int size;
cin >> size;
rear_sprockets[r] = size;
}
vector<double> drive_ratios;

for (int f = 0; f < number_of_front_sprockets; f++)
{
for (int r = 0; r < number_of_rear_sprockets; r++)
{
double drive_ratio = ((double)rear_sprockets[r]) / front_sprockets[f];
drive_ratios.push_back(drive_ratio);
}
}
sort(drive_ratios.begin(), drive_ratios.end());

bool first = true;
double last;
for (vector<double>::iterator dri = drive_ratios.begin(); dri != drive_ratios.end(); dri++)
{

if (first)
{
first = false;
}
else
{
double spread = *dri / last;