Sunday, June 30, 2013

Codeforces Round #188 (Div. 2) B Strings of Power

// Codeforces Round #188 (Div. 2) B Strings of Power

import java.io.*;
import java.util.*;

//Codeforces
public class Codeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException {
String s = in.nextString();
long cnt = 0;
ArrayList<Integer> heavyPos = new ArrayList<Integer>();
ArrayList<Integer> metalPos = new ArrayList<Integer>();
int fromIndex = 0;
while (fromIndex < s.length()) {
int pos = s.indexOf("heavy", fromIndex);
if (pos == -1)
break;
else {
heavyPos.add(pos);
fromIndex = pos + 5;
}
}
fromIndex = 0;
while (fromIndex < s.length()) {
int pos = s.indexOf("metal", fromIndex);
if (pos == -1)
break;
else
metalPos.add(pos);
fromIndex = pos + 5;
}
HashMap<Integer, Integer> firstMetalPosLargerThanHeavyPos = new HashMap<Integer, Integer>();
int lastMetalIdx = 0;
for (int i = 0; i < heavyPos.size(); i++) {
int hpos = heavyPos.get(i);
firstMetalPosLargerThanHeavyPos.put(hpos, -1);
for (int j = lastMetalIdx; j < metalPos.size(); j++) {
if (metalPos.get(j) > heavyPos.get(i)) {
firstMetalPosLargerThanHeavyPos.put(hpos, metalPos.get(j));
lastMetalIdx = j;
break;
}
}
}

HashMap<Integer, Integer> cntMetalsLargerThanPos = new HashMap<Integer, Integer>();
for (int i = 0; i < metalPos.size(); i++) {
int pos = metalPos.get(i);
cntMetalsLargerThanPos.put(pos, metalPos.size() - 1 - i);
}

for (int i = 0; i < heavyPos.size(); i++) {
int hpos = heavyPos.get(i);
int firstMetalLarger = firstMetalPosLargerThanHeavyPos.get(hpos);
if (firstMetalLarger < 0)
continue;
long cntMetalLarger = cntMetalsLargerThanPos.get(firstMetalLarger);
cnt += cntMetalLarger + 1;
}

out.println(cnt);
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (cname != null)
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
} else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
} else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException {
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

No comments:

Post a Comment