380 - Call Forwarding

Red Scorpion · Post by **Red Scorpion** » Thu Jan 15, 2004 8:39 am

I got WA many times in this prob, what is the trick?

vivander · Post by **vivander** » Sat May 21, 2005 2:16 am

I don't have idea why I have W.A. for this problem. Can you help me??

My code is over here:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

short int tel_ini[10][101],tel_fin[10][101],llamadas[10][4],marcados[10],flag;

int Calcula_llamada(int hora,int telefono,int indice){
	
	while(1){
			if ((llamadas[indice][0]==0)||(indice>=10)) 
					return telefono;
			else if ((telefono==llamadas[indice][0])&&(marcados[indice]==1)){				
					while (Calcula_llamada(hora,llamadas[indice][3],indice+1)==telefono)
						if (marcados[indice]==0) {
							flag=1;
							break;
						}
					if (flag==1){
						flag=0;
						marcados[indice]=1;
						return Calcula_llamada(hora,telefono,indice+1);
					  }
					else
						return 9999;
				}
			else if ((telefono!=llamadas[indice][0])||((telefono==llamadas[indice][0])&&((hora<llamadas[indice][1])||(hora>llamadas[indice][2]))))
					return Calcula_llamada(hora,telefono,indice+1);
			else if ((telefono==llamadas[indice][0])&&(telefono==llamadas[indice][3])&&(hora>=llamadas[indice][1])&&(hora<=llamadas[indice][2]))
					return 9999;
			else if ((telefono==llamadas[indice][0])&&(hora>=llamadas[indice][1])&&(hora<=llamadas[indice][2])){
					marcados[indice]=1;
					return Calcula_llamada(hora,llamadas[indice][3],0);
				}
		}
}

int main(){
	
	int i,j,l,casos,condiciones,prueba,resultado;
	char linea[1000],res_char[4];
		
	/* Inicializacion de los arrays a utilizar */
	for(i=0;i<10;i++){
		marcados[i]=0;
		
		for(j=0;j<4;j++){
			tel_ini[i][j]=0;
			tel_fin[i][j]=0;
			llamadas[i][j]=0;		
		}
		for(j=4;j<100;j++){
			tel_ini[i][j]=0;
			tel_fin[i][j]=0;
		}
	}

	/* Leer numero de casos */
	fgets(linea,1000,stdin);
	sscanf(linea, "%d", &casos);
	i=0;

	/* Leer forward de llamadas */
	while(1){		
		fgets(linea,1000,stdin);
		sscanf(linea,"%d",&prueba);
		if (prueba!=0){
			sscanf(linea,"%d %d %d %d",&llamadas[i][0],&llamadas[i][1],&llamadas[i][2],&llamadas[i][3]);
			llamadas[i][2] += llamadas[i][1];
			i++;
		}
		else break;
	}
	

	/* Leer lista de llamadas para los dos casos */
	for(i=0; i<casos; i++){
		j=0;
		while(1){
			fgets(linea,1000,stdin);
			sscanf(linea,"%d",&prueba);

			if(prueba==9000) {
				fgets(linea,1000,stdin);
				break;
				}

			else{
				sscanf(linea,"%d %d",&tel_ini[i][j],&tel_fin[i][j]);
				j++;
			}
		}
	}
	
	/* Calcular la redireccion para todas las llamadas */
	printf("CALL FORWARDING OUTPUT\n");
	for(i=0; i< casos; i++){
		printf("SYSTEM %d\n",i+1);
		j=0;
		while(1){
			for(l=0;l<10;l++) marcados[l]=0;
		    flag=0;				
			if ((tel_ini[i][j]!=0)&&(j<=100)){
				resultado = Calcula_llamada(tel_ini[i][j],tel_fin[i][j],0);
				printf("AT ");
				if(tel_ini[i][j]<1000) printf("0");
				if(tel_ini[i][j]<100) printf("0");
				if(tel_ini[i][j]<10) printf("0");
				printf("%d CALL TO ",tel_ini[i][j]);
				if(tel_fin[i][j]<1000) printf("0");
				if(tel_fin[i][j]<100) printf("0");
				if(tel_fin[i][j]<10) printf("0");
				printf("%d RINGS ",tel_fin[i][j]);
				if(resultado<1000) printf("0");
				if(resultado<100) printf("0");
				if(resultado<10) printf("0");
				printf("%d\n",resultado);
			}
			else break;
			j++;
		}
	  }		
		
	printf("END OF OUTPUT\n");	  
	  
	return 1;
}

kwedeer · Post by **kwedeer** » Mon Sep 25, 2006 12:05 am

so - I have made my own code in Pascal - and got WA, although I have perfect agreement with the test case provided in the task. Can someone me provide the test case against which my code gives WA as it is executed by judge?

So - as judge doesn't support TStringList and any serious map-type collection, then I had to use fixed size 2D array tForwards for forwarding command data - the each row contains data about all forwards from one source and each element in row contains data about single forwards - targe, initial time and time period (extension). I have used also some additional arrays to reduce time for sorting (when one should find the path how call is forwarded).

Can some help me to get accepted this task by judge?!!!
A lot of thanks for any help in advance!!!

p.s. as I have observed - then there can be cases when some runtime error (e.g. array index outside boundaries) can be given as WA by judge) - if it is so in this case as well - then it would be so great to get know about this!!!

Code: Select all

program Prg3800(input, output);

{$APPTYPE CONSOLE}

uses
  SysUtils; {Classes for TStringList}

type TExt=record
       time: Integer;
       ext: Integer; //duration
       target: Integer;
       end;

var  //Forwards: array of array of TExt;
     tForwards: array [1..100] of array [1..100] of TExt;
     {not support for dynamic arrays in free pascal -
      maybe only through pointers?}
      sources: array [1..100] of Integer; //sources[i]
      indices: array [1..100] of Integer; //indices[i]->tForwards[indices[i]]
      numberOfSystems: SmallInt;
      source,time,duration,target,extension: SmallInt;
      notEndOfData,sourceFound: Boolean;
      i,j,k: Integer;
      numberOfRequests: Integer;
      maxSource: Integer;
      numberOfTimes: array [1..100] of Integer;
      maxTimes: array [1..100] of Integer;
      minTimes: array [1..100] of Integer;
      nextI: Integer;

  procedure addForwardTime(aIndex,aTime,aDuration,aTarget: Integer);
  var ii,jj: Integer;
  begin
    if aTime>maxTimes[aIndex] then begin
       tForwards[aIndex][numberOfTimes[aIndex]+1].time:=aTime;
       tForwards[aIndex][numberOfTimes[aIndex]+1].ext:=aDuration;
       tForwards[aIndex][numberOfTimes[aIndex]+1].target:=aTarget;
       maxTimes[aIndex]:=aTime+aDuration;
       if (numberOfTimes[aIndex]=0) then begin
         minTimes[aIndex]:=aTime;
       end;
    end else begin // if...
      ii:=1;
      while ( aTime<tForwards[aIndex][ii].time ) do
        inc(ii);
      //ii - the index of the first time which is greater that the
      //new time, so - time[ii] should give place for new time
      for jj:=numberOfTimes[aIndex] downto ii do begin
        tForwards[aIndex][jj+1].time:=tForwards[aIndex][jj].time;
        tForwards[aIndex][jj+1].ext:=tForwards[aIndex][jj].ext;
        tForwards[aIndex][jj+1].target:=tForwards[aIndex][jj].target;
      end;
      tForwards[aIndex][ii].time:=aTime;
      tForwards[aIndex][ii].ext:=aDuration;
      tForwards[aIndex][ii].target:=aTarget;
      if (ii=1) then begin
        minTimes[aIndex]:=aTime;
      end;
    end; // if...
    numberOfTimes[aIndex]:=numberOfTimes[aIndex]+1;
  end; // procedure

  function findTarget(aExtension,aTime,initialTarget: Integer): Integer;
  var ii,jj: Integer;
      sourceHasData,timeIsFound: Boolean;
      fwdIndex: Integer;
      tmpTarget: Integer;
  begin
    if ( (aExtension>maxSource) or
         (aExtension<sources[1])
       ) then begin
      Result:=aExtension;
      exit;
    end;

    //it is possile that we have data for this source
    sourceHasData:=false;
    ii:=1;
    while ( (ii<=numberOfRequests) and
            (not sourceHasData)
          ) do begin
      if sources[ii]=aExtension
        then sourceHasData:=true
        else inc(ii);  //MXX
    end;

    if (not sourceHasData) then begin
      Result:=aExtension;
      exit;
    end else begin
      //extension has additional data - so - check time
      fwdIndex:=indices[ii];
      if ( (aTime<minTimes[ii]) or
           (aTime>maxTimes[ii])
         ) then begin
        Result:=aExtension;
        exit;
      end else begin
        timeIsFound:=false;
        jj:=1;
        // in while condition: ii changed to jj!!!  and added =
        while ( (jj<=numberOfTimes[ii]) and
                (not timeIsFound)
              ) do begin
          if ( (aTime>=tForwards[fwdIndex][jj].time) and
               (aTime<=(tForwards[fwdIndex][jj].time+
                        tForwards[fwdIndex][jj].ext)
               )
             ) then begin
            timeIsFound:=true;
            tmpTarget:=tForwards[fwdIndex][jj].target;
          end else begin
            inc(jj);
          end;
        end; //while

        if timeIsFound then begin
          if tmpTarget=initialTarget then begin
            Result:=9999;
            exit;
          end else begin
            Result:=findTarget(tmpTarget,aTime,initialTarget);
            exit;
          end;
        end else begin
          Result:=aExtension;
          exit;
        end; //if timeIsFound then...
      end; //check - whether time is inside interval about which we have data
    end; //if (not sourceHasData) then ...

  end; //function

  function intToSpecString(num: integer): string;
  {the result for number with more than 4 cipher is not specified}
  var res: String;
  begin
    res:=intToStr(num);
    case length(res) of
      0: res:='0000';
      1: res:='000'+res;
      2: res:='00'+res;
      3: res:='0'+res;
    end;  
    Result:=res;  
  end; //function

begin
   {
  AssignFile(Input, 'in03__.txt');
  Reset(Input);
  AssignFile(Output, 'out03__.txt');
  Rewrite(Output);
    }
  {for each i there is entry in indices[...] and sources[...], where
   sources[...] contain the actual values of source, but indices[...] - the
   index at which the forwarding data from that source is located at tForwards
   array.

   tForwards is 2D array - one row for each source and in this row: - one
   element for each actual forwarding, all the forwardings are ordered in row;
   the number of forwardings from source is contained in numberOfTimes[...]}

  writeln('CALL FORWARDING OUTPUT');

  numberOfRequests:=0;
  for i:=1 to 100 do
    numberOfTimes[i]:=0;

  read(numberOfSystems);
  readln;
  for i:=1 to numberOfSystems do begin
    writeln('SYSTEM '+IntToStr(i));
    notEndOfData:=true;

    // making data structure
    while(notEndOfData) do begin
      read(source);
      if (source<>0) then begin
        read(time);
        read(duration);
        read(target);
        //add entry to data structure;

        j:=1;
        sourceFound:=false;
        while ( (source<=maxSource) and    //MXX - in both tests = added
                (j<=numberOfRequests) and
                (not sourceFound)
              ) do begin
          if (source=sources[j])
            then sourceFound:=true;
          inc(j);
        end;
        if sourceFound then begin
          //entry is found - so - simply add time/duration/extension data
          addForwardTime(indices[j-1],time,duration,target);
        end else begin
          //no entry is found for source - so add new entry -
          //check - where to put it - at the top of array - or iside it
          if (source<maxSource) then begin
            //the new element is inserted inside the array - nextI is the
            //place where new source is going
            nextI:=0;
            while source>sources[nextI] do Inc(nextI);
            for k:=numberOfRequests downto nextI do begin
              indices[k+1]:=indices[k];
            end;
            indices[nextI]:=numberOfRequests+1;
            addForwardTime(indices[nextI],time,duration,target);
            numberOfRequests:=numberOfRequests+1;
          end else begin //if (source<maxSource)...
            //the new element is put at the top of array
            indices[numberOfRequests+1]:=numberOfRequests+1;
            sources[numberOfRequests+1]:=source;
            maxSource:=source;
            addForwardTime(indices[numberOfRequests+1],time,duration,target);
            numberOfRequests:=numberOfRequests+1;
          end; //if (source<maxSource)...
        end; // if sourceFound...
      end else begin // if source<>0 ...
        notEndOfData:=false;
      end; // if source<>0 ...
      readln;
    end; // while ...

    //now we have data structure - we are employing it for call target
    //determination
    notEndOfData:=true;
    while (notEndOfData) do begin
      read(time);
      if (time<>9000) then begin
        read(extension);
        target:=findTarget(extension,time,extension);
        writeln('AT '+intToSpecString(time)+
                ' CALL TO '+intToSpecString(extension)+
                ' RINGS '+intToSpecString(target));
      end else begin
        notEndOfData:=false;
      end;

      readln;
    end;

  end; // for ... numberOfSystems

  writeln('END OF OUTPUT');
end.

shantanu18 · Post by **shantanu18** » Sat Sep 04, 2010 10:12 am

WA! please help! please give some IO. Thanks in advance

Code: Select all

#include <vector>
#include <map>
#include <iostream>
#include <cstdio>
#include <sstream>
#define pa pair<TIME,int>
#define MAX 10010
#define white 0
#define black 1

using namespace std;
struct TIME{
	int start;
	int end;
};
vector <pa> V[MAX];
int dis[MAX],f[MAX];
int Time=0;
bool gf=false;
void Track(int src,int time)
{
	for(int i=0;i<(int)V[src].size();i++)
	{
		if(dis[V[src][i].second]==white && time >=V[src][i].first.start && time<=V[src][i].first.end)
		{
			++Time;
			dis[V[src][i].second]=black;
			Track(V[src][i].second,time);
			dis[V[src][i].second]=white;
		}
		else if(dis[V[src][i].second]==black && time >=V[src][i].first.start && time<=V[src][i].first.end)
		{
			gf=true;
			return;
		}
	}
	++Time;
	f[src]=Time;
}

int main()
{
	//freopen("380.in","r",stdin);
	int t,m,s,d,n;
	scanf("%d",&t);
	printf("CALL FORWARDING OUTPUT\n");
	for(int l=0;l<t;l++)
	{
		printf("SYSTEM %d\n",l+1);
		map <int,int>rmp;
		map <int,int> mp;
		int k=0;
		while(scanf("%d",&n)==1 && n)
		{
			scanf("%d%d%d",&s,&d,&m);
			if(mp.find(n)==mp.end()) 
			{
				mp[n]=k++;
				rmp[k-1]=n;
			}
			if(mp.find(m)==mp.end())
			{
				mp[m]=k++;
				rmp[k-1]=m;
			}
			TIME tmp;
			tmp.start = s;
			tmp.end=s+d;
			V[mp[n]].push_back(pa(tmp,mp[m]));
		}
		string time;int src,somoy;
		getchar();
		while((getline(cin,time))!=NULL)
		{
			if(time.compare("9000")==0)break;
			stringstream ss(time);
			for(int i=0;i<=(int)mp.size();i++)
			{
				f[i]=0x3f3f3f3f;
				dis[i]=white;
			}
			ss>>src;
			somoy=src;
			ss>>src;
			if(mp.find(src)==mp.end()) {mp[src]=k++;rmp[k-1]=src;}
			Time=0;
			gf=false;
			Track(mp[src],somoy);
			string re="";
			for(int i=0;i<(int)time.length();i++)
			{
				if(time[i]==' ')break;
				re = re + time[i];
			}
			if(gf)
			{
				printf("AT ");
				cout<<re; 
				printf(" CALL TO %d RINGS 9999\n",src);
			}
			else
			{
				int min=99999;
				int save=-1;
				for(int i=0;i<(int)rmp.size();i++)
					if(min>f[i]) {min=f[i];save=i;}
				printf("AT ");
				cout<<re; 
				printf(" CALL TO %d RINGS %d\n",src,rmp[save]);
			}
		}
		for(int i=0;i<=(int)mp.size();i++)
		{
			V[i].clear();
		}
	}
	printf("END OF OUTPUT\n");
	return 0;
}

OJ Board

380 - Call Forwarding

380-Call Forwarding, What is the trick?

380 - Call Forwarding

Re: 380 - Why do I have W.A.?