Break through in 8 and a half minutes. As a hint, I tried to solve it quickly with the division quadrature method. I was worried about how many sections should be divided, but if I did it properly with 4096, the accuracy was good with the first shot. Came out, so I submitted it and it was safe AC.
a, b = map(int, input().split())
x = a
result = 0
t = 1 / 4096
while x < b:
result += abs((x - a) * (x - b) * t)
x += t
print(result)
Break through in 41 minutes. I wrote a code that processes integers and was wondering why I didn't AC. It's too stupid. Fold the short one vertically and horizontally to the limit, and then fold the long one to the limit. ..
x, y, h = map(int, input().split())
if x < y:
x, y = y, x
x *= 1000
y *= 1000
result = 0
while y > h:
y /= 2
h *= 2
result += 1
while x > h:
x /= 2
h *= 2
result += 1
print(result)
It can also be processed as an integer, as long as the numbers change relatively correctly.
x, y, h = map(int, input().split())
if x < y:
x, y = y, x
x *= 1000
y *= 1000
result = 0
while y > h:
x *= 2
h *= 4
result += 1
while x > h:
y *= 2
h *= 4
result += 1
print(result)
Lost. If you DP obediently, it will be * O * (* N * 2 </ sup> d), so TLE. If you think carefully, you will reach the i stage id .. i-1 stage, i + The first step is the same except for i --d + 1 .. i and the two ends. If so, * O * (1) can be used instead of * O * (* d ). It became * O * ( N * 2 </ sup>) and was solved.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func main() {
N := readInt()
d := readInt()
K := readInt()
buf0 := make([]int, d*N+K+1)
buf1 := make([]int, d*N+K+1)
buf0[0] = 1
for i := 0; i < N; i++ {
t := 0
for j := 0; j < d; j++ {
t += buf0[j]
t %= 1000000007
buf1[j] = t
}
for j := d; j < (i+1)*d; j++ {
t -= buf0[j-d]
if t < 0 {
t += 1000000007
}
t += buf0[j]
t %= 1000000007
buf1[j] = t
}
buf0, buf1 = buf1, buf0
}
fmt.Println(buf0[K-N])
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
#AC for PyPy
N, d, K = map(int, input().split())
buf0 = [0] * (d * N + K + 1)
buf1 = [0] * (d * N + K + 1)
buf0[0] = 1
for i in range(N):
t = 0
for j in range(d):
t += buf0[j]
t %= 1000000007
buf1[j] = t
for j in range(d, (i + 1) * d):
t -= buf0[j - d]
t += buf0[j]
t %= 1000000007
buf1[j] = t
buf0, buf1 = buf1, buf0
print(buf0[K - N])
Recommended Posts