Задача Гипотеза

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.

Задача Гипотеза

Сообщение Vladislav_133 24 мар 2016, 11:12

Задача Гипотеза
Вложения
Gipoteza.pdf
(264.97 Кб) Скачиваний: 436
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение hardcore_test 24 мар 2016, 12:20

Тут точно нет ограничения по времени?
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Гипотеза

Сообщение Vladislav_133 24 мар 2016, 12:53

Нет. Я не предполагаю в тестах проверять на больших промежутках. Но значение границ может быть большим.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение Vladislav_133 27 мар 2016, 11:30

В данной задача была одна маленькая ловушка, в которую народ с удовольствием начал попадаться.
Дело в том, что задача (по условию) решается на множестве целых 32-битовых чисел.
Хотя ни кто не мешал взять и 64-битовые числа.
Максимальное значение 2147483647. И вот если взять промежуток [a,2147483647] то все естественно
пишут цикл типа for(i=a; i<=b; i++) . Но после i=b цикл делает еще один инкремент i++ и тут же оказывается в минусовых значениях
и программа уже не может закончиться никогда.
Последний раз редактировалось Vladislav_133 27 мар 2016, 14:07, всего редактировалось 1 раз.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение Vladislav_133 27 мар 2016, 12:43

А в ловушку продолжают попадаться. Не думал я, что это серьезно.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение Vladislav_133 27 мар 2016, 13:12

Не внимательно читали условие задачи. Вообще говоря 1 не является простым числом по современным трактовкам. Правда Гольдбах считал 1 простым числом.
Вот ради Гольдбаха можно человека простить, поскольку в принципе алгоритм верен. Хотя опять попал в поставленную мной ловушку.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение hardcore_test 27 мар 2016, 14:46

Vladislav_133 писал(а):А в ловушку продолжают попадаться. Не думал я, что это серьезно.

Забавно, что у меня именно здесь программа работала долго и поэтому я спросил про время
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Гипотеза

Сообщение Vladislav_133 28 мар 2016, 13:17

Напоминаю, что ваши результаты могут не совпадать с эталонными и все равно считаются правильными, если удовлетворяют условию данной задачи.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение Vladislav_133 29 мар 2016, 08:53

У меня на виртуальной машине тест 1 моя программа проходит за несколько секунд.
На Jav'е просто результата не могу дождаться. Даже не думал, что это самый натуральный крэш-тест.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение hardcore_test 29 мар 2016, 09:01

1 тест это же тот самый вечный цикл?
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Гипотеза

Сообщение Vladislav_133 29 мар 2016, 09:05

Нет, у многих проходит, но очень долго, почему то.
Я предварительно заглядываю в программу и вижу, что скажем long используется.
Тогда можно ждать. Сейчас у одного ждал 3 минуты, хотел уже ему нолик поставить.
В общем правила нарушаю, конечно.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение Vladislav_133 29 мар 2016, 09:24

Я думаю, что и на Java можно сделать программу, которая быстро работает, но надо потрудиться.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение hardcore_test 29 мар 2016, 09:40

У меня если int поменять на long, то работает быстро
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Гипотеза

Сообщение Vladislav_133 29 мар 2016, 10:15

Да, вот ваша программа в отличие от других программ на Java проходит "нехорошие" тесты быстро.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение Vladislav_133 06 апр 2016, 13:27

Проверка гипотезы Гольдбаха. Чистый 32-битовый C.

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
//prime numbers (conjecture of Goldbach)
#include <stdio.h>

int simple(int);

int main(){
    int a,b,i,j,j1,j2;
    scanf("%d %d",&a,&b);
    if(a<3)return 1;
    for(i=a; i<=b; i++){
        if(i%2!=0){
            if(i==2147483647)break;
            continue;
        }
        printf("%d=",i);
        for(j=2; j<=i/2; j++){
            j1=j; j2=i-j1;
            if(simple(j1)&&simple(j2)){
                printf("%d+%d\n",j1,j2);
                break;                 
            }
        }
    }    
    return 0;
}
//whether this number simple or not
int simple(int k){
    int h;
    for(h=2; h<k/2; h++){
        if(k%h==0)break;
    }
    if(h==k/2)return 1; else return 0;    
}

 
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Гипотеза

Сообщение hardcore_test 06 апр 2016, 17:56

Simple лучше идти до корня из числа, так как максимальный делитель из числа это его корень
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Гипотеза

Сообщение Vladislav_133 06 апр 2016, 18:14

Верно, но здесь я, что по-проще
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.


Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron