The most important idea for this task is the fact that according to Lagrange’s Four Square Theorem, every natural number can be written as the sum of squares of four non-negative integers. Good luck, hope this will help! Edited by author 13.11.2021 00:26 Edited by author 13.11.2021 00:26 I don't understand problem,please give me some tests.Thank!!!!!! Here are some tests ~~~~~~~~~~~~ 11995=3 11996=4 11997=3 11998=3 11999=4 12000=3 12001=3 12002=2 12003=3 ~~~~~~~~~~~~~~ 23402=2 23403=3 23404=3 23405=3 23406=3 23407=4 23408=4 23409=1 23410=2 23411=3 ~~~~~~~~~~~~~~ 59989=3 59990=3 59991=4 59992=3 59993=2 59994=3 59995=3 59996=4 59997=3 59998=3 59999=4 60000=3 We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you! We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you! Well... For n=72... what are the possible squares you can take? You can take 64,49,36,25...4,1 . So what's the best result for 72? The best result Best(72)=min(Best(72-64),Best(72-49),Best(72-36), ... Best(72-1))+1; Now whats the base cases? U see, for all square numbers, u can take it in one go. So Best(1)=Best(4)=Best(9)=Best(16) ... = 1 Its a top down approach. I hope u got the idea... Goodluck. Btw, I'm wondering how u solved by Theorem on the sum of four squares. Can u send your code to my mail please? ealham86@gmail.com i solved it with dp. but i wondered with u.plz send me ur code. EMAIL:achowdhury@isrt.ac.bd I am getting a WA at test #5 Here's my code : #include <iostream> using namespace std; int main(){ int n,i=1,count=0; cin>>n; while(n>0){ if(i*i<=n) i++; else{ n-=(i-1)*(i-1); i=1; count++; } } cout<<count<<endl; return 0 } Imagine you are given the following input: n=72. Given that 72 = 6*6 + 6*6 the answer should be 2, but your output is 3. This is happening because you are solving the problem using a greedy strategy. Here a greedy strategy does not work. If you want more information on why this technique does not work read chapter 15 and 16 of "Introduction to algorithms" by Cormen,Leiserson,Rivest and Stein. Thanks for the explanation... ^_^ 60000 Edited by author 05.10.2016 10:30 Hi I got WA on test 10 |: I need some testcase! PLZ HELLLLLP MEEEE! :D #include <iostream> #include <cmath> using namespace std; int minCoins(int coins[], int m, int V) { int table[V+1];
table[0] = 0;
for (int i=1; i<=V; i++) table[i] = INT_MAX;
for (int i=1; i<=V; i++) { for (int j=0; j<m; j++) if (coins[j] <= i) { int subResult = table[i-coins[j]]; if (subResult != INT_MAX && subResult + 1 < table[i]) table[i] = subResult + 1; } } return table[V]; } int main() { int V; cin>>V; int coins[1000]; int i;
for(i=1;i<=sqrt(V);i++) { coins[i-1] = (i)*(i); } int m = sqrt(V); cout<< minCoins(coins, m, V)<<endl; return 0; } This problem can be translated to get the minimum amout of coins to get the value N.(We must just check that the coins are the actual square numbers). i write the output and the square roots. Input 41 Answer 2 16 25 Input 51 Answer 3 1 1 49 Input 19 Answer 3 1 9 9 Input 102 Answer 3 1 1 100 Input 18467 Answer 3 25 6561 11881 Input 6334 Answer 3 25 225 6084 Input 26500 Answer 2 256 26244 Input 19169 Answer 2 400 18769 Input 15724 Answer 3 36 1764 13924 Input 11478 Answer 3 4 25 11449 Input 29358 Answer 3 4 5329 24025 Input 26962 Answer 2 1681 25281 Input 24464 Answer 3 64 64 24336 Input 5705 Answer 3 4 225 5476 Input 28145 Answer 2 256 27889 Input 23281 Answer 3 9 7396 15876 Input 16827 Answer 3 49 5329 11449 Input 9961 Answer 3 16 144 9801 There can be any solution but the number of square roots is unique Wheres my wrong? help pleas #include <bits/stdc++.h> const int maxn = (int)1e6; const int mod = (int)1e9 + 7; using namespace std; int n; int dp[maxn]={-1}; int calc(int n){ int res=n; dp[0]=0; if(dp[n] != -1) return dp[n]; for(int i=1; i*i <= n; i++){ res=min(res,1+calc(n-i*i)); } return dp[n]=res; }
int main(){ scanf("%d",&n); printf("%d\n", calc(n));
return 0; } Edited by author 20.12.2015 23:27 Edited by author 11.10.2015 17:44 #include <iostream> #include <cmath> #include <algorithm> using namespace std; int function(int n) { if (n == 1) return 1; else if (n == 0) return 0; else{
int k = 999999999; for (int i = 1; i <= sqrt(n); i++) { int a = function(n - i*i); if (a < k ) k = min(k, a); } return function(k) + 1;
}
} int main() { int n; cin >> n; cout << function(n) << endl; } use memoization Thank you Noob, I got an AC with your help. One optimization No need to start loop from always from 1 , sqrt(N)/2 is enough ;) thing why?. :) my code: #include<iostream> #include<cmath> using namespace std; main() { unsigned int n,temp,nc; cin>>n; nc=n; temp=sqrt(n); if(n==0) cout<<0; else if(temp*temp==n) cout<<1; else { unsigned int x=-1,m=0,q=4,t; for(unsigned int i=temp;i>=1;i--) { t=i; while(x!=0) { x=n-t*t; n=x; t=sqrt(x); m++; } if(m<q) q=m; if(m==2) break; x=-1; m=0; n=nc; } cout<<q; } } Use Brute Force approach with Lagrange's four square theorem, but to short-cut do check only 1, 2, 3 case. If those do not give any squares then output 4 (see Lagrange's theorem). :) Of course, Dynamic Programming solution is better. But for your info there is a theorem of Lagrange. Quote from Wikipedia "Lagrange's four-square theorem states that any natural number can be represented as the sum of four integer squares" http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem Example, 3 = 1^2 + 1^2 + 1^2 + 0^2 31 = 5^2 + 2^2 + 1^2 + 1^2 310 = 17^2 + 4^2 + 2^2 + 1^2. Here is my C# code: using System; class Program { static void Main() { int n = int.Parse(Console.ReadLine()); for (int i1 = 0; i1 <= (int)Math.Sqrt(n); i1++) for (int i2 = 0; i2 <= (int)Math.Sqrt(n); i2++) for (int i3 = 0; i3 <= (int)Math.Sqrt(n); i3++) for (int i4 = 0; i4 <= (int)Math.Sqrt(n); i4++) if (i1 * i1 + i2 * i2 + i3 * i3 + i4 * i4 == n) { Console.WriteLine(Math.Sign(i1)+Math.Sign(i2)+Math.Sign(i3)+Math.Sign(i4)); return; } } } Hello i wrote the following code in python , but it takes too much time, hwo should it be improved class timus1073: def __init__(self): pass def problem(self,y): a = [0] + range(1,60001) b = [x**2 for x in range(1,246)] for i in b: j = 0 while j+i <= 60000: if (a[j+i] > a[j] + 1): a[j+i] = a[j] + 1 j = j + 1 return a[y] if __name__ == "__main__": p = timus1073() a = input() print p.problem(int(a)) var fi,fv:text; chi,kolc: longint; procedure round_sqrt(a:longint; var kol:longint); var b:longint; begin b:=trunc(sqrt(a)); b:=b*b; a:= a-b; if a> 0 then begin kol:=kol+1; round_sqrt(a,kol); end else kol:=kol+1; end; begin assign(fi,'input.txt'); reset(fi); assign(fv,'output.txt'); rewrite(fv); {============} read(fi,chi); kolc:=0; if chi>0 then round_sqrt(chi,kolc); write(fv,kolc); {============} close(fi); close(fv); end. Don't use files. Only standart streams. var i,j,k,n:longint; begin read(n); for i:=1 to 250 do if sqr(i)=n then begin write(1); exit; end; for i:=1 to 250 do for j:=1 to 250 do if sqr(i)+sqr(j)=n then begin write(2); exit; end; for i:=1 to 250 do for j:=1 to 250 do for k:=1 to 250 do if sqr(i)+sqr(j)+sqr(k)=n then begin write(3); exit; end; write(4); end. If N was bigger, you would have time limit. I don't think so. My code got AC. #include<stdio.h> int i,j,k; long int n; int main() { scanf("%d",&n);
for(i=1;(i*i)<=n;i++) if((i*i)==n) { printf("%d",1); return 0; } for(i=1;i*i<=n;i++) for(j=1;j*j<=n;j++) if((i*i+j*j)==n) { printf("%d",2); return 0; }
for(i=1;i*i<=n;i++) for(j=1;j*j<=n;j++) for(k=1;k*k<=n;k++) if((i*i+j*j+k*k)==n) { printf("%d",3);
return 0; }
printf("%d",4); return 0;
} But this solution is bad. I think it's DP in this problem O(n*sqrt(n)); for(i=1;(i*i)<=n;i++) if((i*i)==n) { printf("%d",1); return 0; } you can just write if (sqrt(n) * sqrt(n) == n) this is the most epic answer I've read....hhhh :) u are awesome thanks dud and good luck My program 4729094 got AC, but the same program gives WA2 on problem 1593 (harder tests). So, there is a class of numbers those my solution gives incorrect answer and I think some of such numbers must be below 60000 2nd test of problem 1593 was added to the test set Could you tell me case for Text 14.Thank You Could you give me case for 14.Thank you. Could you give me case for test 14? Thank you! |
|