Thread: Very difficult task

So my teacher gave me the task to solve it for tomorrow but there is no possible way I can do it

So here it is:
Along the circular road,there are N cities and in every city has it's own shop for appliances. You know (enter) the price of each fridge and the price of the trip (two-way ticket). For citizens of each city determinate the city in which they can find the cheapest fridge plus the smallest price for tickets. Directions can be clockwise or counterclockwise.

Test example:

Ticket: 4 3 4 10
Fridge: 5 10 7 10

For citizens of the first city: It's cheapest to go to the town 1.
For citizens of the second city: It's best to stay in their own city
For citizens of the the third city: It's best to stay in their own city
For citizens of the fourth city: It's best to go the town 1.


We came to arrays so no advanced techniques like pointers or functions are allowed.


Thank you.

The rule is that you give it a shot first,try your attempt here and then the problem is sure to be solved.

Oh didn't know that.

Code:

#include<stdio.h> 
#include<conio.h> 
#define MAX 40 


int main() 
{ 
   int price[MAX],ticket[MAX],i,n,pos,xu,yu,s[MAX],j,z[MAX],q[MAX],min,t,pozk; 
   for(i=0;i<n;i++) cena[i]=karta[i]=0; 
   do 
   { 
      printf("Number of the city and fridges:");
      scanf("%d",&n); 
      if(n>0 && n<MAX) break; 
      clrscr(); 
   }            while(1); 
    printf("Enter the price of the fridges"); 
    xu=wherex(); 
    yu=wherey(); 
    xu=1; 
    yu++; 
   for(i=0;i<n;i++) 
   { 
     gotoxy(xu,yu); 
     scanf("%d",&price[i]); 
     xu+=5; 
     if(xu>80) xu=1,yu++; 
   } 
   printf("Entere the price of the tickets"); 
    xu=wherex(); 
    yu=wherey(); 
    xu=1; 
    yu++; 
   for(i=0;i<n;i++) 
   { 
      gotoxy(xu,yu); 
     scanf("%d",&ticket[i]); 
     xu+=5; 
     if(xu>80) xu=1,yu++; 
   } 
   printf("\n\nEnter the city where you are located:"); 
   do{ 
       xu=wherex(); 
       yu=wherey(); 
   scanf("%d",&poz); 
   if(poz>0 && poz<n) break; 
   gotoxy(xu,yu); 
   printf("         "); 
   gotoxy(xu,yu); 
   }while(1); 
   s[0]=min; 
   for(i=0;i<n;i++) 
   { 
        s[i]=ticket[i]+price[i]; 
        if(s[i]<min) min=s[i],pozk=j; 


   } 
   printf("Ticket:%d\n Price of the fridge:%d ",ticket[pozk],price[pozk]); 
   getch(); 
}

The problem with my code is that it's showing only the place where the cheapest ticket and price of the fridge are.

Code:

#include<stdio.h>
#define MAX 40




int main()
{
   int price[MAX],ticket[MAX],i,n,loc,xu,yu,s[MAX],j,z[MAX],q[MAX],min,t,pozk;
   for(i=0;i<n;i++) price[i]=ticket[i]=0;
   do
   {
      printf("Number of the city and fridges:");
      scanf("%d",&n);
      if(n>0 && n<MAX) break;
      printf("Wrong entry!!!");
   }            while(1);
    printf("Enter the price of the fridges\n");
   for(i=0;i<n;i++)
   {
     printf("Fridge No[%d]:",i+1);
     scanf("%d",&price[i]);
   }
   printf("Entere the price of the tickets\n");
   for(i=0;i<n;i++)
   {
     printf("Ticket for city number[%d]:",i+1);
     scanf("%d",&ticket[i]);


   }
   printf("\n\nEnter the city where you are located:");
   do{
   scanf("%d",&loc);
   if(loc>0 && loc<n) break;
   printf("Wrong entry!!!");
   }while(1);
   s[0]=min;
   for(i=0;i<n;i++)
   {
        s[i]=ticket[i]+price[i];
        if(s[i]<min) min=s[i],pozk=j;




   }
   printf("Ticket:%d\n Price of the fridge:%d ",ticket[pozk],price[pozk]);


}

Here is the version w/out getch(); and other conio.h-related functions.

Code:

#include<stdio.h>


#define MAX 40


int main(void)
{
   int price[MAX],ticket[MAX],i,n,loc,s[MAX],j,min,pozk;




   for(i=0;i<MAX;i++) price[i]=ticket[i]=0;
   while (1)
   {
      printf("Number of the city and fridges:");
      scanf("%d",&n);
      if(n>0 && n<MAX) break;
      printf("Wrong entry!!!");
   }


   printf("Enter the price of the fridges\n");


   for(i=0;i<n;i++)
   {
     printf("Fridge No[%d]:",i+1);
     scanf("%d",&price[i]);
   }


   printf("Enter the price of the tickets\n");


   for(i=0;i<n;i++)
   {
     printf("Ticket for city number[%d]:",i+1);
     scanf("%d",&ticket[i]);
   }


   printf("\n\nEnter the city where you are located:");


   while (1)
   {
      scanf("%d",&loc);
      if(loc>0 && loc<n) break;
      printf("Wrong entry!!!");
   }


   min=s[0];




   for(i=0;i<n;i++)
   {
        s[i]=ticket[i]+price[i];
        if(s[i]<min) min=s[i],j=pozk;
   }


   printf("Ticket:%d\n Price of the fridge:%d ",ticket[pozk],price[pozk]);


   return 0;
}

