Квадратная страна

@odip · Регистрация: 17.06.2009

http://acm.timus.ru/problem.as... &locale=ru

В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок.
Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 × 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», — сказал он. Сделка состоялась.
Найдите, какое количество квадратных свидетельств он получил.
Исходные данные
В единственной строке стоит положительное число N ≤ 60 000 — число квадриков, которое было у жителя.

Результат
В единственной строке стоит число свидетельств, полученных в результате сделки.

Пример:
INPUT
344
OUTPUT
3

@outoftime · 08.01.2010, 16:06

Не по теме:

сейчас камп будет занят, я пока поразмышляю над задачей, напишу потом

@Delphin_KKC · 08.01.2010, 16:22

Интересная задача.

Алгоритм решения

0)переменной, в которой будет число участков (у меня - k), присваиваем ноль
1)берём квадратный корень из числа имеющихся квадриков
2)округляем результат вниз до целого
3)возводим результат в квадрат
4)отнимаем результат от числа квадриков
5)k++;
6)повторяем п.п. 1-5 до тех пор, пока деньги не кончатся

Код программы. Вариант с While

C++

#include <iostream>
#include <math.h>
 
using namespace std;
 
int main(int argc, char *argv[])
{
    int N;
    cout << "N=";
    cin>>N;
    int k=0;
    while (N>0) 
    {
    N-=static_cast<int>(pow(floor(sqrt(N)),2));
    k++;      
    }
    cout<<"\nK="<<k;
    system("PAUSE");
    return EXIT_SUCCESS;
}

Код программы. Вариант с For

C++

#include <iostream>
#include <math.h>
 
using namespace std;
 
int main(int argc, char *argv[])
{
    int N;
    cout << "N=";
    cin>>N;
    int k;
    for(k=0;N > 0;k++) N-=static_cast<int>(pow(floor(sqrt(N)),2));
    cout<<"\nK="<<k;
    system("PAUSE");
    return EXIT_SUCCESS;
}

В программе я использовал консольный ввод/вывод. Если нужно из файла - переделывайте.
Работоспособность кода проверена на приведённом в первом посте примере и для случая когда квадрик только 1.
Использовал DevCPP 4.9.9.2

@odip · 08.01.2010, 16:58 **[ТС]**

Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена.
Ты забываешь что это олимпиадные задачи.
А значит всегда есть над чем подумать.

А именно - приведенный тобой алгоритм находит какое-то разбиение на квадраты.
А нужно найти разбиение чтобы число квадратов было минимально.

Добавлено через 3 минуты
Вот тебе тест:
N=18
Правильный ответ: 2 ( 9+9 )
Твоя программа выводит 3 ( видимо 16+1+1 )

@Delphin_KKC · 08.01.2010, 17:53

Сообщение от odip

Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена.
Ты забываешь что это олимпиадные задачи.
А значит всегда есть над чем подумать.
...

Потому и написал что задача интересная.

Сообщение от odip

...
А именно - приведенный тобой алгоритм находит какое-то разбиение на квадраты.
А нужно найти разбиение чтобы число квадратов было минимально.
...

Тот алгоритм - это первое до чего я додумался.
По свободе подумаю над другими алгоритмами.

Сообщение от odip

...тест:
N=18
Правильный ответ: 2 ( 9+9 )
Твоя программа выводит 3 ( видимо 16+1+1 )

Добавил вывод отладочной информации.
Действительно 16+1+1.

@odip · 08.01.2010, 18:18 **[ТС]**

Вспомнил - что-то подобное я уже решал.
Момент такой: Любое натуральное N может быть представлено в виде суммы квадратов не более чем 4-ех слагаемых.
То есть в худшем случае будет 4 участка.
Значит задача резко упрощается.
1) Проверить N - это A0^2
2) Проверить что N = A0^2+A1^2, причем A0>=A1
3) Проверить что N= A0^2+A1^2+A2^2, причем A0>=A1>=A2
4) Проверить - но можно и не проверять
N = A0^2+A1^2+A2^2+A3^2, причем A0>=A1>=A2>=A3
Какой вариант нашли раньше - такой ответ и будет.

