Исследовательский институт полупроводников Samsung (программное обеспечение SSIR), стажер / FTE | Комплект-1

Опубликовано: 4 Января, 2022

Есть N мест для рыбалки и 3 ворот. У каждых ворот несколько рыбаков ждут, чтобы добраться до ближайшего незанятого места для рыбалки. (Общее количество рыбаков <= N)
Расстояние между последовательными точками = расстояние между воротами и ближайшей точкой = 1 м
Только 1 ворота могут быть открыты одновременно, и все рыбаки этих ворот должны занять места до открытия следующих ворот.
Расстояние рассчитывается как от ворот до ближайшего места + от ближайшего места до ближайшего свободного места.
Найдите общую сумму минимальных расстояний, которые нужно пройти всем рыбакам.

Входы, которые необходимо предпринять:
Количество мест для рыбалки
Положение ворот
Количество рыбаков у каждых ворот

Следуйте этому примеру:

Общее количество мест для рыбалки = 10
5 рыбак у выхода 1, расположенного в позиции 4,
2 рыбака у выхода 2 на позиции 6,
2 рыбака у выхода 3 на позиции 10,

Если ворота открываются в порядке G1-> G2-> G3
Аранжировка будет:

Расстояние рассчитывается как от ворот до ближайшего места + от ближайшего места до ближайшего свободного места.
После открытия ворот G1 рыбаки размещаются в местах, отмеченных цифрой 1.
Расстояние = 11м
После открытия ворот G2 рыбаки размещаются в местах, отмеченных цифрой 2.
Расстояние = 5м
После открытия ворот G3 рыбаки размещаются в местах, отмеченных цифрой 3.
Расстояние = 3 м
Общее расстояние в таком порядке: 11 + 5 + 3 = 19

Если ворота открываются в порядке G2-> G1-> G3

Случай 1 - Последний рыбак у выхода 2 находится на позиции 7
окончательная аранжировка будет:

После открытия ворот G2 рыбаки размещаются в местах, отмеченных цифрой 2.
Расстояние = 3 м
После открытия ворот G1 рыбаки размещаются в местах, отмеченных цифрой 1.
Расстояние = 12 м
После открытия ворот G3 рыбаки размещаются в местах, отмеченных цифрой 3.
Расстояние = 3 м
Общее расстояние в таком порядке: 3 + 12 + 3 = 18
Случай 2 - Последний рыбак у выхода 2 размещается на позиции 5
окончательная аранжировка будет:

После открытия ворот G2 рыбаки размещаются в местах, отмеченных цифрой 2.
Расстояние = 3 м
После открытия ворот G1 рыбаки размещаются в местах, отмеченных цифрой 1.
Расстояние = 14 м
После открытия ворот G3 рыбаки размещаются в местах, отмеченных цифрой 3.
Расстояние = 3 м
Общее расстояние в таком порядке: 3 + 14 + 3 = 20

Остальные случаи избыточны
минимальное расстояние 18

Решение:
Сгенерируйте все комбинации и назначьте рыбаков для всех комбинаций ворот, чтобы рассчитать минимальное расстояние ходьбы.
Генерация комбинации может выполняться как рекурсивным, так и итеративным способом. Теперь, чтобы исключить ненужные перестановки, мы можем сделать вывод, что при минимальных расстояниях ходьбы рыбаки от определенных ворот должны оставаться вместе, то есть они должны занимать последовательные места для рыбалки. Таким образом, мы можем представить себе проблему в виде 3 блоков (группы рыбаков), скользящих по всему промысловому ареалу. Минимум из которых и есть ответ.

C ++

 #define _CRT_SECURE_NO_WARNINGS
 #include<iostream>
 using namespace std;
 #define MAX 3
 
int fishspot[100]; // fishing spots
 int gate[MAX]; // position of gates
 int fishermen[MAX]; // no of fishermen at each gate
 int N; // total no of fishing spots
 int visited[MAX]; // occupied fishing spots
 int Answer; // result
 
// To unmark spots occupied by fishermen of gate# index
 class GFG
 {
 public :
 void reset_fishspot( index) int
 {
    int i;
    for (i = 1; i <= N; i++)
        if (fishspot[i] == index + 1)
            fishspot[i] = 0;
 }
 
// Calculate minimum distance while
 // allotting spots to fishermen of gate# index.
 // Returns number of positions possible
 // with minimum disance.
 // pos1, pos2 is used to return positions
 int calculate_distance( int index, int *pos1,
                       int *pos2, int *score)
 {
    int i, sum = 0, left_min = 999999,
                    right_min = 999999,
                    left, right, npos = 0;
    *pos1 = *pos2 = *score = 0;
 
    left = right = gate[index];
 
    // Allot spots to all fishermen except
    // last based on minimum distance
    for (i = 1; i < fishermen[index]; i++)
    {
        if (fishspot[gate[index]] == 0)
        {
            sum++;
            fishspot[gate[index]] = index + 1;
        }
        else
        {
            left_min = right_min = 999999;
 
            while ((left > 0) && (fishspot[left] > 0))
                left--;
 
            while ((right <= N) &&
                   (fishspot[right] > 0))
                right++;
 
            if ((left > 0) && (fishspot[left] == 0))
                left_min = gate[index] - left + 1;
 
            if ((right <= N) && (fishspot[right] == 0))
                right_min = right - gate[index] + 1;
 
            if (right_min == left_min)
            {
                // Place 2 fishermen, if avaiable
                if ((fishermen[index] - i - 1) > 1)
                {
                    fishspot[left] = fishspot[right] = index + 1;
                    sum += (2 * left_min);
                    i++;
 
                    // If all fishermen are alloted spots
                    if (i == fishermen[index])
                    {
                        npos = 1;
                        *score = sum;
                        return npos;
                    }
                }
                else
                {
                    sum += left_min;
                    fishspot[left] = index + 1;
                }
            }
            else if (left_min < right_min)
            {
                sum += left_min;
                fishspot[left] = index + 1;
            }
            else if (right_min < left_min)
            {
                sum += right_min;
                fishspot[right] = index + 1;
            }
        }
    }
 
    left_min = right_min = 99999;
 
    // Allot spot to last fishermen
    while ((left > 0) && (fishspot[left] > 0))
        left--;
 
    if ((left > 0) && (fishspot[left] == 0))
        left_min = gate[index] - left + 1;
 
    while ((right <= N) && (fishspot[right] > 0))
        right++;
 
    if ((right <= N) && (fishspot[right] == 0))
        right_min = right - gate[index] + 1;
 
    if ((sum + left_min) == (sum + right_min))
    {
        npos = 2;
        *pos1 = left;
        *pos2 = right;
        *score = sum + left_min;
    }
    else if ((sum + left_min) >
             (sum + right_min))
    {
        npos = 1;
        *score = sum + right_min;
        fishspot[right] = index + 1;
    }
    else if ((sum + left_min) <
             (sum + right_min))
    {
        npos = 1;
        *score = sum + left_min;
        fishspot[left] = index + 1;
    }
    return npos;
 }
 
// Solve is used to select next gate
 // and generate all combinations.
 solve( void int index, int sum, int count)
 {
    int npos, pos1, pos2, score, i;
 
    visited[index] = 1;
 
    if (sum > Answer)
        return ;
 
    npos = calculate_distance(index, &pos1,
                              &pos2, &score);
    sum += score;
 
    if (count == MAX)
    {
        if (Answer > sum)
            Answer = sum;
 
        return ;
    }
 
    if (npos == 1)
    {
        for (i = 0; i < MAX; i++)
        {
            if (visited[i] == 0)
            {
                solve(i, sum, count + 1);
                visited[i] = 0;
                reset_fishspot(i);
            }
        }
    }
     
    else if (npos == 2)
    {
        fishspot[pos1] = index + 1;
        for (i = 0; i < MAX; i++)
        {
            if (visited[i] == 0)
            {
                solve(i, sum, count + 1);
                visited[i] = 0;
                reset_fishspot(i);
            }
        }
 
        fishspot[pos1] = 0;
        fishspot[pos2] = index + 1;
        for (i = 0; i < MAX; i++)
        {
            if (visited[i] == 0)
            {
                solve(i, sum, count + 1);
                visited[i] = 0;
                reset_fishspot(i);
            }
        }
        fishspot[pos2] = 0;
    }
 }
 };
 
// Driver Code
 int main()
 {
    GFG g;
 
    int i;
    /*scanf("%d", &N); // for input
         
    for (i = 0; i < MAX; i++)
    {
        scanf("%d %d", &gate[i], &fishermen[i]);
        visited[i] = 0;
    }*/
     
    N = 10; // total no of fishing spots
     
    // position of gates(1-based indexing)
    gate[0] = 4;
    gate[1] = 6;
    gate[2] = 10;
     
    //no of fishermen at each gate
    fishermen[0] = 5; //gate1
    fishermen[1] = 2; //gate 2
    fishermen[2] = 2; //gate 3
 
    for (i = 1; i <= N; i++)
        fishspot[i] = 0;
 
    Answer = 999999;
 
    for (i = 0; i < MAX; i++)
    {
        g.solve(i, 0, 1);
        visited[i] = 0;
        g.reset_fishspot(i);
    }
 
    cout << Answer << endl;
 
    return 0;
 }
 
// This code is contributed by SoM15242

C

 #define _CRT_SECURE_NO_WARNINGS
 #include<stdio.h>
 
#define MAX 3
 
int fishspot[100]; // fishing spots
 int gate[MAX]; // position of gates
 int fishermen[MAX]; // no of fishermen at each gate
 int N; // total no of fishing spots
 int visited[MAX]; // occupied fishing spots
 int Answer; // result
 
//To unmark spots occupied by fishermen of gate# index
 void reset_fishspot( index) int
 {
    int i;
    for (i = 1; i <= N; i++)
        if (fishspot[i] == index + 1)
            fishspot[i] = 0;
 }
 
// Calculate minimum distance while allotting spots to
 // fishermen of gate# index.
 // Returns number of positions possible with minimum disance.
 // pos1, pos2 is used to return positions
 int calculate_distance( int index, int *pos1, int *pos2, int *score)
 {
    int i, sum = 0, left_min = 999999, right_min = 999999,
                                    left, right, npos = 0;
    *pos1 = *pos2 = *score = 0;
 
    left = right = gate[index];
 
    // Allot spots to all fishermen except last based on
    // minimum distance
    for (i = 1; i < fishermen[index]; i++)
    {
        if (fishspot[gate[index]] == 0)
        {
            sum++;
            fishspot[gate[index]] = index + 1;
        }
        else
        {
            left_min = right_min = 999999;
 
            while ((left > 0) && (fishspot[left] > 0))
                left--;
 
            while ((right <= N) && (fishspot[right] > 0))
                right++;
 
            if ((left > 0) && (fishspot[left] == 0))
                left_min = gate[index] - left + 1;
 
            if ((right <= N) && (fishspot[right] == 0))
                right_min = right - gate[index] + 1;
 
            if (right_min == left_min)
            {
                // Place 2 fishermen, if avaiable
                if ((fishermen[index] - i - 1) > 1)
                {
                    fishspot[left] = fishspot[right] = index + 1;
                    sum += (2 * left_min);
                    i++;
 
                    // If all fishermen are alloted spots
                    if (i == fishermen[index])
                    {
                        npos = 1;
                        *score = sum;
                        return npos;
                    }
                }
                else
                {
                    sum += left_min;
                    fishspot[left] = index + 1;
                }
            }
            else if (left_min < right_min)
            {
                sum += left_min;
                fishspot[left] = index + 1;
            }
            else if (right_min < left_min)
            {
                sum += right_min;
                fishspot[right] = index + 1;
            }
        }
    }
 
    left_min = right_min = 99999;
 
    // Allot spot to last fishermen
    while ((left > 0) && (fishspot[left] > 0))
        left--;
 
    if ((left > 0) && (fishspot[left] == 0))
        left_min = gate[index] - left + 1;
 
    while ((right <= N) && (fishspot[right] > 0))
        right++;
 
    if ((right <= N) && (fishspot[right] == 0))
        right_min = right - gate[index] + 1;
 
    if ((sum + left_min) == (sum + right_min))
    {
        npos = 2;
        *pos1 = left;
        *pos2 = right;
        *score = sum + left_min;
    }
    else if ((sum + left_min) > (sum + right_min))
    {
        npos = 1;
        *score = sum + right_min;
        fishspot[right] = index + 1;
    }
    else if ((sum + left_min) < (sum + right_min))
    {
        npos = 1;
        *score = sum + left_min;
        fishspot[left] = index + 1;
    }
 
    return npos;
 }
 
// Solve is used to select next gate and generate all combinations.
 void solve( int index, int sum, int count)
 {
    int npos, pos1, pos2, score, i;
 
    visited[index] = 1;
 
    if (sum > Answer)
        return ;
 
    npos = calculate_distance(index, &pos1, &pos2, &score);
    sum += score;
 
    if (count == MAX)
    {
        if (Answer > sum)
            Answer = sum;
 
        return ;
    }
 
    if (npos == 1)
    {
        for (i = 0; i < MAX; i++)
        {
            if (visited[i] == 0)
            {
                solve(i, sum, count + 1);
                visited[i] = 0;
                reset_fishspot(i);
            }
        }
    }
    else if (npos == 2)
    {
        fishspot[pos1] = index + 1;
        for (i = 0; i < MAX; i++)
        {
            if (visited[i] == 0)
            {
                solve(i, sum, count + 1);
                visited[i] = 0;
                reset_fishspot(i);
            }
        }
 
        fishspot[pos1] = 0;
        fishspot[pos2] = index + 1;
        for (i = 0; i < MAX; i++)

                    
                                            Собеседования
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИОпыт интервью BYJU (за пределами кампуса) 2022 г.
24 Февраля, 2023
Опыт интервью Trilogy Innovations Lab для SDE (на кампусе) 2022
24 Февраля, 2023
Опыт интервью с фанатиками для SWE -1 (в кампусе) 2022 г.
24 Февраля, 2023
Опыт интервью Legato Health Technologies (на кампусе) 2022 г.
18 Февраля, 2023
Опыт собеседования по банковскому программному обеспечению Sopra
18 Февраля, 2023
ZEE Entertainment Pvt. ООО Опыт интервью
18 Февраля, 2023
Опыт интервью Hanu Software Solutions
18 Февраля, 2023
Kantar Interview Experience для SDE-1 (в кампусе)
18 Февраля, 2023