Форум программистов, компьютерный форум, киберфорум
C++
Форум программистов и сисадминов Киберфорум > Форум программистов > C++
Войти
Регистрация
Восстановить пароль
Правила Карта Блоги Социальные группы Поиск Сообщения за день  
 
Рейтинг 4.83/18: Рейтинг темы: голосов - 18, средняя оценка - 4.83
Эксперт С++
7172 / 3230 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
1

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

08.01.2010, 15:57. Просмотров 3466. Ответов 10
Метки нет (Все метки)
http://acm.timus.ru/problem.as... &locale=ru

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

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

Пример:
INPUT
344
OUTPUT
3
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 08.01.2010, 15:57
Ответы с готовыми решениями:

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

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

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

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

10
outoftime
08.01.2010, 16:06
  #2

Не по теме:

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

0
UNIX-way
712 / 495 / 49
Регистрация: 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
1
Эксперт С++
7172 / 3230 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
08.01.2010, 16:58  [ТС] 4
Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена.
Ты забываешь что это олимпиадные задачи.
А значит всегда есть над чем подумать.

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

Добавлено через 3 минуты
Вот тебе тест:
N=18
Правильный ответ: 2 ( 9+9 )
Твоя программа выводит 3 ( видимо 16+1+1 )
1
UNIX-way
712 / 495 / 49
Регистрация: 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.
1
Эксперт С++
7172 / 3230 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
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() */
2
║XLR8║
1098 / 840 / 256
Регистрация: 25.07.2009
Сообщений: 4,158
Записей в блоге: 5
08.01.2010, 21:28 7
odip, хорошо что вы до теста 18 сами дошли, и то что програма рабочая - тоже хорошо, но можно поподробнее, именно тот факт что любое натуральное чисо можно представить в виде сумы не более чем 4-ех слагаемых?
0
Эксперт С++
7172 / 3230 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
08.01.2010, 21:38  [ТС] 8
Что за тест 18 ?

Этот факт упоминался в какой-то олимпиадной задаче.
Я проверял от 1 до INT_MAX - не врут
1
3128 / 1321 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
08.01.2010, 23:34 9
То, что Вы ищете есть не что иное, как знаменитая теорема Лагранжа о четырёх квадратах.
2
Эксперт С++
7172 / 3230 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
08.01.2010, 23:55  [ТС] 10
Буду знать как называется

Так вот для кубов:
Каждое натуральное число представимо в виде суммы не более 8 кубов чисел.
0
b4990
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);
    
}
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 25.09.2010, 18:36

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Свойства и методы классов Ученик, Учитель, Школа, Экзамен, Турнир, Урок, Страна, Браузер
Подумайте, какими свойствами и методами могли бы обладать объекты следующих классов: Ученик,...

Реализовать односвязный список данных вида "Страна, город, количество населения"
Поставлена задача реализовать односвязный список данных вида Страна город количество населения...

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

игра "туманная страна" на с++
добрый день. пишу игру на с++ и параллельно изучаю этот прекрасный (!!!) язык. использую SFML как...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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