Добавлено через 24 минуты
Все - сдал

Программа

C

/* Problem 1073 */
 
#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
 
 
/********************************************************************/
int calc_min_k( int n );
 
 
/********************************************************************/
int main( void ) {
 
int n, k;
 
 
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
freopen( "output.txt", "w", stdout );
#endif
 
scanf( "%d", &n );
assert( 1<=n && n<=60000 );
 
k= calc_min_k( n );
printf( "%d\n", k );
 
return 0;
 
} /* main() */
 
 
/********************************************************************/
int calc_min_k( int n ) {
 
int sq_n;
int a0, a1, a2, a3;
int ost0, ost1, ost2, ost3;
 
 
/* Init */
ost0= n;
sq_n= (int)sqrt( ost0 );
 
/* Check 1 */
a0= sq_n;
if ( ost0 == a0*a0 ) {
    return 1;
}
    
/* Check 2 */
for ( a0= sq_n; a0>=1; a0-- ) {
    ost1= ost0-a0*a0;
    a1= (int)sqrt( ost1 );
    if ( a0<a1 ) { break; }
    if ( ost1 == a1*a1 ) {
        return 2;
    }
}
 
/* Check 3 */
for ( a0= sq_n; a0>=1; a0-- ) {
    ost1= ost0-a0*a0;
    for ( a1= (int)sqrt(ost1); a1>=1; a1-- ) {
        if ( a0<a1 ) { break; }
 
        ost2= ost1-a1*a1;
        a2= (int)sqrt( ost2 );
        if ( a1<a2 ) { break; }
        if ( ost2 == a2*a2 ) {
            return 3;
        }
    }
}
 
/* Check 4 */
for ( a0= sq_n; a0>=1; a0-- ) {
    ost1= ost0-a0*a0;
    for ( a1= (int)sqrt(ost1); a1>=1; a1-- ) {
        if ( a0<a1 ) { break; }
 
        ost2= ost1-a1*a1;
        for ( a2= (int)sqrt(ost2); a2>=1; a2-- ) {
            if ( a1<a2 ) { break; }
 
            ost3= ost2-a2*a2;
            a3= (int)sqrt( ost3 );
            if ( a2<a3 ) { break; }
            if ( ost3 == a3*a3 ) {
                return 4;
            }
        }
    }
}
 
fprintf( stderr, "Internal error !\n" );
return 4;
 
} /* calc_min_k() */

@outoftime · 08.01.2010, 21:28

odip, хорошо что вы до теста 18 сами дошли, и то что програма рабочая - тоже хорошо, но можно поподробнее, именно тот факт что любое натуральное чисо можно представить в виде сумы не более чем 4-ех слагаемых?

@odip · 08.01.2010, 21:38 **[ТС]**

Что за тест 18 ?

Этот факт упоминался в какой-то олимпиадной задаче.
Я проверял от 1 до INT_MAX - не врут

@Eugeniy · 08.01.2010, 23:34

То, что Вы ищете есть не что иное, как знаменитая теорема Лагранжа о четырёх квадратах.

@odip · 08.01.2010, 23:55 **[ТС]**

Буду знать как называется

Так вот для кубов:
Каждое натуральное число представимо в виде суммы не более 8 кубов чисел.

25.09.2010, 18:36

Извиняюсь за некрофильство, но возможно кому-то будет интересно.
Без знания теоремы Лагранджа задачу можно решить динамическим программированием, например так

C++

# include <iostream>
# include <cstdio>
# include <cstdlib>
# include <vector>
# include <cmath>
# include <algorithm>
# include <iomanip>
# include <numeric>
# include <iterator>
# include <climits>
 
