QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#820775 | #3168. Letter Wheels | umd-red# | AC ✓ | 1985ms | 92144kb | Java11 | 5.6kb | 2024-12-19 01:37:03 | 2024-12-19 01:37:04 |
Judging History
answer
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* Java equivalent of the provided Kotlin code.
* This program reads three strings and attempts to find the minimal spread
* of shift positions (x, y) such that the combined hash of the shifted strings equals zero.
*/
public class H {
public static void main(String[] args) throws IOException {
// Initialize BufferedReader for efficient input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// Initialize Random with current time in milliseconds
Random random = new Random(System.currentTimeMillis());
// Read the three input strings
String s = br.readLine().trim();
String t = br.readLine().trim();
String u = br.readLine().trim();
// Ensure all strings have the same length
int n = s.length();
if (t.length() != n || u.length() != n) {
throw new IllegalArgumentException("All strings must have the same length.");
}
// Generate random weights for each position
long[] weights = new long[n];
for (int i = 0; i < n; i++) {
weights[i] = random.nextLong();
}
// Define the hash function
// It calculates the sum of (value * weight) for each character in the string
// 'A' -> 1, 'B' -> 2, 'C' -> -3
// Throws an exception for unknown characters
HashFunction hashFunction = new HashFunction(weights);
long sHash = hashFunction.hash(s);
// Precompute all possible shifted hashes for t and u
long[] tShifts = new long[n];
for (int shift = 0; shift < n; shift++) {
String tShifted = rotateString(t, shift);
tShifts[shift] = hashFunction.hash(tShifted);
}
long[] uShifts = new long[n];
for (int shift = 0; shift < n; shift++) {
String uShifted = rotateString(u, shift);
uShifts[shift] = hashFunction.hash(uShifted);
}
// Initialize the answer to a large value (5 * n as in the Kotlin code)
int answer = 5 * n;
// Iterate over all possible shift positions for t and u
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
// Check if the combined hash equals zero
if (sHash + tShifts[x] + uShifts[y] == 0L) {
// Create a list of shift positions including the fixed position 0
List<Integer> sorted = new ArrayList<>(Arrays.asList(0, x, y));
Collections.sort(sorted);
// Iterate to find the minimal spread considering the circular nature
for (int i = 0; i < 3; i++) {
// Calculate the spread between the maximum and minimum shift positions
int currentSpread = sorted.get(2) - sorted.get(0);
answer = Math.min(answer, currentSpread);
// Rotate the list by adding n to the first element and removing it
int first = sorted.remove(0) + n;
sorted.add(first);
Collections.sort(sorted);
}
}
}
}
// If no valid shifts are found, print -1. Otherwise, print the minimal spread.
if (answer == 5 * n) {
System.out.println(-1);
} else {
System.out.println(answer);
}
}
/**
* Rotates a string to the left by the specified number of positions.
*
* @param str The original string.
* @param shift The number of positions to rotate.
* @return The rotated string.
*/
private static String rotateString(String str, int shift) {
if (shift == 0) {
return str;
}
return str.substring(shift) + str.substring(0, shift);
}
/**
* Helper class to handle hashing of strings based on character values and weights.
*/
static class HashFunction {
private final long[] weights;
/**
* Constructor to initialize the weights.
*
* @param weights An array of weights corresponding to each position in the strings.
*/
public HashFunction(long[] weights) {
this.weights = weights;
}
/**
* Calculates the hash of a given string based on predefined character values and weights.
*
* @param string The input string to hash.
* @return The calculated hash value.
* @throws IllegalArgumentException If an unknown character is encountered.
*/
public long hash(String string) {
long result = 0L;
for (int j = 0; j < string.length(); j++) {
char letter = string.charAt(j);
long value;
switch (letter) {
case 'A':
value = 1L;
break;
case 'B':
value = 2L;
break;
case 'C':
value = -3L;
break;
default:
throw new IllegalArgumentException("Unknown letter: " + letter);
}
result += value * weights[j];
}
return result;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 126ms
memory: 54320kb
input:
ABC ABC ABC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 126ms
memory: 57188kb
input:
ABBBAAAA BBBCCCBB CCCCAAAC
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 123ms
memory: 58956kb
input:
AABB BBCC ACAC
output:
-1
result:
ok single line: '-1'
Test #4:
score: 0
Accepted
time: 1985ms
memory: 92144kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 312ms
memory: 88396kb
input:
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 367ms
memory: 88972kb
input:
ABBBCCACACBCBACCBBCCBACBBBABAABBCAACCABBBACABAACABBCAAACACABACAACACCBCABBABBCBBCCABBCCABCCACBCCCBABABAACAAACCCCBACCABBAACCAABCABBABAAABACBAABABCABAAACABAAACABBCBCACABACBBBBBBCCABBACAAAACBAAACABCABABBBABBAABACABABCCBCCBAAAABBCACACABBCABCAAAABABAAACBCCAAABCABBBAACBABBBACBBBCBCAABCCCCBBACCBABABBAAACAAB...
output:
911
result:
ok single line: '911'
Test #7:
score: 0
Accepted
time: 359ms
memory: 89672kb
input:
AACABBCACCCBABAACCBBACAAAACABCCCCCCAABBCACACBAACBBBCCBAABBCBAABCABBAABCABAACBBABBAAABBAACACBAACBBACAABCAACBCBCACBACAABCCBBACACCABCCCCCCCCACABBBCBCBBACACCBACCBCAACACAABABACCAACCCAABBBABCCCACBCBAACAACCCBAAABBCCCBBABBBBBABAACAACCABCAABCCABBAABCBACBAABBBACCBAABBCAAACACCCCCCCBBAAABBCBBCCACCAAACBABCCAABBB...
output:
465
result:
ok single line: '465'
Test #8:
score: 0
Accepted
time: 390ms
memory: 88516kb
input:
CBCBAABCCCABBACCBABCAABBCACBBBCABCCAABCCCABBCACAAAACACBCBCCCCBCBBCCCBACCAABABACCABCBCCBBCCAACABCCABBBBBABACCBCBABCACCCCCBBCBAABABBCACBCABBCAAAACBABCCACABABCBABABBCAABABCCAACABCBBBBCABCAAABCABCAACBBBBBCBBCAABCBACABACBBCAACBCBCCABBCABBACCBBABCBABBCCCBBCABABAACBBBACCCACBAAAACCCBACACAACBACABACCCCBACCCCA...
output:
861
result:
ok single line: '861'
Test #9:
score: 0
Accepted
time: 308ms
memory: 89084kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2612
result:
ok single line: '2612'
Test #10:
score: 0
Accepted
time: 328ms
memory: 89332kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2189
result:
ok single line: '2189'
Test #11:
score: 0
Accepted
time: 346ms
memory: 88436kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
1519
result:
ok single line: '1519'
Test #12:
score: 0
Accepted
time: 336ms
memory: 90276kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2546
result:
ok single line: '2546'
Test #13:
score: 0
Accepted
time: 310ms
memory: 90620kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2319
result:
ok single line: '2319'
Test #14:
score: 0
Accepted
time: 321ms
memory: 88232kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2505
result:
ok single line: '2505'
Test #15:
score: 0
Accepted
time: 344ms
memory: 89180kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2474
result:
ok single line: '2474'
Test #16:
score: 0
Accepted
time: 351ms
memory: 88620kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2993
result:
ok single line: '2993'
Test #17:
score: 0
Accepted
time: 109ms
memory: 55020kb
input:
ACCCCBBB BBBACCCC BAAABAAA
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 167ms
memory: 57932kb
input:
CBBACBBAABAACCCBACCCBABAABBCABCABBACABBAAAAAACABCBCCACCABACBAAAAABBBABCCCBCBCACACACABBCBCACAAACCAABCCBCACABCBABBABBCBCCCACABCCBBCBCAACABBACCBCBCABABAAABACBBAAACACACBBACBBCACACACBCAAAABBCCBCBCCCBBBCBABCBBCACCCABBAACBACABAABBCABCBAACBCAABBBCACAAABAAABCBABACACBAAAABCAABACCABAAAACBCCBBCAAABABCABBAACCACC...
output:
183
result:
ok single line: '183'
Test #19:
score: 0
Accepted
time: 336ms
memory: 89488kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
1332
result:
ok single line: '1332'