Problem:


Score : 1000 points

Problem Statement

In a two-dimensional plane, we have a rectangle R whose vertices are (0,0), (W,0), (0,H), and (W,H), where W and H are positive integers.
Here, find the number of triangles \Delta in the plane that satisfy all of the following conditions:

Each vertex of \Delta is a grid point, that is, has integer x- and y-coordinates.

\Delta and R shares no vertex.

Each vertex of \Delta lies on the perimeter of R, and all the vertices belong to different sides of R.

\Delta contains at most K grid points strictly within itself (excluding its perimeter and vertices).

Constraints

1 \leq W \leq 10^5

1 \leq H \leq 10^5

0 \leq K \leq 10^5

Input

Input is given from Standard Input in the following format:

W H K

Output

Print the answer.

Sample Input 1

2 3 1

Sample Output 1

12

For example, the triangle with the vertices (1,0), (0,2), and (2,2) contains just one grid point within itself and thus satisfies the condition.

Sample Input 2

5 4 5

Sample Output 2

132

Sample Input 3

100 100 1000

Sample Output 3

461316



Sample input:
2 3 1


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys


def count_h(y1, y2, w):
    n = y1 * (w + 1)
    if y2 == y1:
        n += (w + 1)
    else:
        n += int((y2 - y1 + 1) * (w + 1) / 2 + 1)
    return n - 2


def count_xy(x, y):
    return int(((x+1) * (y+1) + 1) / 2) + 1 - 2


def test_count():
    assert count_xy(1, 1) == 1
    assert count_xy(1, 2) == 2
    assert count_xy(2, 2) == 4
    assert count_h(0, 0, 3) == 2
    assert count_h(0, 1, 3) == 3
    assert count_h(0, 2, 3) == 5
    assert (3*4) - count_xy(1, 1) - count_xy(1, 1) - count_h(2, 2, 2) - 3 == 0

def count_k(w, h, k):
    result = 0
    for x1 in range(1, w+1):
        count = 0
        for y1 in range(1, h+1):
            for y2 in range(y1, h+1):
                dot = (1+w) * (1+h) - count_xy(x1, y1) - count_xy(w-x1, y2) - count_h(h-y1, h-y2, w) - 3
                if dot == k:
                    #print([x1, 0], [0, y1], [w, y2], "match")
                    count = count + 1 if y1 == y2 else count + 2
                else:
                    #print([x1, 0], [0, y1], [w, y2], "not", dot)
                    assert dot >= 0
            for x2 in range(x1, w+1):
                dot = (1+w) * (1+h) - count_xy(x1, y1) - count_xy(x2, h-y2) - count_h(w-x1, w-x2, h) - 3
                if dot == k:
                    #print([x1, 0], [0, y1], [w, y2], "match")
                    count = count + 1 if x1 == x2 else count + 2
                else:
                    #print([x1, 0], [0, y1], [w, y2], "not", dot)
                    assert dot >= 0
        if w/2 != x1:
            count *= 2
        result += count
    return result


w, h, k = map(int, sys.stdin.readline().split())
print(count_k(w, h, k))

Submission status: Wrong Answer

Solution code:
1

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
readline = sys.stdin.buffer.readline
def main():
  r=0
  w,h,k=map(int,readline().split())
  for a in range(1,w):
    for b in range(1,h):
      for c in range(1,w):
        s=(h-b)*a+b*a+b*c
        if s<=2*(k+h):
          r+=1
  for a in range(1,h):
    for b in range(1,w):
      for c in range(1,h):
        s=(w-b)*a+b*a+b*c
        if s<=2*k:
          r+=1
  print(r*2)         
main()

Submission status: Wrong Answer

Solution code:
import math

w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:

                pc = (w-1)*(c-1) - ((w-a-1)*(c-1)-math.gcd(w-a, c)+1)/2 - ((a-1)*(b-1)-math.gcd(a, b)+1)/2
                if pc <=k:
                    count =count +2
            else:
                pc = (w-1)*(c-1) - ((w-a-1)*(c-1)-math.gcd(w-a, c)+1)/2 - ((a-1)*(b-1)-math.gcd(a, b)+1)/2 - ((w-1)*(c-b-1)-math.gcd(w, c-b)+1)/2


                if pc <=k:
                    count =count +4

w2 = w
w =h
h=w2

for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:

                pc = (w-1)*(c-1) - ((w-a-1)*(c-1)-math.gcd(w-a, c)+1)/2 - ((a-1)*(b-1)-math.gcd(a, b)+1)/2
                if pc <=k:
                    count =count +2
            else:
                pc = (w-1)*(c-1) - ((w-a-1)*(c-1)-math.gcd(w-a, c)+1)/2 - ((a-1)*(b-1)-math.gcd(a, b)+1)/2 - ((w-1)*(c-b-1)-math.gcd(w, c-b)+1)/2


                if pc <=k:
                    count =count +4



print(count)

Submission status: Wrong Answer

Solution code:
w,h,k = (int(x) for x in input().split())

w -= 1
h -= 1
a = w * h * w 
b = h * w * h

print((a+b)*2)

Submission status: Wrong Answer

Solution code:
w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(1,h,1):

            pc =0
            for x in range(1,h,1):
                for y in range(1,w,1):
                    if y<a+a/c*x and y>a-a/b*x and x< (c-b)/w*y+b:

                        pc =pc+1

            if pc <=k:
                count =count +2

w2 = w
w =h
h=w2

for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(1,h,1):

            pc =0
            for x in range(1,h,1):
                for y in range(1,w,1):
                    if y<a+a/c*x and y>a-a/b*x and x< (c-b)/w*y+b:

                        pc =pc+1
            if pc <=k:
                count =count +2



print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+math.gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

w2 = w
w =h
h=w2



for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+math.gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+math.gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

w2 = w
w =h
h=w2



for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+math.gcd(w, c-b)-1)/2)
      
                if pc <=k:
                    count =count +4

print(count)

Submission status: Runtime Error

Solution code:
from fractions import gcd
w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

w2 = w
w =h
h=w2



for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

print(count)

Submission status: Runtime Error

Solution code:
from functions import gcd

w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

w2 = w
w =h
h=w2



for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

print(count)

Submission status: Runtime Error

Solution code:
from functions import gcd

w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

w2 = w
w =h
h=w2



for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

print(count)

Submission status: Runtime Error

Solution code:
import math

w, h, k = map(int, input().split())

count =0


for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+math.gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

w2 = w
w =h
h=w2



for a in range(1,w,1):
    for b in range(1,h,1):
        for c in range(b,h,1):

            if b==c:
                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2)
                if pc <=k:
                    count =count +2
            else:

                pc = (w-1)*(c-1) - int(((w-a-1)*(c-1)+math.gcd(w-a, c)-1)/2) - int(((a-1)*(b-1)+math.gcd(a, b)-1)/2) - int(((w-1)*(c-b-1)+math.gcd(w, c-b)-1)/2)

                if pc <=k:
                    count =count +4

print(count)

Submission status: Runtime Error

Solution code:
from math import gcd

input1 = input().split()
W = int(input1[0])
H = int(input1[1])
K = int(input1[2])

def NumOfGrid(tup1: list, tup2: list):
    return gcd((abs(tup1[0]-tup2[0]), abs(tup1[1]-tup2[1]))) -1

def Sur(p1, p2, p3):
    p22 = [(p2[0]-p1[0]), (p2[1]-p1[1])]
    p23 = [(p3[0]-p1[0]), (p3[1]-p1[1])]
    return abs(p22[0]*p23[1] - p23[0]*p22[1])/2

def Koshiten(p1:list, p2: list, p3: list):
    return int(Sur(p1,p2,p3)-(NumOfGrid(p1, p2)+NumOfGrid(p2,p3)+NumOfGrid(p3,p1)-3)-1)

def Triangles(p1,p2,p3,K):
    if Koshiten(p1,p2,p3) <= K:
        return True
    else:
        return False

Result = 0

for a in range(2, H):
    p1 = [0, a]
    for b in range(2,W):
        p2 = [b, H]
        for c in range(2, W):
            p3 = [c, 0]
            if Triangles(p1,p2,p3,K) == True:
                Result += 1
        for c in range(2, H):
            p3 = [W, c]
            if Triangles(p1,p2,p3,K) == True:
                Result += 1
print(Result)

Submission status: Runtime Error

Solution code:
W, H, K = list(map(int,input().split()))

counter = int(0)
triangle_counter = 0

if (W <= 2 or H == 1):
  print(0)
else:
  for i in range(1, H):
    for j in range(1, W):
      for k in range(j, W):
        counter = 0
        if (j == k): # 三角形の1辺がy軸と垂直
          for l in range(1,j):
            counter += int((H-float(i))/float(k)*l+float(i)/float(j)*l)
          if(counter <= K):
            triangle_counter +=2
        else: # j < k
          for m in range(1,j):
            counter += int((H-float(i))/float(k)*m+float(i)/float(j)*m)
          for n in range (j, W):
            counter += int((H-float(i))/float(k)*n+i-H*n/(float(k)-float(j)-H*j/(1+j)))
          if(counter == K):
            triangle_counter += 4
  print(triangle_counter)

Submission status: Runtime Error

Solution code:
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
x=a-b
y=abs(x)
if v*t>=(y+w*t):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
fgf