Over a million developers have joined DZone.

A Solution For The "Shoemaker" Problem

· Java Zone

Easily build powerful user management, authentication, and authorization into your web and mobile applications. Download this Forrester report on the new landscape of Customer Identity and Access Management, brought to you in partnership with Stormpath.

A solution for the "Shoemaker" problem.

Problem description:

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.06

 * Solution for "Shoemaker" problem.
 * UVa ID: 10026

#define NJOBS 1000

using namespace std;

int jobs[NJOBS]; /* jobs */
double p[NJOBS]; /* priority */

/* main */
int main() {
    int nc;/* number of cases */
int nj; /* number of jobs */
int ct;/* completion time */
int dp; /* daily penalty */

    cin >> nc;

/* for each test case.. */
    for (int i=0; i> nj;

/* init input */
for (int i=0; i> ct >> dp;
jobs[i] = i;
/* priority is daily penalty divided by completion time (minimal fine) */
p[i] = double(dp) / ct;

int j, k, tmp;

/* sort jobs by priority */
for (int i=0; i p[jobs[k]]) || ((p[jobs[j]] == p[jobs[k]]) && (jobs[j] 

The Java Zone is brought to you by Stormpath—offering a complete, pre-built User Management API for building web and mobile applications, and APIs. Download our new whitepaper: "Build Versus Buy: Customer Identity Management for Web and Mobile Applications".


{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}