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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Препроцессорные директивы в C/C++ (#include, #define и прочее) http://www.cyberforum.ru/cpp/thread83659.html
Статья переехала сюда
C++ Игра Пуговицы. http://acm.timus.ru/problem.aspx?space=1&num=1023&locale=ru Правила игры очень просты. Перед двумя играющими находится кучка из K пуговиц. Играющие по очереди берут пуговицы из кучки, причем за один ход каждый из них может взять от 1 до L пуговиц. Выигрывает тот из спортсменов, которому удастся взять последнюю пуговицу. Правила олимпийских соревнований будут лишь немного сложнее обычных. Тот... http://www.cyberforum.ru/cpp/thread83658.html
C++ Ассемблерная вставка
Товарищи!! кто знает, подскажите как сделать ассемблерную вставку в cи-проекте в среде Turbo C?? я пытался скормить ему asm...,но никак..ошибка( может быть надо тот кусок проги на асм отдельным файлом сделать и прикрепить..не знаю подскажите плз!!
C++ Step 1: Specify the working directory from which doxygen will run
У меня есть файлы написанные на С++ (cpp и h). Все эти файлы я разместила на диске D в одной папке. Нужно получить документацию по каждому файлу. А у меня в результате получается пустой документ. Step 1: Specify the working directory from which doxygen will run Я пишу там так: D:/ Учеба/ ВПИ/Registration( в папке Registration у меня cpp и h файлы. Scan recursively - галочка стоит. Source...
C++ Подскажите http://www.cyberforum.ru/cpp/thread83203.html
Как с помощью 0 канала системного таймера подсчитать время выполнения определенных действий?Может у кого код есть с подобным примером?Спасибо всем ответившим?(среда bc 3.1)
C++ Где используется Tini C Compiler? Здравствуйте! Если знаете, напишите пожалуйста примеры использования TCC (или другого интерпретатора си) как интерпретатора? Если не практические, то хотя-бы теоретически, где можно использовать интерпретатор си? подробнее

Показать сообщение отдельно
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
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
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() */
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru