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);
}
}

Rotating Rings

Any square grid can be viewed as one or more rings, one inside the other. For example, as shown in figure (a), a 5 * 5 grid is made of three rings, numbered 1,2 and 3 (from outside to inside.) A square grid of size N is said to be sorted, if it includes the values from 1 to N2 in a row-major order, as shown in figure (b) for N = 4. We would like to determine if a given square grid can be sorted by only rotating its rings. For example, the grid in figure (c) can be sorted by rotating the first ring two places counter-clockwise, and rotating the second ring one place in the clockwise direction.
Input
Your program will be tested on one or more test cases. The first input line of a test case is an integer N which is the size of the grid. N input lines will follow, each line made of N integer values specifying the values in the grid in a row-major order. Note than 0 < N ≤ 1, 000 and grid values are natural numbers less than or equal to 1,000,000.

The end of the test cases is identified with a dummy test case with N = 0.
Output
For each test case, output the result on a single line using the following format:

k._result

Where k is the test case number (starting at 1,) _ is a single space, and result is "YES" or "NO" (without the double quotes.)
Sample Input

4
9 5 1 2
13 7 11 3
14 6 10 4
15 16 12 8
3
1 2 3
5 6 7
8 9 4
0

Sample Output

1. YES
2. NO



SOLUCION



import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

/**
*
* @author Luis Carlos
*/
public class rings {

private BufferedReader bf = null;

public rings() {
}

public static void main(String arg[]) {
rings e = new rings();
try {
File f = new File("C:/Users/Luis Carlos/Documents/NetBeansProjects/Maraton/src/rings.in");
e.bf = new BufferedReader(new FileReader(f));
String orden = e.bf.readLine();
int numeroLinea = 1;
while (orden != null && !orden.equals("0")) {
int[][] matriz = new int[Integer.parseInt(orden)][Integer.parseInt(orden)];
for (int i = 0; i < Integer.parseInt(orden); i++) {
String[] sp = e.bf.readLine().split(" ");
for (int j = 0; j < Integer.parseInt(orden); j++) {
matriz[i][j] = Integer.parseInt(sp[j]);
}
}
if (e.isRotatingRing(e.generarAnillos(matriz, matriz.length), e.generarAnillos(null, matriz.length))) {
System.out.println(numeroLinea++ + ". YES");
} else {
System.out.println(numeroLinea++ + ". NO");
}
orden = e.bf.readLine();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}

public ArrayList<Integer>[] generarAnillos(int[][] matriz, int orden) {
ArrayList<Integer>[] anillos = null;
try {
int n = orden, numeroAnillos = (n + 1) / 2;
anillos = new ArrayList[numeroAnillos];
for (int i = 0; i < numeroAnillos; i++) {
anillos[i] = new ArrayList<Integer>();
}
for (int k = 0; k < numeroAnillos; ++k) {
for (int j = k; j < n - k; ++j) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(k, j, n));
} else {
anillos[k].add(matriz[k][j]);
System.out.println("Anillo " + k + " " + matriz[k][j]);
}
}
for (int i = k + 1; i <= n - k - 2; ++i) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(i, n - k - 1, n));
} else {
anillos[k].add(matriz[i][n - k - 1]);
System.out.println("Anillo " + k + " " + matriz[i][n - k - 1]);
}
}
for (int j = n - k - 1; j >= k; --j) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(n - k - 1, j, n));
} else {
anillos[k].add(matriz[n - k - 1][j]);
System.out.println("Anillo " + k + " " + matriz[n - k - 1][j]);
}
}
for (int i = n - k - 2; i > k; --i) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(i, k, n));
} else {
anillos[k].add(matriz[i][k]);
System.out.println("Anillo " + k + " " + matriz[i][k]);
}
}
}
if (n % 2 != 0) {
anillos[numeroAnillos - 1].remove(anillos[numeroAnillos - 1].size() - 1);
}
} catch (Exception e) {
e.printStackTrace();
} finally {
return anillos;
}
}

public int getElementoPosicion(int i, int j, int n) {
return i * n + j + 1;
}

public boolean isRotatingRing(ArrayList<Integer>[] real, ArrayList<Integer>[] referencia) {
boolean rotatingRing = true;
for (int i = 0; i < referencia.length; i++) {
ArrayList<Integer> arrayList = referencia[i];
ArrayList<Integer> auxiliarComparacion = new ArrayList<Integer>();
if (real[i].contains(arrayList.get(0))) {
auxiliarComparacion.addAll(real[i].subList(real[i].indexOf(arrayList.get(0)), real[i].size()));
auxiliarComparacion.addAll(real[i].subList(0, real[i].indexOf(arrayList.get(0))));
if (!arrayList.equals(auxiliarComparacion)) {
rotatingRing = false;
break;
}
} else {
rotatingRing = false;
break;
}
}
return rotatingRing;
}
}

