@mmix
Da, to sa trougaonom matricom je rešenje. Čim otvorim firmu imaš posao kod mene. Šalim se. Ima jedan mali problem. Odakle mi firma. Ostalo je OK.
Ne znam šta vas je to toliko namučilo oko dekodiranja, ali evo C++ rešenja, pa merite vremena. Nisam ga optimizovao do kraja. Hteo sam da koristim što manji fragment jezika, a da se ipak vide sve formule koje su potrebne u postupku. Pikirao sam na jednostavnost za posetioce koji ne znaju C++. Takođe, sav račun je u 64 bita, tj. svi međurezultati su u opsegu od 0 do 2
64-1.
Code:
#include <iostream>
using namespace std;
// Compiler depended code. This is definition of unsigned 64-bit integer.
// This code can be compiled using GNU C++ compiler and MinGW C++ compiler.
typedef unsigned long long int UInt64;
// March is the first month in the modified calendar (number 0).
// January and February belong to the previous year.
// March = 0, April = 1, May = 2, June = 3, July = 4, August = 5,
// September = 6, October = 7, November = 8, December = 9, January = 10, February = 11
int days_in_month[12] = {31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31, 28};
// Converts datetime to 64-bit unsigned integer.
UInt64 to_num(int year, int month, int day, int hour, int minute, int second) {
UInt64 result = 0;
// Conversion from standard calendar to the modified calendar.
if (month < 3) {
month += 9;
year = year - 1;
} else
month -= 3;
// Number of days in 400 years is 365.2425*400 = 146097.
result = result + (year/400) * 146097;
year = year % 400;
// Number of days in 100 years (of the rest <400 years) is 365.25*100 = 36525.
result = result + (year/100) * 36525;
year = year % 100;
// Number of days in 4 years (of the rest <100 years) is 365.25*4 = 1461.
result = result + (year/4) * 1461;
year = year % 4;
// Number of days in one year (of the rest <4 years) is 365.
result = result + year * 365;
// Add the number of days in previous months.
for (int m = 0; m < month; m = m + 1) {
result += days_in_month[m];
}
// Add the number of previous days in month.
result = result + day - 1;
// Switch to seconds
result = result * (24*60*60);
// Add the number of previous seconds in the day.
result = result + (60*60)*hour + 60*minute + second;
return result;
}
void to_datetime(UInt64 number, int &year, int &month, int &day, int &hour, int &minute, int &second) {
// Conversion from seconds since epoch to days and seconds in day;
int days = number / (24*60*60);
int seconds = number - days * (24*60*60);
int year400 = days / 146097;
year = 400 * year400;
days = days - year400 * 146097;
int year100 = days / 36525;
year = year + 100 * year100;
days = days - year100 * 36525;
int year4 = days / 1461;
year = year + 4 * year4;
days = days - year4 * 1461;
int year1 = days / 365;
year += year1;
days = days - year1 * 365;
int m;
for (m = 0; days >= days_in_month[m]; m = m + 1) {
days = days - days_in_month[m];
}
month = m;
day = days + 1;
hour = seconds / (60*60);
seconds = seconds - hour * (60*60);
minute = seconds / 60;
seconds = seconds - minute * 60;
second = seconds;
// Conversion from modified calendar to standard calendar.
if (month < 10) {
month = month + 3;
} else {
month = month - 9;
year = year + 1;
}
}
UInt64 epoch = to_num(1901, 1, 1, 0, 0, 0);
struct DateTime {
int year;
int month;
int day;
int hour;
int minute;
int second;
};
UInt64 to_num(DateTime datetime) {
UInt64 result = to_num(datetime.year, datetime.month, datetime.day,
datetime.hour, datetime.minute, datetime.second);
result = result - epoch;
return result;
}
DateTime to_datetime(UInt64 number) {
DateTime result;
number = number + epoch;
to_datetime(number, result.year, result.month, result.day,
result.hour, result.minute, result.second);
return result;
}
struct Time_interval {
DateTime from;
DateTime to;
};
// Returns n*(n+1)/2.
UInt64 binomial(UInt64 n) {
// Computing without overflow
if (n % 2 == 0)
return (n/2) * (n+1);
else
return n * ((n+1)/2);
}
UInt64 encode(Time_interval interval) {
UInt64 from = to_num(interval.from);
UInt64 to = to_num(interval.to);
return binomial(to) + from;
}
Time_interval decode(UInt64 code) {
UInt64 min = 0;
// Computing constant 6,074,000,999 without overflow.
// This is the greatest integer n such that n*(n+1)/2 < 2^64.
UInt64 max = 6074001;
max = max * 1000;
max = max - 1;
// Binary search of the greatest number n such that n*(n+1)/2 <= code.
while (min +1 < max) {
UInt64 middle = (min + max) / 2;
if (binomial(middle) > code)
max = middle;
else
min = middle;
}
Time_interval result;
result.to = to_datetime(min);
result.from = to_datetime(code - binomial(min));
return result;
}
ostream& operator<<(ostream &ostr, DateTime datetime) {
ostr << datetime.year
<< "-" << datetime.month
<< "-" << datetime.day
<< " " << datetime.hour
<< ":" << datetime.minute
<< ":" << datetime.second;
return ostr;
}
ostream& operator<<(ostream &ostr, Time_interval interval) {
ostr << interval.from << " " << interval.to;
return ostr;
}
istream& operator>>(istream &istr, DateTime &datetime) {
char ch;
istr >> datetime.year;
istr >> ch;
istr >> datetime.month;
istr >> ch;
istr >> datetime.day;
istr >> datetime.hour;
istr >> ch;
istr >> datetime.minute;
istr >> ch;
istr >> datetime.second;
return istr;
}
istream& operator>>(istream &istr, Time_interval &interval) {
istr >> interval.from;
istr >> interval.to;
return istr;
}
int main() {
cout << "Enter the time interval (from-to) in the format yyyy-mm-dd hh:mm:ss yyyy-mm-dd hh:mm:ss" << endl;
Time_interval interval;
cin >> interval;
UInt64 code = encode(interval);
cout << "It's 64-bit code is " << code << " (decimal)" << endl;
Time_interval check = decode(code);
cout << "Decoded interval is\n" << check << endl;
return 0;
}
[Ovu poruku je menjao Nedeljko dana 26.10.2008. u 15:29 GMT+1]
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.