Zadanie

Najnovšia móda v oblasti kalendárov je kalendár, v ktorom má každý mesiac \(28\) dní. Nie je to až taká novinka. Táto myšlienka je veľmi stará, ale KSPáci sa k nej dostali až nedávno. Rok sa v tomto kalendári skladá z \(13\) mesiacov, každý má presne \(28\) dní a na konci roka nasleduje špeciálny jeden deň, ktorý sa môže využiť na oslavy nového roka. Ak ste správne počítali, výsledný kalendár by mal presne toľko dní v roku ako náš bežný gregoriánsky kalendár. Niektorým KSPákom sa nový kalendár samozrejme nepáči, pretože ich pekné dátumy narodenia ako napr. \(11.11.\) (tento dátum je super, pretože je zrkadlový a skladá sa iba z jednotiek) sa zmenia na nezaujímave \(7.12.\) Preto by všetci chceli rýchlo vedieť, ako bude vyzerať ich dátum narodenia v novom kalendári (aby prípadne mohli protestovať alebo bojovať za jeho zavedenie). Takisto by ich zaujímalo, ktoré dni z nášho kalendára budú nejaké pekné dátumy v novom.

Úloha

Táto úloha sa bude skladať z dvoch častí. V prvej časti budete prevádzať dátumy z nášho kalendára do \(28\) dňového a v druhej časti zase naopak. Všetky dátumy budú patriť do roku \(2015\), takže nebudete musieť riešiť prestupné roky. Posledný deň v roku \(28\) dňového kalendára bude označený ako 1 14 (teda ako keby to bol prvý deň neexistujúceho \(14.\) mesiaca).

Vstup

Na prvom riadku vstupu je číslo \(1\), ktoré znamená, že sa bude prevádzať z nášho kalendára do \(28\) dňového alebo \(2\), ak to bude naopak. Nasleduje číslo \(n\), \(1 \leq n \leq 10^5\) – počet riadkov s dátumami. Ďalej máme \(n\) riadkov, každý obsahujúci dátum buď v našom alebo \(28\) dňovom formáte (dátumy sú uvedené klasicky, najskôr deň, potom mesiac). Vstupy budú rozdelené podľa toho, z ktorého kalendára prechody obsahujú. Ak sa vám podarí napr. prevádzať iba z gregoriánskeho kalendára do \(28\) dňového, môžete stále získať nejaké body.

Výstup

Pre každý dátum zadaný na vstupe vypíšte jeho ekvivalent v opačnom formáte.

Hodnotenie

Zo 6 bodov za popis budú 4 udelené štandartne za popis a zvyšné 2 za eleganciu vášho kódu. Body za kód sa rozdelia rovnomerne medzi obidva prevody (teda 2 za jeden smer a 2 za druhý).

Príklady

Input:

1 3
11 11
1 2
31 12

Output:

7 12
4 2
1 14

Input:

2 3
7 12 
4 2 
1 14

Output:

11 11
1 2
31 12

Úloha sa dala riešiť veľmi veľa spôsobmi. Väčšina z nich, ak sa naimplementovali šikovne, mali dobrú časovú aj pamäťovú zložitosť. Išlo teda hlavne o eleganciu vášho riešenia.

Najmenej elegantné riešenie

Úloha sa dala riešiť úplne priamo. Urobíme si zoznam prekladov dátumov z jedného kalendára do druhého. Aj toto sa dá urobiť rôzne elegantne. Ukážeme si príklad úplne najhoršieho možného riešenia:

#include<cstdio>

int main(){
	int a,n;
	scanf("%d",&a);
	if(a==1){
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			int d,m;
			scanf("%d %d",&d,&m);
			if((d==1)&&(m==1)){
				printf("1 1\n");
			}
			if((d==2)&&(m==1)){
				printf("2 1\n");
			}
			if((d==3)&&(m==1)){
				printf("3 1\n");
			}
			if((d==4)&&(m==1)){
				printf("4 1\n");
			}
			//atď, asi si viete predstaviť ako to pokračuje :)
		}
	}
}

Prečo je toto riešenie zlé? Pretože zakaždým, keď chceme preložiť nejaký dátum, musíme prechádzať cez veľmi veľa ifov. A čo je ešte horšie, všetky tie ify musíme aj napísať. Takže takéto riešenie nie je ani veľmi efektívne (urobí síce pre každý dátum iba konštantný počet operácií, ale tá konštanta je dosť veľká, pre 31.12. musíme prejsť cez 365 ifov). A už vôbec to nie je elegantné.

Trochu elegantnejšie riešenie

Trochu lepšie riešenie nám ponúka Python, kde vieme použiť dictionary (slovník), čo je dátová štruktúra, ktorej každý prvok sa skladá z kľúča a hodnoty, pričom ku hodnote vieme pristúpiť, ak poznáme kľúč. Je to naozaj podobné ako prekladový slovník, predstavte si, že máme prekladový slovník z angličtiny do slovenčiny, potom anglické slová by boli kľuče a slovenské hodnoty. Výhoda slovníka je, že prístup ku každej hodnote vieme vykonať v čase \(O(1)\), teda sa nemusíme otravovať s ifmi a je to aj efektívnejšie. Ako by to vyzeralo implementované?

