QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#820775#3168. Letter Wheelsumd-red#AC ✓1985ms92144kbJava115.6kb2024-12-19 01:37:032024-12-19 01:37:04

Judging History

This is the latest submission verdict.

  • [2024-12-19 01:37:04]
  • Judged
  • Verdict: AC
  • Time: 1985ms
  • Memory: 92144kb
  • [2024-12-19 01:37:03]
  • Submitted

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

详细

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'