10099 - The Tourist Guide

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tri_ipst
New poster
Posts: 1
Joined: Wed Oct 19, 2016 5:30 pm

Re: 10099 - The Tourist Guide

Post by tri_ipst » Wed Oct 19, 2016 5:59 pm

I can't figure out why I'm getting WA. The code generates the indicated results for the example in the problem description, the example earlier in this thread with answer 0, and the input from Morass on uDebug.

It is as follows:

Code: Select all

// Solve the Tourist Guide Problem
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <vector>
#include <climits>
#include <algorithm>

const int LARGE_VALUE = INT_MAX;
const int SMALL_VALUE = INT_MIN;
const int SPCL_VALUE = SMALL_VALUE;
const int MIN_INDEX = 1;
int MIN_POWER_NEEDED = 100;

#define MAX_LINE_SIZE 1000000
int getFldsFromLine(char *line, std::vector<char *> &res, const char* sep = " \t\n\v\f\r");

#define mallocOrDie(name, num, type) name = (type *) calloc (num, sizeof ( type )); \
if (name == NULL) { fprintf (stderr, "Couldn't allocate space for '%s'\nBye!\n", #name ); exit (-1); }

#define makeArray(name, m, n, type) if (name != NULL) { free (name[0]); free (name); } if ((n)*(m) == 0) { name = NULL; } else {mallocOrDie (name, (m), type *); \
mallocOrDie (name[0], ((m)*(n)), type); for (int fdsafdas=0; fdsafdas<m-1; ++fdsafdas) { name[fdsafdas+1] = name[fdsafdas] + (n); } }

int main (int argc, char **argv)
{
     FILE *infile = stdin;
//     infile = fopen ("inputs/problem10099.txt", "r");
     int maxIndex = 1000;
     int **arr = NULL, **arr2 = NULL;
     char line[MAX_LINE_SIZE];
     std::vector<char *> flds;
     int numFlds, numCases, caseNum=0;
     makeArray (arr, maxIndex+1, maxIndex+1, int);
     makeArray (arr2, maxIndex+1, maxIndex+1, int);
     while (fgets (line, MAX_LINE_SIZE, infile)) {
          numFlds = getFldsFromLine (line, flds);
          int N = atoi (flds[0]), R = atoi (flds[1]);
          maxIndex = N;
          if ((!N) && (!R))
               break;
          ++caseNum;
          // Initialize arr vector
          for (int i=MIN_INDEX; i<=maxIndex; ++i)
               for (int j=MIN_INDEX; j<=maxIndex; ++j)
                    if (i == j)
                         arr[i][j] = INT_MAX;
                    else
                         arr[i][j] = 0;
          // Now read in the data and put it in the appropriate elements
          // Now squaring the vector
          for (int i=0; i<R; ++i) {
               fgets (line, MAX_LINE_SIZE, infile);
               numFlds = getFldsFromLine (line, flds);
               int num1 = atoi (flds[0]), num2 = atoi (flds[1]), weight = atoi (flds[2]);
               arr[num1][num2] = arr[num2][num1] = weight; }
          for (int power = 1; power <= MIN_POWER_NEEDED; power *= 2) {
               // Initialize arr2
               for (int i=MIN_INDEX; i<=maxIndex; ++i)
                    for (int j=MIN_INDEX; j<=maxIndex; ++j)
                         arr2[i][j] = 0;
               // "Square" arr to get arr2
               for (int i=MIN_INDEX; i<=maxIndex; ++i)
                    for (int j=MIN_INDEX; j<=maxIndex; ++j) {
                         for (int k=MIN_INDEX; k<=maxIndex; ++k) {
                              int newValue = std::min(arr[i][j], arr[j][k]);
                              arr2[i][k] = std::max (arr2[i][k], newValue);
                         }
                    }
               // copy arr2 to arr
               for (int i=MIN_INDEX; i<=maxIndex; ++i)
                    for (int j=MIN_INDEX; j<=maxIndex; ++j)
                         arr[i][j] = arr2[i][j];
          }
          fgets (line, MAX_LINE_SIZE, infile);
          numFlds = getFldsFromLine (line, flds);
          int begin = atoi (flds[0]), end = atoi (flds[1]), passengers = atoi (flds[2]);
          printf ("Scenario #%d\n", caseNum);
          int maxOnSingleTrip = arr[begin][end]-1;
          int numTrips = passengers / maxOnSingleTrip;
          if (passengers % maxOnSingleTrip != 0)
               ++numTrips;
          if (begin == end)
               numTrips = 0;
          printf ("Minimum Number of Trips = %d\n", numTrips);
          printf ("\n");
     }

     makeArray (arr, 0, 0, int);
     makeArray (arr2, 0, 0, int);

     return (0);
}

int getFldsFromLine(char *line, std::vector<char *> &res, const char* sep) {
  char *saveptr;
  res.clear();

  char *tok = strtok_r(line, sep, &saveptr);
  while(tok) {
    res.push_back(tok);
    tok = strtok_r(0, sep, &saveptr);
  }
  return res.size();
}
Any help would be appreciated. Thanks very much.

Helaluddin_brur
New poster
Posts: 15
Joined: Tue Oct 21, 2014 4:08 pm
Location: Bangladesh
Contact:

Re: 10099 - The Tourist Guide

Post by Helaluddin_brur » Fri Jan 06, 2017 1:35 pm

removed after accepted :D :D :D :D

Post Reply

Return to “Volume 100 (10000-10099)”