preklad = {
    1: {
        (1, 1): (1, 1),
        (2, 1): (2, 1),
        (3, 1): (3, 1),
        (4, 1): (4, 1),
        (5, 1): (5, 1),
        (6, 1): (6, 1),
        # ...
    },
    2: {
        (1, 1): (1, 1),
        (2, 1): (2, 1),
        (3, 1): (3, 1),
        (4, 1): (4, 1),
        (5, 1): (5, 1),
        (6, 1): (6, 1),
        # ...
    }
}


smer_prekladu, n = map(int, input().split())
for i in range(n):
    d1, m1 = map(int, input().split())
    d2, m2 = preklad[smer_prekladu][(d1, m1)]
    print("%d %d" % (d2, m2))

Toto riešenie má už síce dobrú časovú zložitosť, ale stále nie je pekné. Čo keby mal rok 20000 dní? Museli by sme vypísať do slovníka všetky. A to sa nám samozrejme nechce.

Vzorové riešenie

Vzorové riešenie bude robiť konverziu v obidvoch smeroch v dvoch krokoch. Najskôr si každý dátum prevedieme na deň v roku, (napr. 3.2. v gregoriánskom kalendári je 34. deň v roku). A následne si tento deň prevedieme na dátum podľa pravidiel druhého kalendára. Prevod z 28 dňového kalendára do dňa v roku je jednoduchšia časť, stačí nám nasledovná rovnica \(denvroku=28(mesiac-1)+den\). Prevod z klasického gregoriánskeho kalendára je trošku zložitejší, musíme si nejakým spôsobom zadrôtovať v programe dĺžky mesiacov, a kedže sa nestriedajú pravidelne a je ich len 12, tak sa nám to celkom oplatí. Najjednoduchší spôsob je urobiť si pole dĺžky 12, v ktorom si budeme udržiavať dĺžky jednotlivých mesiacov. Ale trochu viac sa nám hodí urobiť si pole dĺžky 12, kde budú uložené hodnoty hovoriace, koľko dní v roku prešlo do začiatku daného mesiaca (môžete si uvedomiť, že to by sme v konečnom dôsledku museli rátať aj z pôvodného poľa). Akú ma toto výhodu? Deň v roku potom vieme vyrátať rovnicou \(denvroku=pole[mesiac-1]+den\). Ok, takže už sa vieme dostať z obidvoch kalendárov ku dňu v roku.

A ako sa teraz dostaneme k dátumu? V 28 dňovom kalendári to bude celkom priamočiare. Mesiac dostaneme vydelením dňa v roku číslom 28 a deň ako zvyšok z tejto hodnoty (plus tam máme problémy s nejakými jednotkami, ale na to ste určite prišli aj sami :)). Vyjadrené pomocou vzorcov to bude vyzerať nasledovne:

\[mesiac=(denvroku-1)/28+1\] \[den=(denvroku-1) \bmod 28+1\]

V gregoriánskom kalendári znova použijeme naše pole s predrátanými dňami v roku po začiatok daného mesiaca. Ktoré políčko z toho poľa budeme potrebovať? Predsa najväčšie menšie ako náš hľadaný deň v roku. To samozrejme musí označovať mesiac, v ktorom sa náš deň v roku nachádza. Teda mesiac už máme. A deň potom získame ako \(den=denvroku-pole[mesiac-1]\). Ak ste sa dostali vo vašom riešení sem, stačilo neseknúť sa v detailoch a 10 bodov za riešenie je vašich :).

#include <cstdio>
int mesiace [] ={0,31,59,90,120,151,181,212,243,273,304,334};
int main(){
	int t,n;
	scanf("%d %d",&t,&n);
	for (int i = 0; i < n; ++i){
		int d,m;
		scanf("%d %d",&d,&m);
		if(t==1){
			int num=mesiace[m-1]+d;
			printf("%d %d\n",(num-1)%28+1,(num-1)/28+1);
		}else{
			int num=28*(m-1)+d;
			int i=0;
			while(num>mesiace[i]&&i<12){
				i++;
			}
			printf("%d %d\n",num-mesiace[i-1],i);
		}
	}
}

Ešte dodám, že časová zložitosť tohto riešenia je \(O(n)\) a pamäťová zložitosť tohto riešenia je \(O(1)\), ako aj každého iného tu prezentovaného riešenia, kedže nezávisle na vstupe urobí každé riešenie iba konštantný počet krokov (najviac \(365\cdot konstanta\) pri najhoršom a najmenej \(12\cdot konstanta\) pri najlepšom). Takisto každú hodnotu môžeme spracovať hneď po načítaní, nemusíme si nikde pamätať všetkých \(n\) hodnôt.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.