Квадратная задача

[Акоб]

Здравствуйте люди.Трудно себе представить квадратных людей.Но следущая задача утверждает, что они есть.Затрудняюсь обьяснить задачу и поэтому прошу прочитать ее здесь http://acm.timus.ru/problem.aspx?space=1&num=1073.

#include<iostream>
#include<cmath>


using namespace std;

int main()
{
	int N, j = 0, x = 0, d = 0;
        cin>>N;

	if( N < 0 || N > 60000 )
	{
		return 0;
		cout<<x;
	}

	if( N == 0 )
	{
		cout<<x;
		return 0;
	}
	while(N >= 0)
	{
															
		
		if( j * j >= N )
			{	
			if( j * j == N)
			{
				x++;
				cout<<x;
				return 0;
			}

			N = N - (j - 1) * (j - 1);
			j = 0;
			x++;
			continue;
		}
		j++;
	}
	cout<<x;
	return 0;
}

это код который написал я, но для некоторых чисел он показывает неправельний ответ.
181 = 10^2 + 9^2 ответ 2, а у меня показывает 5.
что я должен добавить или как должен написать код, чтобы он работал бы праеильно?
Заранее благодарен.

[Obey-Kun]

Короче, я так понял, надо разложить число на минимальное число квадратов и вывести их количество.

if( N < 0 || N > 60000 )
{
return 0;
cout<<x;
}

По-хорошему, это ошибка. Во-первых, сначала cout, а потом return. Но вообще, тут правильней использовать следующее:

assert(N >= 0 && N <= 60000);

И лишние объявления (можно ведь их сделать позже).

Мне задача показалась интересной. Читать твой код дальше не стал и сделал сам... сейчас сделаю...

upd: блин, а ведь задача не так проста, как кажется. Вот например 381. Это 10^2 + 10^2 + 9^2. Тут или перебором надо, или рекурсией...

upd2: вот тебе: http://accepted.shoutwiki.com/wiki/%...quare_country)

[Акоб]

На пребор времени нет.На время задачи дается 1 секунда.
вот и он

#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; 
   
    
}

[Obey-Kun]

Я тебе дал ссылку на решение. Суть такова: идём от 1 квадрика и считаем минимальное кол-во сертификатов.

[Д_М]

Сообщение от Obey-Kun

Но вообще, тут правильней использовать следующее:

assert(N >= 0 && N <= 60000);

Не согласен, пользовательский ввод надо проверять всегда, assert в релизе (-DNDEBUG) не сработает.

Правильней

if(N<0 || N> 60000) {
  cerr << "Invalid input\n";
  return 1;
}

[Obey-Kun]

Правда ваша. Не отлаживаем же.

[boomeer]

Динамика, решение за O(n*sqrt(n))
Вот мой код, но на яве. В обсуждении есть на плюсах.

import java.io.*;
import java.math.*;
import java.util.*;
import static java.lang.Math.*;

public class Timus_1073 implements Runnable {
	
	StreamTokenizer tok;
	BufferedReader in;
	PrintWriter out;
	boolean timus = System.getProperty("ONLINE_JUDGE") != null;
	
	void init() throws IOException {
		if (timus) {
			in = new BufferedReader(new InputStreamReader(System.in));
			tok = new StreamTokenizer(in);
			out = new PrintWriter(System.out);
		} else {
			in = new BufferedReader(new FileReader("input.txt"));
			tok = new StreamTokenizer(in);
			out = new PrintWriter("output.txt");
		}
	}
	
	int readInt() throws IOException {
		tok.nextToken();
		return (int) tok.nval;
	}
	
	String readString() throws IOException {
		tok.nextToken();
		return tok.sval;
	}
	
	public static void main(String[] args) {
		new Thread(new Timus_1073()).start();
	}
	
	@Override
	public void run() {
		try {
			if (timus) {
				init();
				solve();
				out.flush();
			} else {
				long t1 = System.currentTimeMillis();
				init();
				solve();
				out.close();
				long t2 = System.currentTimeMillis();
				System.out.println(t2 - t1);
			}
		} catch(IOException e) {
			System.exit(1);
		}
	}
	
	void solve() throws IOException {
		int n = readInt();
		int[] d = new int[n + 1];
		Arrays.fill(d, Integer.MAX_VALUE / 3);
		d[0] = 0;
		for (int k = 1; k * k <= n; k++) {
			for (int i = k * k; i <= n; i++) {
				d[i] = min(d[i], d[i - k * k] + 1);
			}
		}
		out.println(d[n]);
	}
	
}

Акоб, какой ник? На тимусе

[Акоб]

Ten**
что-то большой код.
обьясни как ты зделал.

[kaljan775]

а если взять корень от этого числа, отбросить дробную часть, вычесть, взять корень, отбросить дробную часть - и так пока не будет минимума ?

[Акоб]

sqt(181) = 13
sqrt(13) = 3
sqrt(3) = 1
так?
правельный ответ 2