Maya Calendar

During his last sabbatical, professor M. A. Ya made a surprising discovery about the old Maya calendar. From an old knotted message, professor discovered that the Maya civilization used a 365 day long year, called Haab, which had 19 months. Each of the first 18 months was 20 days long, and the names of the months were pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu. Instead of having names, the days of the months were denoted by numbers starting from 0 to 19. The last month of Haab was called uayet and had 5 days denoted by numbers 0, 1, 2, 3, 4. The Maya believed that this month was unlucky, the court of justice was not in session, the trade stopped, people did not even sweep the floor.

For religious purposes, the Maya used another calendar in which the year was called Tzolkin (holly year). The year was divided into thirteen periods, each 20 days long. Each day was denoted by a pair consisting of a number and the name of the day. They used 20 names: imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau and 13 numbers; both in cycles.

Notice that each day has an unambiguous description. For example, at the beginning of the year the days were described as follows:

1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, and again in the next period 8 imix, 9 ik, 10 akbal . . .

Years (both Haab and Tzolkin) were denoted by numbers 0, 1, ... , where the number 0 was the beginning of the world. Thus, the first day was:

Haab: 0. pop 0

Tzolkin: 1 imix 0

Help professor M. A. Ya and write a program for him to convert the dates from the Haab calendar to the Tzolkin calendar.

Input

The date in Haab is given in the following format:

NumberOfTheDay. Month Year

The first line of the input contains the number of the input dates in the input. The next n lines contain n dates in the Haab calendar format, each in separate line. The year is smaller then 5000.

Output

The date in Tzolkin should be in the following format:

Number NameOfTheDay Year

The first line of the output contains the number of the output dates. In the next n lines, there are dates in the Tzolkin calendar format, in the order corresponding to the input dates.

Sample Input	Sample Output
3 10. zac 0 0. pop 0 10. zac 1995	3 3 chuen 0 1 imix 0 9 cimi 2801

Solucion

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Luis Carlos
*/
public class MayaCanlendar {

private BufferedReader bf = null;
private static List mesesHaab = Arrays.asList("pop", "no", "zip", "zotz", "tzec", "xul", "yoxkin", "mol", "chen", "yax", "zac", "ceh", "mac", "kankin", "muan", "pax", "koyab", "cumhu");
private static List diasTzolkin = Arrays.asList("imix", "ik", "akbal", "kan", "chicchan", "cimi", "manik", "lamat", "muluk", "ok", "chuen", "eb", "ben", "ix", "mem", "cib", "caban", "eznab", "canac", "ahau");

public static void main(String arg[]) {
MayaCanlendar my = new MayaCanlendar();
File f = new File("mayacalendar.in");
try {
my.bf = new BufferedReader(new FileReader(f));
try {
System.out.println(my.bf.readLine());
String registro = my.bf.readLine();
int day = 0, month = 0, year = 0;
while (registro != null) {
String[] componentes = registro.split(" ");
day = Integer.parseInt(componentes[0].substring(0, componentes[0].indexOf(".")));
month = mesesHaab.indexOf(componentes[1]);
year = Integer.parseInt(componentes[2]);
long allAsDays = day+(month * 20)+(year * 365);
System.out.println(((allAsDays%13)+1)+" "+diasTzolkin.get(Integer.valueOf(String.valueOf((allAsDays%20))))+" "+((allAsDays - (allAsDays % 260))/260));
registro = my.bf.readLine();
}
} catch (IOException ex) {
Logger.getLogger(MayaCanlendar.class.getName()).log(Level.SEVERE, null, ex);
}
} catch (FileNotFoundException ex) {
Logger.getLogger(MayaCanlendar.class.getName()).log(Level.SEVERE, null, ex);
}
}
}

GATTACA

Source file name: gattaca.c, gattaca.cpp or gattaca.java

The Institute of Bioinformatics and Medicine (IBM) of your country has been studying the
DNA sequences of several organisms, including the human one. Before analyzing the DNA of
an organism, the investigators must extract the DNA from the cells of the organism and decode
it with a process called “sequencing”.
A technique used to decode a DNA sequence is the “shotgun sequencing”. This technique is
a method applied to decode long DNA strands by cutting randomly many copies of the same
strand to generate smaller fragments, which are sequenced reading the DNA bases (A, C, G and
T) with a special machine, and re-assembled together using a special algorithm to build the
entire sequence.
Normally, a DNA strand has many segments that repeat two or more times over the sequence
(these segments are called “repetitions”). The repetitions are not completely identified by the
shotgun method because the re-assembling process is not able to differentiate two identical
fragments that are substrings of two distinct repetitions.
The scientists of the institute decoded successfully the DNA sequences of numerous bacterias
from the same family, with other method of sequencing (much more expensive than the shotgun
process) that avoids the problem of repetitions. The biologists wonder if it was a waste of
money the application of the other method because they believe there is not any large repeated
fragment in the DNA of the bacterias of the family studied.
The biologists contacted you to write a program that, given a DNA strand, finds the largest
substring that is repeated two or more times in the sequence.
Input
The first line of the input contains an integer T specifying the number of test cases (1>T<100).>n<1000).>

Sample input	Output for the sample input
56 GATTACA GAGAGAG GATTACAGATTACA TGAC TGTAC TTGGAACC	A 3 GAGAG 2 GATTACA 2 No repetitions found! T 2 A 2

Solucion

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
import java.util.logging.Level;
import java.util.logging.Logger;

public class gattacaV3 {

public static void main(String arg[]) {
File f = new File("gattaca.in");
try {
BufferedReader bf = new BufferedReader(new FileReader(f));
int numeroCasos = Integer.parseInt(bf.readLine());
String entrada = bf.readLine();
int testCase = 0;
while (entrada != null) {
String[] suffixes = getSuffixes(entrada);
String lrs = "";
int N = entrada.length(), repetitions = 2;
Map equalLength = new TreeMap();
for (int i = 0; i < N - 1; i++) {
String x = lcp(suffixes[i], suffixes[i + 1]);
if (x.length() > lrs.length()) {
lrs = x;
repetitions = 2;
equalLength = new TreeMap();
} else if (x.length() == lrs.length()) {
if (x.equals(lrs)) {
repetitions++;
equalLength.put(lrs, repetitions);
} else {
int currentCount = equalLength.get(x) != null ? equalLength.get(x) + 1 : 2;
if (equalLength.get(lrs) == null) {
equalLength.put(lrs, repetitions);
}
equalLength.put(x, currentCount);
}
}
}
String moreRepeated = "";
int maxRepetitions = 0;
for (Map.Entry entry : equalLength.entrySet()) {
if ("".equals(moreRepeated) || entry.getValue() > maxRepetitions) {
moreRepeated = entry.getKey();
maxRepetitions = entry.getValue();
}
}
if (!"".equals(moreRepeated)) {
lrs = moreRepeated;
repetitions = maxRepetitions;
}
if (!"".equals(lrs)) {
System.out.println(lrs + " " + repetitions);
} else {
System.out.println("No repetitions found!");
}
entrada = bf.readLine();
testCase++;
}
} catch (IOException ex) {
Logger.getLogger(gattaca.class.getName()).log(Level.SEVERE, null, ex);
}
}

public static String[] getSuffixes(String testCase) {
int N = testCase.length();
String[] suffixes = new String[N];
for (int i = 0; i < N; i++) {
suffixes[i] = testCase.substring(i, N);
}
Arrays.sort(suffixes);
return suffixes;
}

public static String lcp(String s, String t) {
int n = Math.min(s.length(), t.length());
for (int i = 0; i < n; i++) {
if (s.charAt(i) != t.charAt(i)) {
return s.substring(0, i);
}
}
return s.substring(0, n);
}
}