UAS Pemrograman Lanjut 2025

1. Bilangan Maja

Ada 45 pilihan dua digit pertama yang jumlah digitnya genap dan 45 yang ganjil. Ada 25 bilangan prima pada 00–99, termasuk 02, sehingga untuk N≥4 jumlahnya (45×100 + 45×25)×10^(N−4) = 5625×10^(N−4). Dua kelompok awal genap dan ganjil ini saling lepas, jadi tidak menghitung kondisi ganda dua kali.

MOD = 9973
t = int(input())
for _ in range(t):
    n = int(input())
    print(5625 * pow(10, n - 4, MOD) % MOD)

N=4 menghasilkan 5625; N=5 menghasilkan 56250 mod 9973 = 6385.

2. Segmen berpotongan di interior

Hanya pasangan horizontal dan vertikal dapat memiliki tepat satu titik yang berada di interior keduanya. Jika horizontal (x1,y)-(x2,y) dan vertikal (x,y1)-(x,y2), syaratnya ketat x1 < x < x2 dan y1 < y < y2; tanda ketat mengecualikan ujung. Segmen sejajar yang bersinggungan di ujung tidak masuk, sedangkan yang overlap mempunyai lebih dari satu titik.

import sys
v = list(map(int, sys.stdin.buffer.read().split()))
it = iter(v)
n, q = next(it), next(it)
segments = [tuple(next(it) for _ in range(4)) for _ in range(n)]
def intersects(a, b):
    if a[1] == a[3] and b[0] == b[2]:
        h, vert = a, b
    elif b[1] == b[3] and a[0] == a[2]:
        h, vert = b, a
    else:
        return False
    return h[0] < vert[0] < h[2] and vert[1] < h[1] < vert[3]
for _ in range(q):
    query = tuple(next(it) for _ in range(4))
    print(sum(intersects(s, query) for s in segments))

Batas N,Q≤1000 menjadikan O(NQ) memadai; memori O(N). Data diasumsikan terurut seperti jaminan soal.

3. Memaksimalkan jumlah peserta

Setiap hasil adalah prefix tak kosong dari teks yang sama. Pilih posisi p sebagai awal salah satu bagian terpanjang. Teks bersama dapat diperpanjang menjadi seluruh suffix s[p:]; setiap bagian yang valid tetap merupakan prefix suffix itu. Karena posisi p bagian terpanjang pasti termasuk dalam semua posisi input, mencoba setiap suffix sudah mencakup suatu solusi optimum.

Untuk setiap kandidat suffix, dp[i] menyimpan jumlah maksimum bagian yang dapat memisahkan s[i:]. Jika kesamaan awal s[i:] dan kandidat sepanjang l, coba semua panjang 1 sampai l; simpan ujung yang memberi 1 + dp[i+panjang] terbesar. Keadaan yang tidak dapat dipisah diberi nilai negatif. Telusuri kembali pilihan terbaik untuk mencetak posisi 1-based.

s = input().strip()
n = len(s)
best_count, best_starts = -1, []

for p in range(n):
    dp = [-1] * (n + 1)
    nxt = [-1] * n
    dp[n] = 0
    for i in range(n - 1, -1, -1):
        length = 0
        while i + length < n and p + length < n and s[i + length] == s[p + length]:
            length += 1
        for size in range(1, length + 1):
            if dp[i + size] >= 0 and 1 + dp[i + size] > dp[i]:
                dp[i] = 1 + dp[i + size]
                nxt[i] = i + size
    if dp[0] > best_count:
        best_count = dp[0]
        best_starts = []
        i = 0
        while i < n:
            best_starts.append(i + 1)
            i = nxt[i]

print(best_count)
print(*best_starts)

Kode mengasumsikan masukan tidak kosong seperti format soal. Untuk tiap kandidat ada O(n²) pemeriksaan karakter dan transisi; waktu terburuk O(n³), memori O(n). Naskah tidak mencantumkan batas panjang, sehingga kesesuaian waktunya untuk input sangat besar tidak dapat dipastikan. Contoh aab dapat dipisah menjadi a | ab: kandidat suffix ab memperlihatkan mengapa teks bersama tidak harus dimulai dengan seluruh string gabungan.