### 11296 - Counting Solutions to an Integral Equation

Posted:

**Mon Oct 01, 2007 3:45 am**I got WA with my code...can anyone give me some testcase please ?

thanks..

thanks..

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=38&t=22732

Page **1** of **1**

Posted: **Mon Oct 01, 2007 3:45 am**

I got WA with my code...can anyone give me some testcase please ?

thanks..

thanks..

Posted: **Mon Oct 01, 2007 4:03 am**

Input:
Output:

Code: Select all

```
0
1000000
```

Code: Select all

```
1
125000750001
```

Posted: **Mon Oct 01, 2007 5:52 am**

accepted now...thanks..

im so stupid..it's very easy problems..

im so stupid..it's very easy problems..

Posted: **Mon Oct 01, 2007 6:03 am**

Input:

1000

25

16

15

64

35

12

Output of my acc code:

125751

91

45

36

561

171

28

thanks

keep posting

sapnil cse sust.

1000

25

16

15

64

35

12

Output of my acc code:

125751

91

45

36

561

171

28

thanks

keep posting

sapnil cse sust.

Posted: **Sat Jan 19, 2008 7:56 pm**

I can't see how to solve this problem.

Any hint?

Any hint?

Posted: **Sat Jan 19, 2008 8:18 pm**

Hint.
-----

Rio

Code: Select all

```
x+2*y+2*z = x+2*(y+z)
```

Rio

Posted: **Sat Jan 19, 2008 11:35 pm**

Thanks Rio.

Your hint was very useful to me. I've solved the problem.

Your hint was very useful to me. I've solved the problem.

Posted: **Thu Jul 10, 2008 9:45 am**

my group partner discovered the solution.the solution will be n=n/2+1 and then the sum from 1 up to n,,,,,n*(n+1)/2

he simulated some test cases generated by "diophantine equation ".....and produce this.

but actually i dont understand.and the time limit for this problem is 6 sec!!!!!!!!.can anyone help me explaining how it comes.

Thanx in advance

he simulated some test cases generated by "diophantine equation ".....and produce this.

but actually i dont understand.and the time limit for this problem is 6 sec!!!!!!!!.can anyone help me explaining how it comes.

Thanx in advance

Posted: **Mon Dec 22, 2008 9:10 am**

x+2y+2z=n.

Lets simplify this equation.

2*(y+z)=n-x

We can realized that:

The value of right side of equation will be 0 to n.

// let n-x=k;

=> 2*(y+z)=k..........//k is 0 to n.

=> y+z=k/2.

Ok..........

calculate how many number from 0 to n are divisible by 2.

That means how many number are valid in right side.

that is n/2+1.

Now again in equation.

y+z=s...........//Value of s is 0 to n/2+1

now how many solution of that equation.

That is s*(s+1)/2.

Lets simplify this equation.

2*(y+z)=n-x

We can realized that:

The value of right side of equation will be 0 to n.

// let n-x=k;

=> 2*(y+z)=k..........//k is 0 to n.

=> y+z=k/2.

Ok..........

calculate how many number from 0 to n are divisible by 2.

That means how many number are valid in right side.

that is n/2+1.

Now again in equation.

y+z=s...........//Value of s is 0 to n/2+1

now how many solution of that equation.

That is s*(s+1)/2.

Posted: **Sun Dec 28, 2008 8:42 pm**

thanx mak(cse_DU) for ur explanation.

Posted: **Mon Nov 15, 2010 12:42 pm**

if u just precalculate for 1st few n such as for 2:

2 0 0 | 0 1 0 | 0 0 1 so total solution 3

for :3 1 1 0 |1 0 1 | 3 0 0 so total solution 3

its 4 : 2 1 0 | 2 0 1 | 0 1 1 | 4 0 0 | 0 2 0 | 0 0 2 | total is 6

for 5 :

for every x there will be x+1; and total is also 6

so solution is simple :

cut half of n and then sum up 1 to n/2+1;

2 0 0 | 0 1 0 | 0 0 1 so total solution 3

for :3 1 1 0 |1 0 1 | 3 0 0 so total solution 3

its 4 : 2 1 0 | 2 0 1 | 0 1 1 | 4 0 0 | 0 2 0 | 0 0 2 | total is 6

for 5 :

for every x there will be x+1; and total is also 6

so solution is simple :

cut half of n and then sum up 1 to n/2+1;

Posted: **Mon Feb 23, 2015 10:17 pm**

A technique useful for solving problems like this is to write a brute force solver O(n * n) and look for a pattern for small n.
This would probably TLE on the judge, but you can find the pattern and using 64 bit integers print (n / 2 + 1) * (n / 2 + 2) / 2.

Code: Select all

```
x = 0, y = 0, z = 0
n = 0 has 1 solution(s)
x = 1, y = 0, z = 0
n = 1 has 1 solution(s)
x = 0, y = 0, z = 1
x = 0, y = 1, z = 0
x = 2, y = 0, z = 0
n = 2 has 3 solution(s)
x = 1, y = 0, z = 1
x = 1, y = 1, z = 0
x = 3, y = 0, z = 0
n = 3 has 3 solution(s)
x = 0, y = 0, z = 2
x = 0, y = 1, z = 1
x = 0, y = 2, z = 0
x = 2, y = 0, z = 1
x = 2, y = 1, z = 0
x = 4, y = 0, z = 0
n = 4 has 6 solution(s)
x = 1, y = 0, z = 2
x = 1, y = 1, z = 1
x = 1, y = 2, z = 0
x = 3, y = 0, z = 1
x = 3, y = 1, z = 0
x = 5, y = 0, z = 0
n = 5 has 6 solution(s)
x = 0, y = 0, z = 3
x = 0, y = 1, z = 2
x = 0, y = 2, z = 1
x = 0, y = 3, z = 0
x = 2, y = 0, z = 2
x = 2, y = 1, z = 1
x = 2, y = 2, z = 0
x = 4, y = 0, z = 1
x = 4, y = 1, z = 0
x = 6, y = 0, z = 0
n = 6 has 10 solution(s)
x = 1, y = 0, z = 3
x = 1, y = 1, z = 2
x = 1, y = 2, z = 1
x = 1, y = 3, z = 0
x = 3, y = 0, z = 2
x = 3, y = 1, z = 1
x = 3, y = 2, z = 0
x = 5, y = 0, z = 1
x = 5, y = 1, z = 0
x = 7, y = 0, z = 0
n = 7 has 10 solution(s)
x = 0, y = 0, z = 4
x = 0, y = 1, z = 3
x = 0, y = 2, z = 2
x = 0, y = 3, z = 1
x = 0, y = 4, z = 0
x = 2, y = 0, z = 3
x = 2, y = 1, z = 2
x = 2, y = 2, z = 1
x = 2, y = 3, z = 0
x = 4, y = 0, z = 2
x = 4, y = 1, z = 1
x = 4, y = 2, z = 0
x = 6, y = 0, z = 1
x = 6, y = 1, z = 0
x = 8, y = 0, z = 0
n = 8 has 15 solution(s)
x = 1, y = 0, z = 4
x = 1, y = 1, z = 3
x = 1, y = 2, z = 2
x = 1, y = 3, z = 1
x = 1, y = 4, z = 0
x = 3, y = 0, z = 3
x = 3, y = 1, z = 2
x = 3, y = 2, z = 1
x = 3, y = 3, z = 0
x = 5, y = 0, z = 2
x = 5, y = 1, z = 1
x = 5, y = 2, z = 0
x = 7, y = 0, z = 1
x = 7, y = 1, z = 0
x = 9, y = 0, z = 0
n = 9 has 15 solution(s)
x = 0, y = 0, z = 5
x = 0, y = 1, z = 4
x = 0, y = 2, z = 3
x = 0, y = 3, z = 2
x = 0, y = 4, z = 1
x = 0, y = 5, z = 0
x = 2, y = 0, z = 4
x = 2, y = 1, z = 3
x = 2, y = 2, z = 2
x = 2, y = 3, z = 1
x = 2, y = 4, z = 0
x = 4, y = 0, z = 3
x = 4, y = 1, z = 2
x = 4, y = 2, z = 1
x = 4, y = 3, z = 0
x = 6, y = 0, z = 2
x = 6, y = 1, z = 1
x = 6, y = 2, z = 0
x = 8, y = 0, z = 1
x = 8, y = 1, z = 0
x = 10, y = 0, z = 0
n = 10 has 21 solution(s)
```