Return to problem list2019-qual Problem C
Final solution
func start() {
var t int
mustReadLineOfInts(&t)
for i := 0; i < t; i++ {
stdout.WriteString("Case #")
stdout.WriteString(strconv.Itoa(i + 1))
stdout.WriteString(": ")
test()
}
}
type PrimeList []*big.Int
func (pl *PrimeList) Len() int {
return len(*pl)
}
func (pl *PrimeList) Less(i int, j int) bool {
return (*pl)[i].Cmp((*pl)[j]) < 0
}
func (pl *PrimeList) Swap(i int, j int) {
(*pl)[i], (*pl)[j] = (*pl)[j], (*pl)[i]
}
func (pl PrimeList) SearchFor(i *big.Int) int {
res := sort.Search(len(pl), func(idx int) bool {
return pl[idx].Cmp(i) >= 0
})
if pl[res].Cmp(i) != 0 {
debug(fmt.Sprintf("Warning: searched for %v, found index = %v, pl[index] = %v which does not equal the query.", i.Text(10), res, pl[res].Text(10)))
}
return res
}
func test() {
zero := big.NewInt(0)
var L int
line := strings.Split(mustReadLine(), " ")
L = mustAtoi(line[1])
cipherText := make([]*big.Int, 0, L)
line = strings.Split(mustReadLine(), " ")
if len(line) != L {
panic("length mismatch.")
}
primesFound := make(PrimeList, 0)
for _, numStr := range line {
bn, success := big.NewInt(0).SetString(numStr, 10)
if !success {
panic("!")
}
cipherText = append(cipherText, bn)
}
problematicProducts := make([]*big.Int, 0)
firstNonProblematicCipherIndex := -1
lastNonProblematicCipherIndex := -1
for k := 0; k < L-1; k++ {
if cipherText[k].Cmp(cipherText[k+1]) == 0 {
problematicProducts = append(problematicProducts, cipherText[k])
continue
}
if firstNonProblematicCipherIndex == -1 {
firstNonProblematicCipherIndex = k
}
lastNonProblematicCipherIndex = k + 1
p := big.NewInt(0).GCD(nil, nil, cipherText[k], cipherText[k+1])
primesFound = append(primesFound, p)
}
firstPrimeFound := primesFound[0]
lastPrimeFound := primesFound[len(primesFound)-1]
var firstPrime *big.Int = nil
if firstNonProblematicCipherIndex%2 == 0 {
firstPrime = big.NewInt(0).Div(cipherText[firstNonProblematicCipherIndex], firstPrimeFound)
} else {
firstPrime = firstPrimeFound
}
lastPrime := big.NewInt(0).Div(cipherText[lastNonProblematicCipherIndex], lastPrimeFound)
primesFound = append(primesFound, firstPrime, lastPrime)
buffer := big.NewInt(0)
buffer2 := big.NewInt(0)
for _, prod := range problematicProducts {
for _, primeToTry := range primesFound {
buffer, m := buffer.DivMod(prod, primeToTry, buffer2)
if m.Cmp(zero) == 0 {
q := big.NewInt(0).Set(buffer)
primesFound = append(primesFound, q)
break
}
}
}
sort.Sort(&primesFound)
last := zero
nPrimesFound := make(PrimeList, 0)
for _, p := range primesFound {
if p.Cmp(last) != 0 {
nPrimesFound = append(nPrimesFound, p)
last = p
}
}
primesFound = nPrimesFound
if len(primesFound) != 26 {
debug("Warning: not exactly 26 primes! Got " + strconv.Itoa(len(primesFound)))
}
lastDecrypted := primesFound.SearchFor(firstPrime)
stdout.WriteByte('A' + byte(lastDecrypted))
for _, c := range cipherText {
buffer := buffer.Div(c, primesFound[lastDecrypted])
t := primesFound.SearchFor(buffer)
lastDecrypted = t
stdout.WriteByte('A' + byte(t))
}
stdout.WriteByte('\n')
}
func encrypt(primes []int, msg string) []int {
nums := make([]int, 0, len(msg))
for _, char := range msg {
if char-'A' > 26 {
continue
}
nums = append(nums, primes[char-'A'])
}
c := make([]int, 0, len(msg)-1)
for i := 0; i < len(nums)-1; i++ {
c = append(c, nums[i]*nums[i+1])
}
return c
}
Sample test cases given in question
2
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543
Other files
func encrypt(primes []int, msg string) []int {
nums := make([]int, 0, len(msg))
for _, char := range msg {
if char-'A' > 26 {
continue
}
nums = append(nums, primes[char-'A'])
}
c := make([]int, 0, len(msg)-1)
for i := 0; i < len(nums)-1; i++ {
c = append(c, nums[i]*nums[i+1])
}
return c
}
func main() {
fin, err := os.OpenFile("generated.in", os.O_WRONLY|os.O_CREATE, 0666)
if err != nil {
panic(err)
}
fout, err := os.OpenFile("generated.out", os.O_WRONLY|os.O_CREATE, 0666)
if err != nil {
panic(err)
}
in := bufio.NewWriter(fin)
out := bufio.NewWriter(fout)
t := 1000000
N := 10000
in.WriteString(strconv.Itoa(t))
in.WriteByte('\n')
for i := 0; i < t; i++ {
in.WriteString(strconv.Itoa(N))
in.WriteByte(' ')
L := rand.Intn(100) + 25
in.WriteString(strconv.Itoa(L))
in.WriteByte('\n')
out.WriteString("Case #")
out.WriteString(strconv.Itoa(i + 1))
out.WriteString(": ")
primesList := []int{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}
msg := make([]rune, 0, L+1)
for i := 0; i < len(primesList); i++ {
msg = append(msg, 'A'+rune(i))
}
for i := len(msg); i < L+1; i++ {
idx := rand.Intn(26)
msg = append(msg, 'A'+rune(idx))
}
rand.Shuffle(len(msg), func(i, j int) {
msg[i], msg[j] = msg[j], msg[i]
})
out.WriteString(string(msg))
out.WriteByte('\n')
for i := 0; i < len(msg)-1; i++ {
prod := primesList[byte(msg[i])-'A'] * primesList[byte(msg[i+1])-'A']
if i != 0 {
in.WriteByte(' ')
}
in.WriteString(strconv.Itoa(prod))
}
in.WriteByte('\n')
}
out.Flush()
in.Flush()
}