Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.71
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
#1

Квадратная страна - C++

08.01.2010, 15:57. Просмотров 2206. Ответов 10
Метки нет (Все метки)

http://acm.timus.ru/problem.aspx?spa...1073&locale=ru

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

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

Пример:
INPUT
344
OUTPUT
3
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2010, 15:57     Квадратная страна
Посмотрите здесь:

Создайте структуру Country (страна), содержащую следующие поля - C++
Создайте структуру Country (страна), содержащую следующие поля: • название; • столица; • численность населения; • площадь.

создание структуру СТРАНА. добавление и удаление элементов из структуры - C++
Сформируйте двоичный файл из элементов, заданной в варианте структуры, напечатайте его содержимое, выполните удаление и добавление...

C++ задача. C 2009 года наша страна празднует день программиста 13 сентября - C++
C 2009 года наша страна празднует день программиста 13 сентября. Каким днем недели будет 13 сентября указанного года (начиная с 2009 до...

нужно чтоб нашлась страна и все данные об этой стране вывелись в таблицу... - C++
Помогите с поиском по файлу ну не как не получается его сделать.... В файле записано: Страна Столица Валюта ну вот так ......

Реализовать односвязный список данных вида "Страна, город, количество населения" - C++
Поставлена задача реализовать односвязный список данных вида Страна город количество населения Обеспечить выполнение операций: ...

Разработать класс "Машина" с полями: марка, страна-производитель, максимальная скорость, объём двигателя - C++
Разобрать класс машина, который содержит поля: марка машини, страна производителя, макс. скорость, обьем двигателя. Разобрать конструкторы,...

квадратная матрица на С ??? - C++
написать программу на стандартном языке С (не с++) Дана действительная квадратная матрица порядка 2n. Получить новую матрицу переставляя...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
08.01.2010, 16:06
  #2

Не по теме:

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

Delphin_KKC
UNIX-way
709 / 494 / 17
Регистрация: 15.01.2009
Сообщений: 1,721
08.01.2010, 16:22     Квадратная страна #3
Интересная задача.
Алгоритм решения
0)переменной, в которой будет число участков (у меня - k), присваиваем ноль
1)берём квадратный корень из числа имеющихся квадриков
2)округляем результат вниз до целого
3)возводим результат в квадрат
4)отнимаем результат от числа квадриков
5)k++;
6)повторяем п.п. 1-5 до тех пор, пока деньги не кончатся

Код программы. Вариант с While
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 16:58  [ТС]     Квадратная страна #4
Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена.
Ты забываешь что это олимпиадные задачи.
А значит всегда есть над чем подумать.

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

Добавлено через 3 минуты
Вот тебе тест:
N=18
Правильный ответ: 2 ( 9+9 )
Твоя программа выводит 3 ( видимо 16+1+1 )
Delphin_KKC
UNIX-way
709 / 494 / 17
Регистрация: 15.01.2009
Сообщений: 1,721
08.01.2010, 17:53     Квадратная страна #5
Цитата Сообщение от odip Посмотреть сообщение
Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена.
Ты забываешь что это олимпиадные задачи.
А значит всегда есть над чем подумать.
...
Потому и написал что задача интересная.
Цитата Сообщение от odip Посмотреть сообщение
...
А именно - приведенный тобой алгоритм находит какое-то разбиение на квадраты.
А нужно найти разбиение чтобы число квадратов было минимально.
...
Тот алгоритм - это первое до чего я додумался.
По свободе подумаю над другими алгоритмами.
Цитата Сообщение от odip Посмотреть сообщение
...тест:
N=18
Правильный ответ: 2 ( 9+9 )
Твоя программа выводит 3 ( видимо 16+1+1 )
Добавил вывод отладочной информации.
Действительно 16+1+1.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 18:18  [ТС]     Квадратная страна #6
Вспомнил - что-то подобное я уже решал.
Момент такой: Любое натуральное 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/* 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
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 21:28     Квадратная страна #7
odip, хорошо что вы до теста 18 сами дошли, и то что програма рабочая - тоже хорошо, но можно поподробнее, именно тот факт что любое натуральное чисо можно представить в виде сумы не более чем 4-ех слагаемых?
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 21:38  [ТС]     Квадратная страна #8
Что за тест 18 ?

Этот факт упоминался в какой-то олимпиадной задаче.
Я проверял от 1 до INT_MAX - не врут
Eugeniy
3119 / 1312 / 141
Регистрация: 19.12.2009
Сообщений: 1,808
08.01.2010, 23:34     Квадратная страна #9
То, что Вы ищете есть не что иное, как знаменитая теорема Лагранжа о четырёх квадратах.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 23:55  [ТС]     Квадратная страна #10
Буду знать как называется

Так вот для кубов:
Каждое натуральное число представимо в виде суммы не более 8 кубов чисел.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2010, 18:36     Квадратная страна
Еще ссылки по теме:

Квадратная матрица - C++
Помогите решить: Дана квадратная матрица. Найти строчку с наибольшим и наименьшим произведением элементов. Вывести на печать полученные...

Квадратная матрица - C++
Вариант 5 Дана целочисленная квадратная матрица. Определить: 1) сумму элементов в тех столбцах, которые не содержат отрицательных...

квадратная матрица - C++
Доброе время суток! &quot;дано действительгое число х.получить квадратную матрицу порядка n+1,результат записать в файл?&quot; обьясните хоть...

Квадратная матрица ! - C++
Дана квадратная матрица размерности n × n . Найти максимальный элемент каждой строки и поменять его с элементом этой строки, стоящим в ...

квадратная матрица - C++
помогите решить задачу на турбо си,очень надо( Получить целочисленную квадратную матрицу порядка 7, элементами которой являются числа...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
b4990
Сообщений: n/a
25.09.2010, 18:36     Квадратная страна #11
Извиняюсь за некрофильство, но возможно кому-то будет интересно.
Без знания теоремы Лагранджа задачу можно решить динамическим программированием, например так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 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);
    
}
Yandex
Объявления
25.09.2010, 18:36     Квадратная страна
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru