Problem code : TRAVELPROB (TRAVELPROB)
Author : shyam1909
Difficulty Level : Easy
Question:
3 roads connect 4 destinations. Each road is unique. Can you travel all 4 destinations by travelling each road only once?
Solution:
If you observe carefully, Each destination must be connected with either 1 or 2 road(s). If the number of roads connected is 0, the destination is inaccessible. If the number of roads connected to any destination is more than 2. Then to travel all destinations some roads have to be travelled twice.
In other words,
All individual destinations should be connected to either 1 road / 2 roads. If the road count to any individual destination is 0 or 3, it will not satisfy the condition given in question.
C++ Solution:
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int arr[4];
for(int i=0;i<4;i++)
{
arr[i] = 0;
}
for(int i=0;i<6;i++)
{
int x;
cin >> x;
arr[x-1]++;
}
if((arr[0] >= 1 && arr[0] <= 2) && (arr[1] >= 1 && arr[1] <= 2) && (arr[2] >= 1 && arr[2] <= 2) && (arr[3] >= 1 && arr[3] <= 2))
{
cout << "YES\n";
return;
}
else
{
cout << "NO\n";
return;
}
}
int main()
{
int t;
cin >> t;
while(t–)
{
solve();
}
return 0;
}