I came across a problem in a contest which sounds like this:
A date is “robust” if we can uniquely deduce what a valid date it refers to many numbers, without knowing the correspondence between the values and the date fields.
For example, with the values {3, 20, 30, 53, 2021}, we know that it can only be 30.03.2021 20:53, so this date is robust. On the other hand, the date 23.05.2021 20:53 is not robust, because the values {5, 20, 23, 53, 2021} can identify other data (for example, 20.05.2021 23:53).
I tried to write an algorithm based on heap permutation, testing at the same time how many days are in a given month. Also, I made a function which determinates if a date is valid or not.
The final result is s=38087, but It is supposed to be 44382. How could I correct it?
#include<iostream>
using namespace std;
int getNumberOfDays(int month, int year)
{
if( month == 2)
{
if((year%400==0) || (year%4==0 && year%100!=0))
return 29;
else
return 28;
}
else if(month == 1 || month == 3 || month == 5 || month == 7 || month == 8
||month == 10 || month==12)
return 31;
else
return 30;
}
int date(int d, int m, int h, int mn) //data luna ora minut
{
if(m<1 || m>12) return 0;
else {int x=getNumberOfDays(m, 2021);
if(d>x || d<1) return 0;
if(h>23) return 0;
if(mn>59) return 0;}
return 1;
}
void heapPermutation(int a[], int size, int n, int &k)
{
if (size == 1)
{
k+=date(a[0], a[1], a[2], a[3]);
}
for (int i = 0; i < size; i++) {
heapPermutation(a, size - 1, n, k);
if (size % 2 == 1)
swap(a[0], a[size - 1]);
else
swap(a[i], a[size - 1]);
}
}
int main()
{
int d, m, h, mn, s=0;
for(d=1;d<=31;d++)
for(m=1;m<=12;m++)
for(h=0;h<=23;h++)
for(mn=0;mn<=59;mn++)
{
int a[4] = { d, m, h, mn }, n=4, k=0;
heapPermutation(a, n, n, k);
if(k==1) s++;
}
cout<<s;
return 0;
}