| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Some tips | irinaguseva | 1073. Квадратная страна | 13 ноя 2021 00:26 | 1 |
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 |
| Please give me some tests.Thank in advance!!!! | Search | 1073. Квадратная страна | 13 май 2021 16:11 | 2 |
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 |
| How could we solve this problem by DP? | HowieMa | 1073. Квадратная страна | 29 мар 2020 14:23 | 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 |
| WA at test#5 | Gopesh Tulsyan | 1073. Квадратная страна | 5 окт 2016 10:30 | 5 |
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 |
| WA test 10 |: | havij4 | 1073. Квадратная страна | 29 июл 2016 10:33 | 2 |
Hi
I got WA on test 10 |:
I need some testcase!
PLZ HELLLLLP MEEEE! :D |
| Same as the Coin Change Problem | Erik Arakelyan(AUA) | 1073. Квадратная страна | 17 июн 2016 15:08 | 1 |
#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). |
| Tests and answers. | Grandmaster | 1073. Квадратная страна | 11 фев 2016 18:04 | 1 |
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 |
| Help anybody | ELDVN | 1073. Квадратная страна | 20 дек 2015 23:22 | 1 |
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 |
| Test 4 Wrong Answer | mihai.alpha | 1073. Квадратная страна | 11 окт 2015 17:36 | 1 |
Edited by author 11.10.2015 17:44 |
| How to make this code faster?? Please, help | Najmaddin Akhundov | 1073. Квадратная страна | 12 июл 2015 10:39 | 4 |
#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; } 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?. :) |
| WA14 pls help | moshcode | 1073. Квадратная страна | 16 дек 2014 16:01 | 1 |
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;
}
} |
| Hint | Marius Žilėnas | 1073. Квадратная страна | 24 окт 2013 16:46 | 1 |
Hint Marius Žilėnas 24 окт 2013 16:46 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). :) |
| Lagrange's four-square theorem and its implementation with AC solution in C# | Hikmat Ahmedov | 1073. Квадратная страна | 24 окт 2013 15:37 | 2 |
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; } } } |
| 1073 - square country | gogreen | 1073. Квадратная страна | 22 апр 2013 22:15 | 1 |
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)) |
| why i have WA#1 | alexdeg | 1073. Квадратная страна | 30 мар 2013 13:16 | 2 |
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. |
| easy search | Artem Ladik | 1073. Квадратная страна | 8 фев 2013 11:25 | 6 |
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 |
| Weak tests? | hatred [Ivanovo SPU] | 1073. Квадратная страна | 20 янв 2013 02:00 | 2 |
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 |
| can anyone send me solution of this question? please ! (my mail is: erzhan_jktl@mail.ru) | Erzhan Shaniev | 1073. Квадратная страна | 3 янв 2013 08:38 | 2 |
Could you tell me case for Text 14.Thank You |
| WA 14!!!! | Toy | 1073. Квадратная страна | 3 янв 2013 08:11 | 1 |
Could you give me case for 14.Thank you. |
| WA 14 | Irina | 1073. Квадратная страна | 1 ноя 2012 19:28 | 1 |
WA 14 Irina 1 ноя 2012 19:28 Could you give me case for test 14? Thank you! |
