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

Наихудший делитель. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
12.05.2011, 11:30     Наихудший делитель. #1
Наихудший делитель
(Время: 1 сек. Память: 16 Мб Сложность: 23%)

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n. Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель c числа n лучше, чем d.
Входные данные

Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 105000).
Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.
INPUT.TXT
10
OUTPUT.TXT
10

INPUT.TXT
239
OUTPUT.TXT
1
Ведь наихудший делитель всегда будет равен 1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2011, 11:30     Наихудший делитель.
Посмотрите здесь:

Делитель. C++
C++ наибольший общий делитель
C++ Общий делитель С++
найти общий делитель C++
Наибольший общий делитель на С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
12.05.2011, 11:34     Наихудший делитель. #2
А как же первый сэмпл? Сумма цифр 1 и 10 равна, 1 < 10, значит 10 хуже.
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
12.05.2011, 12:13  [ТС]     Наихудший делитель. #3
вот как...

Добавлено через 36 минут
Хохол, в чем смысл задания?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 13:20     Наихудший делитель. #4
Алгоритм такой-выводим 1, и если в конце числа есть нули, то выводим их количество.
Реализация
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>>
#include <string.h>
char a[9999];
main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%s",&a);
    printf("1");
    for (int i = strlen(a)-1; i > 0; i--)
        if (a[i]=='0') printf("0"); else break;
    return 0;
}

P.S.
Вопрос к гуру-как можно код под катом сжать до 104 символов? Символов на 30 еще смогу, но дальше-уже за гранью добра и зла.
Temirlan90
 Аватар для Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
12.05.2011, 14:05  [ТС]     Наихудший делитель. #5
На реализацию не смотрел =), за алгоритм спасибо, diagon, Вы не могли бы сказать почему именно такой алгоритм????
Реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
using namespace std;
int main() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    string s;
    cin >> s;
    cout << 1;
    for (int i = s.length() - 1; i > 0; i--)
        if (s[i] == '0') 
            cout << 0; 
    return 0;
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.05.2011, 14:07     Наихудший делитель. #6
Если честно, то уже не помню, давно решал...
Прочитайте внимательно условие, может поймете.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
12.05.2011, 16:14     Наихудший делитель. #7
diagon, я максимум на столько смог сжать:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <fstream>
 
std::ofstream c("output.txt");
 
main()
{
    char s[9999];
    std::ifstream("input.txt") >> s;
    int i = strlen(s);
    c << 1;
    while(s[--i] == 48)
        c << 0;
}
(Оно даже у меня в студии не компилится из-за голого main, а там работает)
Тоже интересно, как этот Лунев такое вытворяет.
Temirlan90
12.05.2011, 16:17  [ТС]
  #8

Не по теме:

Тоже интересно, как этот Лунев такое вытворяет.
Походу Он легенда =))

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2011, 18:19     Наихудший делитель.
Еще ссылки по теме:

C++ делитель
Наилучший делитель C++
C++ Как найти делитель

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

Или воспользуйтесь поиском по форуму:
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
12.05.2011, 18:19     Наихудший делитель. #9
C++
1
2
3
4
5
6
7
8
9
10
#include <fstream>
 
main()
{
    char b[9999], *p;
    std::fstream("input.txt") >> b;
    p = b+strlen(b);
    while(*--p == 48);
    std::ofstream ("output.txt") << 1 << p+1;
}
135 символов.

Добавлено через 1 час 5 минут
C++
1
2
3
4
5
6
7
8
9
10
#include <map>
char b[9999];
#define a(b) freopen(#b"put.txt","a+",std##b);
main()
{
    a(in)
    a(out)
    while (scanf("%c%[0]",b,b+1)>=0)*b=49;
    puts(b);
}
133

Эти два - уже не мое.
Yandex
Объявления
12.05.2011, 18:19     Наихудший делитель.
Ответ Создать тему
Опции темы

Текущее время: 07:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru