A place where a program beginner is likely to trip.
Double loop without duplication.
I arbitrarily define this type of problem as the upper right triangle problem
w
ABC133B Difficulty:137 It is difficult to understand the problem if there are subscripts ... For the time being, I can't imagine it even if it's called D dimension, so I imagine it in 2 dimensions. In short ① Calculate all combinations of distances between two different points ② Whether each distance is an integer If you look up k
If you code the full search of the upper right triangle (5 rows * 5 columns), it looks like this
test.py
for i in range(5):
for j in range(i+1,5):
#Distance calculation
i is the 0th line (A line), the 1st line (B line), the 2nd line (C line), the 3rd line (D line), and the 4th line (E line).
When i is 0, j is range (1,5)
→ 1,2,3,4
When i is 1, j is range (2,5)
→ 2,3,4
When i is 2, j is range (3,5)
→ 3,4
When i is 3, j is range (4,5)
→ 4
When i is 4, j is range (5,5)
→ none, so nothing is processed.
⇨ Firmly ** You can search all 10 places (4 + 3 + 2 + 1 + 0) of the triangle (yellow part!) ** on the upper right!
If you can understand this, no matter what the upper right triangle problem comes, "I'm not afraid of anything anymore"
This is easy.
%1==0
or is_integer
I think it doesn't matter which one. I'm not good at English, so I use the former.
①+② In summary, it looks like this
test.py
def LI(): return list(map(int,input().split()))
N,D = LI()
X = [LI() for _ in range(N)]
_ans = 0
for i in range(N):
for j in range(i+1,N):
temp = 0
for k in range(D):
temp += (X[j][k]-X[i][k])**2
if temp**0.5%1==0:
_ans += 1
print(_ans)
I think that the place where temp = 0
is described will become intuitive if you manage the number of problems.
The formula for the distance between two points is to remember junior high school mathematics!
I think this will deepen your understanding. Number of AOJ (ITP1_7_B) combinations
Like this~
test.py
def LI(): return list(map(int,input().split()))
while 1:
n,x = LI()
if n==x==0:
break
_ans = 0
for i in range(1,n+1):
for j in range(i+1,n+1):
for k in range(j+1,n+1):
if i+j+k==x:
_ans += 1
print(_ans)
It's not the main subject of this article, but if you talk about the extras,
k = x-i-j (k condition: 1 <= k <= n and j <k)
By setting it, you can solve it with a double for statement! !! !!
** (Added on 2020/05/07) ** Currently, the problem of the above triple for statement Write code using ʻitertools.combinations`! Click here for details! [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22]
** (Added on May 26, 2020) **
--Full search of the upper right triangle
- itertools.combinations(range(N),2)
--Full search of upper right triangle + shaded area
- itertools.combinations_with_replacement(range(N),2)
It will be. ʻItertools.combinations_with_replacement` is a duplicate combination! !! !!
end!
Recommended Posts