# define LOOP(i,s,e) for (int i=s; i<e; ++i)
    
# define INF 1./0
# define Fi 1.61803
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    
    vector<int> hash(1,0);
    
    LOOP(i,1,n+1)
    {
        int pat = i*i;
        if (pat > n) break;
        hash.push_back(pat);
    }
    
    vector<int> vec(n+1, INT_MAX);
    vec[0] = 0;
    
    LOOP(i,0,n)
    {
        if (vec[i] == INT_MAX) continue;
        LOOP(j,1,hash.size())
        {
            if (i+hash[j] > n) break;
            
            vec[i+ hash[j]] = min(vec[i+ hash[j]], vec[i] +1);
        }
    }
    cout << vec[n];
    exit(0);
    
}

@odip 7175 / 3234 / 79 Регистрация: 17.06.2009 Сообщений: 14,164
		1
	Квадратная страна 08.01.2010, 15:57. Показов 4209. Ответов 10 Метки нет (Все метки) http://acm.timus.ru/problem.as... &locale=ru В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 × 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», — сказал он. Сделка состоялась. Найдите, какое количество квадратных свидетельств он получил. Исходные данные В единственной строке стоит положительное число N ≤ 60 000 — число квадриков, которое было у жителя. Результат В единственной строке стоит число свидетельств, полученных в результате сделки. Пример: INPUT 344 OUTPUT 3 0

@outoftime
	08.01.2010, 16:06 #2
	Не по теме: сейчас камп будет занят, я пока поразмышляю над задачей, напишу потом 0

@odip 7175 / 3234 / 79 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 16:58 [ТС]	4
	Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена. Ты забываешь что это олимпиадные задачи. А значит всегда есть над чем подумать. А именно - приведенный тобой алгоритм находит какое-то разбиение на квадраты. А нужно найти разбиение чтобы число квадратов было минимально. Добавлено через 3 минуты Вот тебе тест: N=18 Правильный ответ: 2 ( 9+9 ) Твоя программа выводит 3 ( видимо 16+1+1 ) 1

@Delphin_KKC UNIX-way 712 / 495 / 49 Регистрация: 15.01.2009 Сообщений: 1,720
	08.01.2010, 17:53	5
	Сообщение от odip Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена. Ты забываешь что это олимпиадные задачи. А значит всегда есть над чем подумать. ... Потому и написал что задача интересная. Сообщение от odip ... А именно - приведенный тобой алгоритм находит какое-то разбиение на квадраты. А нужно найти разбиение чтобы число квадратов было минимально. ... Тот алгоритм - это первое до чего я додумался. По свободе подумаю над другими алгоритмами. Сообщение от odip ...тест: N=18 Правильный ответ: 2 ( 9+9 ) Твоя программа выводит 3 ( видимо 16+1+1 ) Добавил вывод отладочной информации. Действительно 16+1+1. 1

@outoftime ║XLR8║ 1211 / 908 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	08.01.2010, 21:28	7
	odip, хорошо что вы до теста 18 сами дошли, и то что програма рабочая - тоже хорошо, но можно поподробнее, именно тот факт что любое натуральное чисо можно представить в виде сумы не более чем 4-ех слагаемых? 0

@odip 7175 / 3234 / 79 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 21:38 [ТС]	8
	Что за тест 18 ? Этот факт упоминался в какой-то олимпиадной задаче. Я проверял от 1 до INT_MAX - не врут 1

@Eugeniy 3130 / 1323 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	08.01.2010, 23:34	9
	То, что Вы ищете есть не что иное, как знаменитая теорема Лагранжа о четырёх квадратах. 2

@odip 7175 / 3234 / 79 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 23:55 [ТС]	10
	Буду знать как называется Так вот для кубов: Каждое натуральное число представимо в виде суммы не более 8 кубов чисел. 0

	25.09.2010, 18:36

Опции темы