Electronic Document Security

The Tyrell corporation uses a state-of-the-art electronic document system that controls all aspects of document creation, viewing, editing, and distribution. Document security is handled via access control lists (ACLs). An ACL defines a set of entities that have access to the document, and for each entity defines the set of rights that it has. Entities are denoted by uppercase letters; an entity might be a single individual or an entire division. Rights are denoted by lowercase letters; examples of rights are a for append, d for delete, e for edit, and r for read.

The ACL for a document is stored along with that document, but there is also a separate ACL log stored on a separate log server. All documents start with an empty ACL, which grants no rights to anyone. Every time the ACL for a document is changed, a new entry is written to the log. An entry is of the form ExR, where E is a nonempty set of entities, R is a nonempty set of rights, and x is either "+", "–", or "=". Entry E+R says to grant all the rights in R to all the entities in E, entry E–R says to remove all the rights in R from all the entities in E, and entry E=R says that all the entities in E have exactly the rights in R and no others. An entry might be redundant in the sense that it grants an entity a right it already has and/or denies an entity a right that it doesn't have. A log is simply a list of entries separated by commas, ordered chronologically from oldest to most recent. Entries are cumulative, with newer entries taking precedence over older entries if there is a conflict.

Periodically the Tyrell corporation will run a security check by using the logs to compute the current ACL for each document and then comparing it with the ACL actually stored with the document. A mismatch indicates a security breach. Your job is to write a program that, given an ACL log, computes the current ACL.

Input: The input consists of one or more ACL logs, each 3–79 characters long and on a line by itself, followed by a line containing only "#" that signals the end of the input. Logs will be in the format defined above and will not contain any whitespace.

Output: For each log, output a single line containing the log number (logs are numbered sequentially starting with one), then a colon, then the current ACL in the format shown below. Note that (1) spaces do not appear in the output; (2) entities are listed in alphabetical order; (3) the rights for an entity are listed in alphabetical order; (4) entities with no current rights are not listed (even if they appeared in a log entry), so it's possible that an ACL will be empty; and (5) if two or more consecutive entities have exactly the same rights, those rights are only output once, after the list of entities.

Example input:	Example output:
MC-p,SC+c YB=rde,B-dq,AYM+e GQ+tju,GH-ju,AQ-z,Q=t,QG-t JBL=fwa,H+wf,LD-fz,BJ-a,P=aw #	1:CSc 2:AeBerMeYder 3: 4:BHJfwLPaw

Solucion: eds.java



import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;

public class eds {

private BufferedReader bf = null;

public eds() {
}

public static void main(String arg[]) {
eds e = new eds();
try {
File f = new File("eds.in");
e.bf = new BufferedReader(new FileReader(f));
String linea = e.bf.readLine();
int numeroLinea = 0;
while (linea != null && !linea.equals("#")) {
Map<String, String> permisos = new LinkedHashMap<String, String>();
String[] sp = linea.split(",");
for (int i = 0; i < sp.length; i++) {
if (sp[i].indexOf("-") >= 0) {
String[] prs = sp[i].split("-");
for (int j = 0; j < prs[0].length(); j++) {
permisos.put(String.valueOf(prs[0].charAt(j)), e.retirarPermisos((String) permisos.get(String.valueOf(prs[0].charAt(j))), prs[1]));
}
}
if (sp[i].indexOf("+") >= 0) {
String[] prs = new String[2];
prs[0] = sp[i].substring(0, sp[i].indexOf("+"));
prs[1] = sp[i].substring(sp[i].indexOf("+") + 1);
for (int j = 0; j < prs[0].length(); j++) {
permisos.put(String.valueOf(prs[0].charAt(j)), e.agregarPermisos((String) permisos.get(String.valueOf(prs[0].charAt(j))), prs[1]));
}
}
if (sp[i].indexOf("=") >= 0) {
String[] prs = sp[i].split("=");
for (int j = 0; j < prs[0].length(); j++) {
permisos.put(String.valueOf(prs[0].charAt(j)), prs[1]);
}
}
}
System.out.println((numeroLinea++ + 1) + ":" + e.listadoEntidadesPermisos(permisos).replace("null", ""));
linea = e.bf.readLine();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}

public String getOrdenada(String cadena) {
String res = "";
char[] sb = cadena.toCharArray();
for (int k = 0; k < sb.length; k++) {
for (int i = 0; i < sb.length - 1; i++) {
if (sb[i] > sb[i + 1]) {
char tmp = sb[i];
sb[i] = sb[i + 1];
sb[i + 1] = tmp;
}
}
}
for (int i = 0; i < sb.length; i++) {
res += sb[i];
}
return res;
}

public String retirarPermisos(String cadena, String permisos) {
String cadenaRetorno = cadena;
if (cadena != null) {
for (int i = 0; i < permisos.length(); i++) {
cadenaRetorno = cadenaRetorno.replace(String.valueOf(permisos.charAt(i)), "");
}
} else {
cadenaRetorno = "";
}
return cadenaRetorno;
}

public String agregarPermisos(String cadena, String permisos) {
String cadenaRetorno = cadena;
if (cadena != null) {
for (int i = 0; i < permisos.length(); i++) {
if (!cadenaRetorno.contains(String.valueOf(permisos.charAt(i)))) {
cadenaRetorno += String.valueOf(permisos.charAt(i));
}
}
} else {
cadenaRetorno = permisos;
}
return cadenaRetorno;
}

public String listadoEntidadesPermisos(Map<String, String> permisos) {
String permisosRetorno = "";
String[] prm = new String[permisos.keySet().size()];
permisos.keySet().toArray(prm);
ordenarArray(prm);
String permisoAnterior = "";
ArrayList<Mapeo> maps = new ArrayList<Mapeo>();
for (int i = 0; i < prm.length; i++) {
if (!permisos.get(prm[i]).equals("")) {
if (getOrdenada(permisoAnterior).equals(getOrdenada(permisos.get(prm[i])))) {
Mapeo mp = maps.get(maps.size() - 1);
mp.setEntidades(mp.getEntidades().append(prm[i]));
} else {
Mapeo mp = new Mapeo();
mp.setPermisos(permisos.get(prm[i]));
mp.setEntidades(new StringBuffer(prm[i]));
maps.add(mp);
permisoAnterior = permisos.get(prm[i]);
}
}
}
for (Mapeo aux : maps) {
permisosRetorno += aux.getEntidades().toString() + getOrdenada(aux.getPermisos());
}
return permisosRetorno;
}

public void ordenarArray(String[] prm) {
String tmp;
for (int k = 0; k < prm.length; k++) {
for (int i = 0; i < prm.length - 1; i++) {
if (prm[i].compareTo(prm[i + 1]) > 0) {
tmp = prm[i];
prm[i] = prm[i + 1];
prm[i + 1] = tmp;
}
}
}

}
}

class Mapeo {

private StringBuffer entidades;
private String permisos;

public Mapeo() {
}

public Mapeo(StringBuffer entidades, String permisos) {
this.entidades = entidades;
this.permisos = permisos;
}

public StringBuffer getEntidades() {
return entidades;
}

public void setEntidades(StringBuffer entidades) {
this.entidades = entidades;
}

public String getPermisos() {
return permisos;
}

public void setPermisos(String permisos) {
this.permisos = permisos;
}
}

100 The 3n + 1 problem

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then
5. else
6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no operation overflows a 32-bit integer.

The Output
For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input
1 10
100 200
201 210
900 1000

Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

Referencia http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

SOLUCIÓN POSIBLE (este codigo da Wrong answer)

import java.io.*;

/**
*
* @author dthomas
*/
class Main {

public static int longitud;
public static int mayor;

public static int longitudNumero(int num) {
if (num == 0) {
return 0;
}
int contador = 1;
while (num != 1) {
if (num % 2 != 0) {
num = num * 3 + 1;
} else {
num = num / 2;
}
contador = contador + 1;
}
return contador;
}

public static int MaxLongitud(int i, int j) {
int inf, sup;
mayor = 0;
if (i > j) {
inf = j;
sup = i;
} else {
sup = j;
inf = i;
}
for (int k = inf; k <= sup; k++) {
int lon = longitudNumero(k);
if (lon > mayor) {
mayor = lon;
}
}
return mayor;
}

public static void main(String a[]) {
FileReader fr;
try {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String linea = bf.readLine();
String valores[];
int num1, num2;
while ((linea != null)) {
valores = linea.split(" ");
if (valores.length == 2) {
num1 = Integer.parseInt(valores[0]);
num2 = Integer.parseInt(valores[1]);
System.out.println(num1 + " " + num2 + " " + MaxLongitud(num1, num2));
}
linea = bf.readLine();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} catch (Exception e) {
e.printStackTrace();
}
System.exit(0);
}
}