https://math.stackexchange.com/questions/2138051/how-many-squares-is-passing-the-diagonal

Edited by author 16.09.2020 22:50

I have correctly performed all tests from the forum, but still WA 3. Please tell me what the problem is or write new tests for me.

//pseudo code
divider = first_input-1;
dividend = second_input-1;
result: divider + dividend - FindCrossesOnTheWay(dividend,divider)
*FindCrossesOnTheWay
if(divider < dividend) swap()
for(i=1;i<=divider;i++)
if((dividend * i) % divider == 0) crosses++

For each x (x=0,1,2,..,n-1) (x is horizontal axis)  find y0=x*tg(a) and y1=(x+1)*tg(a),  where tg(a) is (m-1)/(n-1).  Add to answer floor (y1) - floor(y0) +1. If y1 is a whole number then subtract 1 from answer.

I wrote simple implementation but can't figure out test to prove my solution wrong.

4 3 -> 4
3 3 -> 2
4 5 -> 6
4 6 -> 7
3 8 -> 8
6 5 -> 8
6 8 -> 10

#include "stdio.h"
#include <stdlib.h>

int main(void) {
  int bigger, lesser, a, b;
  scanf("%d", &a);
  scanf("%d", &b);
  if (a >= b) {
    bigger = a - 1; lesser = b - 1;
  } else {
    bigger = b - 1; lesser = a - 1;
  }

  if (bigger % lesser == 0) {
    printf("%d\n", bigger); return 0;
  }

  printf("%d\n", bigger + lesser - 1);

  return 0;
}

I use Python 3.5
Is it right that it's prohibited to import function gcd from library math?
But it's allowed to import this function from library fractions

Edited by author 27.11.2015 02:04

for input 3 3, I guess the result should be 3. Why it is 2?

For whom who use floating K = n / m, try to this test:
3 99  - right answer is 98
99 3  - right answer is 98

4 3 - 4
3 3 - 2

Is it not true 4 3 - 6, 3 3 - 3?

i used bresenham line drawing algorithm :)) together with gcd()

What is test 8?
What input ?

Edited by author 13.11.2009 15:02

Edited by author 13.11.2009 15:02

Does anybody know what is test #3?

Well, this is for those who didnt get the method.
Consider N: no of rows of blocks M: no of columns of the blocks (N+1 and M+1 are the input).
Crosspoint here refers to a point where a horizontal and a vertical line meet.

For each line that the plane intersects, a new block is introduced. Consider the south western most point also as one such point. No of horizontal lines intersected=N. No of vertical lines intersected=M. But the southwestern most point has been counted twice and it introduces the same first block.
If gcd(M,N)==1, there is no intermediate point where the line passes over a crosspoint. Hence no. of blocks = M+N-1.
If gcd(M,N)!=1, the whole grid can be split horizontally at
the points where the line passes over a crosspoint and each of them can be considered separately with that cross point as the south westernmost point of the subproblem. There are gcd(M,N) such points. Say a=gcd(M,N). Then in each subproblem  the line flies over M/a+N/a-1 blocks. Totally the line flies over a*(M/a+N/a-1) blocks. ie. M+N-a blocks.

Edited by author 29.11.2007 02:42

If the plane fly across a edge and it will produce a point then produce a new block so the answer add one.
If gcd(M, N) = 1, it means there is no situation that the plane fly across the crossroads.
See from left to right it produce M point and see from north to south it produce N point,
but one is calculate twice, so there are M + N - 1 points and Ans is M + N - 1.

Use
inter:=trunc(r*i+0.0000001)-trunc(r*(i-1)-0.0000001);
instead of
inter:=trunc(r*i)-trunc(r*(i-1));

I had the same problem as you. By the way, on my computer I
couldn't find a test where your program would give the
result that differs from the result of my program, and I
can't explain why do we have to use those 0.0000001. By the
way, see problem 1030 - if you try to submit it, you will
face similar problems...

Good luck!