Okay but the logic in my task is wrong so someone needs to give me the direction to solve this problem.

Assuming the inputs are interpreted as

Code:

    City     (4)    1     2     3      4
    Ticket       4     3     4     10 
    Fridge          5    10     7     10

it is easy to construct the logic needed to find the cheapest (and let's say "fastest" -- break ties by choosing the least number of tickets needed) way to buy a fridge. However, the results are different:

Code:

    In city 1, it is cheapest to buy a fridge locally for 5.
    In city 2, it is cheapest to buy a fridge from city 1, for 5 + 3 = 8.
    In city 3, it is cheapest to buy a fridge locally for 7.
    In city 4, it is cheapest to buy a fridge from city 1, for 5 + 4 = 9.

One could also interpret the data as

Code:

    City     1     2     3     4    (1)
    Ticket      4     3     4     10 
    Fridge   5    10     7    10

    In city 1, it is cheapest to buy a fridge locally for 5.
    In city 2, it is cheapest to buy a fridge from city 1 for 5 + 4 = 9.
    In city 3, it is cheapest to buy a fridge locally for 7.
    In city 4, it is cheapest to buy a fridge locally for 10.

Start at the current city, and the fridge price there. This is the initial best price.

Next, do a loop with two imaginary travellers, one going clockwise, the other counterclockwise. Each traveller at each stop (city) compares the fridge price at that city plus the accumulated ticket costs, to the best price. If it is better than the currently best price, update the best price (and the city it was obtained from, and optionally which way the traveller went). Repeat until both travellers have arrived back at the original city.

To find the optimum for all cities, you simply repeat the above loop for each city separately. (You could also use a separate pair of virtual travellers for each city; that solution becomes useful only when you have lots of cities, and wish to parallelize the work using multiple threads. In this particular problem it is not useful at all, because there is not enough work to do at each stop.)

Tip 1: Note that there are two prices to reach any given city from any given city: one clockwise, and the other counterclockwise. If you use < for the best price comparison, among multiple equal prices you'll get the one with the fewest trips, because those are found earlier in the loop. If you use <= you'll get the one with the most trips, since later iterations will be preferred over earlier ones for equal price.

Tip 2: Your loop does need to go fully around, both travellers to the origin city (actually, the city before that). It is not enough to go half way, i.e. when the travellers meet! Consider a case where almost all trips are almost free, with the cheapest fridge at the next city clockwise, but that one trip being very expensive. The cheapest way might just be to travel almost the entire circuit counterclockwise to the city next clockwise! While this does not happen with these exact inputs, you shouldn't assume it will never happen.

Great discussion by Nominal Animal ^^^. Especially good was the part about the need to check which way is the better way to move, to get the best price (clockwise or counter clockwise), and the need to go all the way around.

Thank you Nominal Animal...I will try something with your help...
Now I have some other problem with some other task...

How can I randomize numbers from one to seven in one array without repeating?

Code:

Code:

#include <stdio.h>
#include <stdlib.h>
#define MAX 7
int main()
{
    int x[MAX],i,j;
    for(i=0;i<MAX;i++) x[i]=0;
    for(i=0;i<MAX;i++)
    {
        j=0;
        randomize();
        x[i]=random(7);
        while(j<i){ j++; if(x[i]==x[j]) break;}
        if(j!=i) while(x[j]!=x[i]) x[i]=random(7);
    }
    for(i=0;i<MAX;i++)
    {
        printf("%d\n",x[i]);
    }
}

I tried like this,but it gets me the same number over and over

Originally Posted by kantagara

Thank you Nominal Animal...I will try something with your help...
Now I have some other problem with some other task...

How can I randomize numbers from one to seven in one array without repeating?

Code:

Code:

#include <stdio.h>
#include <stdlib.h>
#define MAX 7
int main()
{
    int x[MAX],i,j;
    for(i=0;i<MAX;i++) x[i]=0;
    for(i=0;i<MAX;i++)
    {
        j=0;
        randomize();
        x[i]=random(7);
        while(j<i){ j++; if(x[i]==x[j]) break;}
        if(j!=i) while(x[j]!=x[i]) x[i]=random(7);
    }
    for(i=0;i<MAX;i++)
    {
        printf("%d\n",x[i]);
    }
}

I tried like this,but it gets me the same number over and over

What does the "randomize" function do? It's not a standard function.

My guess is it's a Terrible C extension which sets the seed from the current time. If that's the case, you're likely seeding the random-number generator with the same initial random number every time through the loop, since the system clock doesn't change during the loop. Call randomize() only once in your program, such as at the top of main().

But for the task at hand (generating an array of non-repeating random numbers), this could be called "shuffling". Set each element to its index plus one (x[0] = 1, x[1] = 2, etc), iterate through each element in the array except for the last, and then swap the value at that index and one of the remaining elements (from a randomly chosen index, of course). This might have an off-by-one error (I haven't tested it), but the basic concept should work for shuffling the values.

Originally Posted by christop

this could be called "shuffling".

It is. The common method is well described in the Wikipedia article for Fisher-Yates shuffle (also known as Knuth shuffle).

The basic idea is to first create an array with all the values, then either reorder them by swapping each one with a random one in the array, or by creating a copy of the array where the elements are in random order. Remember that in C, arrays are zero based, i.e. a[0] is the first element.

There are algorithms for filling an array with consecutive numbers in random order, but they are very tricky to write right. Most implementations suffer from subtle bugs that cause the order to be less random than expected (nonuniform distribution). First filling an array and then shuffling it is much simpler and much more robust.