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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
#1

Задача "Урюк" - C++

27.04.2012, 10:53. Просмотров 1505. Ответов 29
Метки нет (Все метки)

Ребят, всем привет, помогите пожалуйста задачу решить
http://imcs.dvgu.ru/cats/static/prob...id-850202.html

Рекурсивным поиском скорее всего не прокатит по времени.
Я решил как рекурентное соотношение, но получаю за задачу 14 баллов.
Вобщем легко составить ряд для небольших чисел(заполняя массив):

2 - U
3 - max(R,U)
4 - 2U
5 - max(R, 2U)
6 - U + max(R,U);
7 - max(R, U+max(R,U))
8 - 3U

можно заметить, что если N четное то a[N] = a[N/2] + U
а если нечетное то a[N] = max(R, a[N/2]+U)

т.е. для каждого элемента от 2 до 500000 сделать следующее
a[2*i]= a[i]+U
a[2*i+1]=max(R, a[i]+U)

поэтому по 2 и 3 значению можно собрать массив до милионного элемента
Вроде бы логично, но повторюсь что набрал всего 14 баллов
Подскажите пожалуйства в чем ошибка или посоветуйте другое решение, заранее благодарен
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2012, 10:53     Задача "Урюк"
Посмотрите здесь:

C++ по строкам.замените в слове сочетание "му" на "а" , а букву "ы" на "ца". очень нужно
C++ Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64"
Чтения структуры из файла (описать структуру с именем "ORDER": "счет плательщика"; "счет получателя"; "сумма, переводится банковской операцией") C++
Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" C++
Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) C++
C++ Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс"
Реализовать структуру "Анкета" с полями "Фамилия", "Пол" и "Адрес" C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
28.04.2012, 11:39  [ТС]     Задача "Урюк" #2
upppp!!!
-=ЮрА=-
Заблокирован
Автор FAQ
28.04.2012, 13:14     Задача "Урюк" #3
Demsol, вот тебе решение.
алгоритм прост есть куча, бьём её случайным образом на две
N1 = rand()%(N - 1)
N2 = N - N1
далее производим сравнение, понятное дело что потом будем брать кучу с меньшим весом и снова её делить на две и так пока не дойдём до кучи из 2х монет
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
#include <cmath>
#include <ctime>
#include <fstream>
#include <iostream>
using namespace std;
 
int main()
{
    long N;
    long R;
    long U;
    long N1;
    long N2;
    long M = 0;
 
    srand(time(0));
    ifstream ifs("in.txt");
    ofstream ofs("out.txt");
    if(!ifs.is_open())
        cout<<"Error open in.txt\n";
    else
    if(!(ifs>>N>>R>>U))
        cout<<"Error read in.txt\n";
    else
    {
        while(2 < N)
        {
            N1 = rand()%(N - 1);
            N2 = N - N1;
            if(N1 == N2)
                M += R;
            else
                M += U;
            N = N1 < N2 ? N1 : N2;
        }
        cout<<"M = "<<(M + U)<<endl;
        if(!ofs.is_open())
            cout<<"Error open out.txt\n";
        else
            ofs<<(M + U);
    }
    ifs.close();
    ofs.close();
    system("pause");
    return 0;
}
Отработка
in.txt 15 2 3
out.txt 9
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
15.05.2012, 12:20  [ТС]     Задача "Урюк" #4
Твое решение неверно, "рандом умным не бывает(с)", нужно найти МИНИМАЛЬНОЕ количество урюка.
Проходит оно несколько тестов в середине, каждый раз они меняются. В среднем, это еще меньшее количество баллов чем у меня. Меня натолкнуло на мысль, если например N это степень двойки, и R и U сильно различаются, то решение рекурентным соотношением уже может быть неверным, (тесты скорее всего так и подобраны), нужно еще хорошо подумать.
Но все равно спасибо вам )
-=ЮрА=-
Заблокирован
Автор FAQ
15.05.2012, 12:49     Задача "Урюк" #5
[OFF]Demsol,
Цитата Сообщение от Demsol Посмотреть сообщение
нужно найти МИНИМАЛЬНОЕ количество урюка.
- минимально количество урюка говоришь - тогда 1 на одной чаше весов все деньги а на другой фальшивая монета.
"рандом умным не бывает(с)"
- рандомно как раз моделируем реальные случаи разложения монет по кучам - надеюсь слышал такие понятия как событие, вероятность и прочее. В комбинаторике рандом положен во главу краеугольных камней всех выкладок, а ты мне тут свои копирайты подсовываешь...Если бы раскрыл глаза то увидел что для малого числа моент резултаты совпадают 1 к 1-му а для больше числа моент результаты поданные в ответах часто "проскакивают", как раз всё зависит от "настроения рандома".

Цитата Сообщение от Demsol Посмотреть сообщение
Меня натолкнуло на мысль, если например N это степень двойки
- кто тебе вообще это сказал что монет в куче под степень двойки - потому что так хочется?
А если в куче будет 4097 или 4098 монет или просто три - тоже под степень двойки говоришь
MrGluck
Ворчун
Эксперт CЭксперт С++
6403 / 3601 / 448
Регистрация: 29.11.2010
Сообщений: 9,528
15.05.2012, 15:38     Задача "Урюк" #6
Я бы делил вобще на 3 кучи и сравнивал. Если взвешиваемые кучи не равны - весы покажут. Если равны - монета в куче, которую не взвешивали.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 21:52     Задача "Урюк" #7
Цитата Сообщение от MrGluck Посмотреть сообщение
Я бы делил вобще на 3 кучи и сравнивал. Если взвешиваемые кучи не равны - весы покажут. Если равны - монета в куче, которую не взвешивали.
Не все так просто. Этим можно добится минимального количества взвешиваний, но не минимальное количество урюка. Пример: 9 монет, R=1, U=1000000.
Деля на на три кучки можно найти монету за два взвешивания, но урюка получится 2000000.
А если брать по 2 монеты, взвешивать только их, то получится 4 взвешивания, но всего 1000003 урюка.
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
22.05.2012, 10:36  [ТС]     Задача "Урюк" #8
To-=ЮрА=-
- минимально количество урюка говоришь - тогда 1 на одной чаше весов все деньги а на другой фальшивая монета.
Минимальное кол-во урюка, необходимого для 100% выявления фальшивой монеты. Т.е. нужно разделить кол-во взвешиваний на наименее затратное, и из этой комбинации выбрать наихудший случай.
всё зависит от "настроения рандома".
Ну если ты слышал о правилах проведения всерос олимпиад, то жюри вправе сколь угодно много запускать твое решение и проверять его правильность. Если в структуре присутсвует рандом, то вероятнее всего так и будет. Если интересно, решение проходит(точно уже не помню) 5-6 тестов из примерно 30. Ну при "хорошем настроении рандома" впринципе можно 7-8 баллов получить, но не больше. Да для небольших N вероятность совпадения велика, а если для N=10^6? Да и вобще, если бы олимпиада была acm'овской, то такое решение НИКОГДА бы не получило правильности, надеюсь догадываешься почему.
кто тебе вообще это сказал что монет в куче под степень двойки - потому что так хочется?
Нет не потому что так хочется, а потому что такой случай наиболее прост и удобен в ручном разборе и его я выбрал для объяснения самому себе неправильности рекурентного соотношения. Да и вобще
если НАПРИМЕР N это степень двойки, и R и U СИЛЬНО РАЗЛИЧАЮТСЯ...
Вот тебе пример valeriikozlov, , N - вобще без разницы какое, R=1, U=1000000.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
22.05.2012, 11:10     Задача "Урюк" #9

Не по теме:

А где можно посмотреть результаты Всероссийской олимпиады и все задачи сразу? Можно ссылку, пожалуйста?



Добавлено через 8 минут
И еще, где можно сдать задачу, чтобы проверить решение?
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
22.05.2012, 11:40  [ТС]     Задача "Урюк" #10
В этом году олимпиада проходила в казани, все материалы здесь
http://infoolimp.tatar.ru/about_olym...алы-олимпиады/
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
22.05.2012, 11:40     Задача "Урюк" #11
По крайней мере половину задачи можно решить. Если u < r тогда задача решается легко.
C++
1
2
3
4
5
6
7
8
9
long long u, r ;
long long solve( long long n, long long s )
{
     if( n == 1 )
          return s ;
     
     if( u <= r )
       return max( s + r , solve( n/2, s + u ) );
}
Ответ - solve( n, 0 )

Когда u > r сложнее...тут что то с делителями связано.
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
22.05.2012, 11:49  [ТС]     Задача "Урюк" #12
Ну если хочешь проверить решения, можно тут
http://imcs.dvgu.ru/cats/main.pl?f=p...id=;cid=850112
Но тут только с первого тура задачи
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
22.05.2012, 12:17     Задача "Урюк" #13
Да у них сайт какой то глючный! Там сдать невозможно. Другую бы ссылку...

Добавлено через 21 минуту
Прошло 6 первых тестов

Добавлено через 1 минуту
Все таки думаю, что во всех остальных 44 тестах: u > r
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
22.05.2012, 12:48  [ТС]     Задача "Урюк" #14
да нормальный сайт, просто серваки во владике расположены. У меня отлично и без тормозов работает

Добавлено через 4 минуты
хм, ну вот вишь всего 6 тестов проходит, а там задания по блокам развешены, т.е минимально нужно 30 баллов набрать, а так Solution rejected
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
22.05.2012, 21:40     Задача "Урюк" #15
Нет, я был не прав. В половине u > r в половине наоборот.
Мое решение не верно.

Добавлено через 3 часа 35 минут
Мое новое решение проходит пока что 11 первых тестов, 1 второй и 1 третий (на остальных ВА )

Добавлено через 12 минут
Оно следущее:
Пусть у нас есть n камней, даны r и u . Обозначим через f( n ) - минимальное количество урюка, с помощью которого гарантированно будет обнаружена фальшивая монета в кучке размером в n монет.

Попробуем вычислить значение этой функции через предыдущие значения. Допустим, мы решили взять 2 кучки по a камней ( a <= n/2 ) из данных нам n монет. Тогда может быть:

1) a = a То есть кучки сравнялись и среди кучек нет фальшивой монеты. Тогда f( n ) = f( n - 2*a ) + r ( осталось n - 2*a монет, ищем там фальшивую )

2) a <> a То есть в одной из кучек фальшивая монета. Тогда f( n ) = f( a ) + U

Мы должны рассмотреть худший случай, то есть максимальное значение f( n ) для этого a . То есть найти максимум среди f( n - 2*a ) + r и f( a ) + U .

Теперь рассмотрим решение для произвольного a .

1) Пусть f( n - 2*a ) + r > f( a ) + U . Тогда f( n ) = f( n - 2*a ) + r.

Нам нужно найти минимум f( n ) ( следуя условию нужно найти минимальное количество урюка ) . Минимум f( n ) достигается при минимуме f( n - 2*a ).

Тут я предположил, что минимум f( n - 2*a ) достигается при минимуме n - 2*a, а иначе при максимуме a, то есть я предположил, что функция f( x ) возрастает при увеличении x .
Update. Это действительно так.

Тогда можно перебирать всемозножные a бинарным поиском от 1 до n/2 и найти такое максимальное а, что f( n - 2*a ) + r > f( a ) + U .

2)Аналогично предпологается, что f( n - 2*a ) + r < f( a ) + U . Тогда f( n ) = f( a ) + U.

Краевые значения f( i ) = 0, i <= 1 и f( 2 ) = u .

То есть весь алгоритм:

- для каждого n бинарным поиском сначала ищется максимальное a, для которого выполняется f( n - 2*a ) + r > f( a ) + U

- для каждого n бинарным поиском ищется минимальное a, для которого выполняется f( n - 2*a ) + r < f( a ) + U

- ответом будет являтся минимум из f( n - 2*a ) + r ( то значение которое получили при первом бинпоиске ) и f( a ) + U ( при втором )

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

Добавлено через 23 секунды
Поищите ошибку, пожалуйста

Добавлено через 11 минут
Ура! Подправил ошибку и прошло более половины тестов:
16 первой группы, 5 второй группы, 4 последней группы

Но все же ошибка где-то есть. И, кстати, на 3 тестах в конце ТЛЕ.

Добавлено через 1 час 14 минут
Пофиксил все ошибки... Итого - 17 тестов первых тестов, 9 вторых, 5 третих. Остальные 19 тестов не могу сдать. Думаю, решение правильное, описано сверху.

Код
Писал на Dev-C++.
В map'е для ускорения хранятся уже ранее вычисленные значения solve( n ) чтобы не пересчитывать их. Внутри функции solve - R, L, m - переменные для бинпоиска, после цикла бинпоиска( их два, как я и писал выше ) еще раз проверяю подходит ли значение. ans1 , ans2 - переменные для двух вариантов, что тоже описано выше. Одна вычисляется в первом бинпоиске, вторая - в другом .
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
#include <fstream>
#include <map>
using namespace std ;
 
ifstream cin("apricot.in");
ofstream cout("apricot.out");
 
long long r, u ;
map < long long , long long > f ;
 
long long solve( long long n )
{          
    if( n < 2 )
      return 0 ;
      
    if( f[n] != 0 )
      return f[n];
      
    if( n == 2 )
    {
      f[n] = u ;
      return u ;
    } 
      
    long long L, R, m, f1, f2, ans1 = (long long)1e15, ans2 = (long long)1e15 ;
    
    //Первый бинпоиск
    L = 1 ; R = n/2 ;
    while( L <= R )
    {     
      m = ( L+R+1 )/2 ; 
          
      f1 = solve( n - 2*m );
      f2 = solve( m ) ;
      
      long long rr = ( m == ( n+1 ) / 2 ? 0 : r ) ;
      
      if( rr + f1 >= u + f2 )
      {   
        ans1 = min( ans1, rr + f1 ) ;
        if( L == R )
          break ;
        L = m ;
      }
      else
      {
        if( L == R )
          break ;
        R = m - 1 ;
      }
    }
    
    //Второй бинпоиск
    L = 1 ; R = n/2 ;   
    while( L <= R )
    {  
      m = ( L+R )/2 ; 
          
      f1 = solve( n - 2*m );
      f2 = solve( m ) ;
      
      long long rr = ( m == ( n+1 ) / 2 ? 0 : r ) ;
      
      if( rr + f1 <= u + f2 )
      {
        ans2 = min( ans2, u + f2 ) ;
        if( L == R )
          break ;
        R = m ;
      }
      else
      {
        if( L == R )
          break ;
        L = m + 1 ;
      }
    } 
    
    f[n] = min( ans1, ans2 ) ;
    return f[n] ;  
}
 
int main()
{
      long long n ;
      
      cin >> n >> r >> u ;
      
      cout << solve( n );
}


Добавлено через 2 часа 38 минут
Подчистил код
vndtta
70 / 47 / 5
Регистрация: 17.10.2011
Сообщений: 152
Завершенные тесты: 1
23.05.2012, 10:29     Задача "Урюк" #16
Цитата Сообщение от AncinetHero Посмотреть сообщение
Нет, я был не прав. В половине u > r в половине наоборот.
Мое решение не верно.

Добавлено через 3 часа 35 минут
Мое новое решение проходит пока что 11 первых тестов, 1 второй и 1 третий (на остальных ВА )

Добавлено через 12 минут
Оно следущее:
Пусть у нас есть n камней, даны r и u . Обозначим через f( n ) - минимальное количество урюка, с помощью которого гарантированно будет обнаружена фальшивая монета в кучке размером в n монет.

Попробуем вычислить значение этой функции через предыдущие значения. Допустим, мы решили взять 2 кучки по a камней ( a <= n/2 ) из данных нам n монет. Тогда может быть:

1) a = a То есть кучки сравнялись и среди кучек нет фальшивой монеты. Тогда f( n ) = f( n - 2*a ) + r ( осталось n - 2*a монет, ищем там фальшивую )

2) a <> a То есть в одной из кучек фальшивая монета. Тогда f( n ) = f( a ) + U

Мы должны рассмотреть худший случай, то есть максимальное значение f( n ) для этого a . То есть найти максимум среди f( n - 2*a ) + r и f( a ) + U .

Теперь рассмотрим решение для произвольного a .

1) Пусть f( n - 2*a ) + r > f( a ) + U . Тогда f( n ) = f( n - 2*a ) + r.

Нам нужно найти минимум f( n ) ( следуя условию нужно найти минимальное количество урюка ) . Минимум f( n ) достигается при минимуме f( n - 2*a ).

Тут я предположил, что минимум f( n - 2*a ) достигается при минимуме n - 2*a, а иначе при максимуме a, то есть я предположил, что функция f( x ) возрастает при увеличении x .
Update. Это действительно так.

Тогда можно перебирать всемозножные a бинарным поиском от 1 до n/2 и найти такое максимальное а, что f( n - 2*a ) + r > f( a ) + U .

2)Аналогично предпологается, что f( n - 2*a ) + r < f( a ) + U . Тогда f( n ) = f( a ) + U.

Краевые значения f( i ) = 0, i <= 1 и f( 2 ) = u .

То есть весь алгоритм:

- для каждого n бинарным поиском сначала ищется максимальное a, для которого выполняется f( n - 2*a ) + r > f( a ) + U

- для каждого n бинарным поиском ищется минимальное a, для которого выполняется f( n - 2*a ) + r < f( a ) + U

- ответом будет являтся минимум из f( n - 2*a ) + r ( то значение которое получили при первом бинпоиске ) и f( a ) + U ( при втором )

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

Добавлено через 23 секунды
Поищите ошибку, пожалуйста

Добавлено через 11 минут
Ура! Подправил ошибку и прошло более половины тестов:
16 первой группы, 5 второй группы, 4 последней группы

Но все же ошибка где-то есть. И, кстати, на 3 тестах в конце ТЛЕ.

Добавлено через 1 час 14 минут
Пофиксил все ошибки... Итого - 17 тестов первых тестов, 9 вторых, 5 третих. Остальные 19 тестов не могу сдать. Думаю, решение правильное, описано сверху.

Код
Писал на Dev-C++.
В map'е для ускорения хранятся уже ранее вычисленные значения solve( n ) чтобы не пересчитывать их. Внутри функции solve - R, L, m - переменные для бинпоиска, после цикла бинпоиска( их два, как я и писал выше ) еще раз проверяю подходит ли значение. ans1 , ans2 - переменные для двух вариантов, что тоже описано выше. Одна вычисляется в первом бинпоиске, вторая - в другом .
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
#include <fstream>
#include <map>
using namespace std ;
 
ifstream cin("apricot.in");
ofstream cout("apricot.out");
 
long long r, u ;
map < long long , long long > f ;
 
long long solve( long long n )
{          
    if( n < 2 )
      return 0 ;
      
    if( f[n] != 0 )
      return f[n];
      
    if( n == 2 )
    {
      f[n] = u ;
      return u ;
    } 
      
    long long L, R, m, f1, f2, ans1 = (long long)1e15, ans2 = (long long)1e15 ;
    
    //Первый бинпоиск
    L = 1 ; R = n/2 ;
    while( L <= R )
    {     
      m = ( L+R+1 )/2 ; 
          
      f1 = solve( n - 2*m );
      f2 = solve( m ) ;
      
      long long rr = ( m == ( n+1 ) / 2 ? 0 : r ) ;
      
      if( rr + f1 >= u + f2 )
      {   
        ans1 = min( ans1, rr + f1 ) ;
        if( L == R )
          break ;
        L = m ;
      }
      else
      {
        if( L == R )
          break ;
        R = m - 1 ;
      }
    }
    
    //Второй бинпоиск
    L = 1 ; R = n/2 ;   
    while( L <= R )
    {  
      m = ( L+R )/2 ; 
          
      f1 = solve( n - 2*m );
      f2 = solve( m ) ;
      
      long long rr = ( m == ( n+1 ) / 2 ? 0 : r ) ;
      
      if( rr + f1 <= u + f2 )
      {
        ans2 = min( ans2, u + f2 ) ;
        if( L == R )
          break ;
        R = m ;
      }
      else
      {
        if( L == R )
          break ;
        L = m + 1 ;
      }
    } 
    
    f[n] = min( ans1, ans2 ) ;
    return f[n] ;  
}
 
int main()
{
      long long n ;
      
      cin >> n >> r >> u ;
      
      cout << solve( n );
}


Добавлено через 2 часа 38 минут
Подчистил код
первое что приходит в голову - это что f(x) не монотонна, там возможны такие последовательности ...8889899999...
второе - ты не использовал разность R и U, т.е. случай когда одно больше другого и наоборот

щас сам еще подумаю как делать

Добавлено через 1 час 1 минуту
если R>U , тогда нужно искать минимум f(a)(или максимум f(n-2*a) кстати f(n-2*a) должна быть монотонна), такой что f(a)+R>=f(n-2*a)+U
если U>R, тогда нужно искать максимум f(a)(или минимум f(n-2*a)), такой что f(a)+R<=f(n-2*a)+U

т.е. нужно найти такое а, чтобы f(a)+R и f(n-2*a)+U различались максимум на 1, а лучше были равны
и поиск нужно начинать от n/3 к 1 или к n/2 - зависит от R-U

по индексам по a выйдет от [(n+2)/3] к 1 если R>U пока f(a)+R>=f(n-2*a)+U
либо от [n/3] к [n/2] если R<U пока f(a)+R<=f(n-2*a)+U
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
23.05.2012, 12:58     Задача "Урюк" #17
Цитата Сообщение от vndtta Посмотреть сообщение
первое что приходит в голову - это что f(x) не монотонна, там возможны такие последовательности ...8889899999...
второе - ты не использовал разность R и U, т.е. случай когда одно больше другого и наоборот
Она возрастающая, для фиксированных r и u я перебрал множество n и ответ возрастал. Попробуй привести контрпример, я не нашел!

Разность R и U не имеет значения, рассматривается лишь суммы r + f( n - 2*a ) и u + f( a ) . r и u по отдельности не имеют значения. Я раньше тоже так думал, потом пришел к последнему!
vndtta
70 / 47 / 5
Регистрация: 17.10.2011
Сообщений: 152
Завершенные тесты: 1
23.05.2012, 14:10     Задача "Урюк" #18
Цитата Сообщение от AncinetHero Посмотреть сообщение
Она возрастающая, для фиксированных r и u я перебрал множество n и ответ возрастал. Попробуй привести контрпример, я не нашел!

Разность R и U не имеет значения, рассматривается лишь суммы r + f( n - 2*a ) и u + f( a ) . r и u по отдельности не имеют значения. Я раньше тоже так думал, потом пришел к последнему!
я те показал как сделать так чтоб перебора меньше было, учитывая разность r-u

а на возрастание я те щас прогу напишу с выводом - с полным перебором

код
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
#include <iostream>
using namespace std;
 
int x[100];
int N=15;
int U=2;
int R=3;
 
int main()
{
 
 x[0]=0;
 x[1]=0;
 x[2]=U;
 x[3]=(R>U)?R:U;
 for(int i=4;i<40;i++){
  x[i]=1000000000;
  int min=0;
  for(int j=1;i-2*j>1;j++)
  {
   if (R+x[i-2*j]>U+x[j]) min=R+x[i-2*j];
   else min=U+x[j];
   if (min<x[i]) x[i]=min;
  }
 }
 for(int i=1;i<40;i++) cout<<x[i]<<" ";
 return 0;
}
вывод
C++
1
0 2 3 5 6 5 6 5 6 7 7 8 8 7 7 8 8 7 7 8 8 8 9 8 9 8 9 9 9 9 9 9 9 9 9 9 9 9 9
Добавлено через 30 минут
Цитата Сообщение от vndtta Посмотреть сообщение
код
код
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
#include <iostream>
using namespace std;
 
int x[100];
int N=15;
int U=2;
int R=3;
 
int main()
{
 
 x[0]=0;
 x[1]=0;
 x[2]=U;
 x[3]=(R>U)?R:U;
 for(int i=4;i<40;i++){
  x[i]=1000000000;
  int min=0;
  for(int j=1;i-2*j>1;j++)
  {
   if (R+x[i-2*j]>U+x[j]) min=R+x[i-2*j];
   else min=U+x[j];
   if (min<x[i]) x[i]=min;
  }
 }
 for(int i=1;i<40;i++) cout<<x[i]<<" ";
 return 0;
}
вывод
C++
1
0 2 3 5 6 5 6 5 6 7 7 8 8 7 7 8 8 7 7 8 8 8 9 8 9 8 9 9 9 9 9 9 9 9 9 9 9 9 9
блин код не рабочий
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
23.05.2012, 15:57     Задача "Урюк" #19
Рабочий, Dev-cpp скачай и запусти..возможно не работает потому что ты не создал входной файл в директории программы. Это программа, которую я посылал на сдачу, так что создай файлы .in и в .out будет ответ. Из за отсутствия входного файла ошибка и возникает.

Добавлено через 1 минуту
Программа неправильно твоя работает.

Посмотри при тесте 4 3 2 у тебя ответ 5, а правильный ответ - 4 . Потому что мы будем делить на 2 кучки постоянно и они будут разных масс.

Добавлено через 6 минут
Аа ты про свой код) А я то думал..
Да он не рабочий, потому что ты не добавил еще один поиск. У тебя внутри цикла один цикл, а должно быть два цикла, мы же два раза ищем ответ, по моему алгоритму по крайней мере. Плюс тебе надо искать максимум и минимум, а break у тебя я не вижу..и цикл по j тогда уж нужно начинать с максимума и j уменьшать до 1 если не нашли ответ.

Добавлено через 13 минут
Вот тупой перебор: (очевидно, будет ТЛЕ)
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
#include <fstream>
#include <vector>
using namespace std ;
 
ifstream cin("apricot.in");
ofstream cout("apricot.out");
 
int main()
{
      long long N, n, r, u, j, ans ;
      
      cin >> N >> r >> u ;
      
      vector < long long > f( N+1 );
      
      f[2] = u ;
      for( n = 3 ; n <= N ; n++ )
      {
           ans = ( long long ) 1e15 ;
           
           for( j = ( n + 1 )/2 - 1 ; j >= 1 ; j -- )
                if( r + f[ n - 2*j ] >= u + f[ j ] )
                {
                    ans = min( ans, r + f[ n - 2*j ] );
                    break ;
                }
                
           for( j = 1 ; j <= ( n + 1 )/2 - 1 ; j ++ )
                if( r + f[ n - 2*j ] <= u + f[ j ] )
                {
                    ans = min( ans, u + f[ j ] );
                    break ;
                }
           
           if( n % 2 == 0 )
                ans = min( ans, f[ n/2 ] + u ) ;     
                
           f[n] = ans ;
      }
      
      cout << f[ N ];
}
Я его отослал, прошел 18 тестов \ 9 тестов \ 1 тест. В среднем хуже, но в 1 категории больше набрал

ВА всего в 5-6 тестах, на последних везде ТЛЕ.

Добавлено через 4 минуты
В общем нужно найти некие, возможно, исключения из правил + оптимизировать бинпоиск, я думаю. Если бы кто то нашел контрпример было бы здорово

Добавлено через 3 минуты
Тут сложность квадрат, интерестно какая сложность у бинпоиска? Ответ для любого n мы вычисляем за логарифм если все предыдущие необходимые значения уже вычислены, интерестно, а сколько предыдущих значений обязательно нужно вычислить? Все от 1 до n или некоторые?

Добавлено через 2 минуты
Ух. Вольфрам альфа сказал, что это log( n! ) ( двоичный логарифм ), если нужно вычислить полностью все предыдущие значения. Все таки интерестно, обязательно ли все вычислять.
http://www.wolframalpha.com/input/?i...r+i+%3D+1+to+n
А как оценить логарифм факториала?

По идее задача должна решаться за O( N )

Добавлено через 17 минут
Ура. Я понял. Закономерность есть и не сложна.

Вернемся к предыдущему решению. Пусть мы решили задачу для ( n-1 ) и нашли некое a . Тогда чтобы решить задачу для следующего n мы просто попробуем взять то же a и проверим подходит оно или нет!

Вот новый код, сложность O( N ) , проходит больше тестов чем все предыдущие!
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
#include <fstream>
#include <vector>
using namespace std ;
 
ifstream cin("apricot.in");
ofstream cout("apricot.out");
 
int main()
{
      long long N, n, r, u, last_a[2], ans ;
      
      cin >> N >> r >> u ;
      
      vector < long long > f( N+1 );
      
      if( N == 2 )
      {
        cout << u ;
        return 0 ;
      }
      
      f[2] = u ;
      
      last_a[0] = last_a[1] = 1 ;
      
      for( n = 3 ; n <= N ; n++ )
      {
           ans = ( long long ) 1e15 ;
           
           if( n - 2*( last_a[0]+1 ) >= 0 && r + f[ n - 2*( last_a[0]+1 ) ] >= u + f[ last_a[0]+1 ] )
           {
              ans = min( ans, r + f[ n - 2*( last_a[0]+1 ) ] );
              last_a[0]++ ;
           }
           else if( n - 2*last_a[0] >= 0 && r + f[ n - 2*last_a[0] ] >= u + f[ last_a[0] ] )
              ans = min( ans, r + f[ n - 2*last_a[0] ] );
                
           if( n - 2*last_a[1] >= 0 && r + f[ n - 2*last_a[1] ] <= u + f[ last_a[1] ] )
              ans = min( ans, u + f[ last_a[1] ] );
           else if( n - 2*( last_a[1]+1 ) >= 0 && r + f[ n - 2*( last_a[1]+1 ) ] <= u + f[ last_a[1]+1 ] )
           {
              ans = min( ans, u + f[ last_a[1]+1 ] );
              last_a[1]++ ;
           }
           
           if( n % 2 == 0 )
                ans = min( ans, f[ n/2 ] + u ) ;     
                
           f[n] = ans ;
      }
      
      cout << f[ N ];
}
17 \ 9 \ 8
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2012, 17:26     Задача "Урюк"
Еще ссылки по теме:

C++ Создать класс "Книга" с полями "название книги", "количество страниц", "год издания"
Создать иерархию классов "Фирма", "Бухгалтер", "Сотрудник", "Зарплата" C++
C++ Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления"
Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" C++
C++ Задача на нахождение "+" и "-" элементов в массиве

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

Или воспользуйтесь поиском по форуму:
vndtta
70 / 47 / 5
Регистрация: 17.10.2011
Сообщений: 152
Завершенные тесты: 1
23.05.2012, 17:26     Задача "Урюк" #20
Цитата Сообщение от AncinetHero Посмотреть сообщение
17 \ 9 \ 8
я твою предыдущую функцию переписал, посмотри ка ее, а то чтоб самому проверить - походу зарегистрироваться надо
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
int solve( int n )
{
    if( n < 2 )       return 0 ;
    if( f[n] != 0 )      return f[n];
    if( n == 2 ){
      f[n] = u ;
      return u ;
    } 
 
    int L, M, R, min=0, f1=0, f2=0;
    L=1;M=n/3;R=n/2;
 
    if (u>r){
        min=1000000000;
        for(int i=M;i>=L;i--)
        {
            f1=solve(i);
            f2=solve(n-2*i);
            if ( n==2*i ) min=f1+u;
            else if ( (f1+u) >= (f2+r) ) min=f1+u;
            else
            {
                if ( min > f2+r ) min=f2+r;
                break;
            }
        }
    }
    else{
        min=1000000000;
        for(int i=M;i<=R;i++)
        {
            f1=solve(i);
            f2=solve(n-2*i);
            if ( n==2*i ) min=f1+u;
            else if ( (f1+u) <= (f2+r) ) min=f2+r;
            else
            {
                if ( min > f1+u ) min=f1+u;
                break;
            }
        }
    }
    f[n]=min;
    return min;  
}
Добавлено через 14 минут
Цитата Сообщение от AncinetHero Посмотреть сообщение
Аа ты про свой код) А я то думал..
Да он не рабочий, потому что ты не добавил еще один поиск. У тебя внутри цикла один цикл, а должно быть два цикла, мы же два раза ищем ответ, по моему алгоритму по крайней мере. Плюс тебе надо искать максимум и минимум, а break у тебя я не вижу..и цикл по j тогда уж нужно начинать с максимума и j уменьшать до 1 если не нашли ответ.
да не, там проверки когда i-2*j=0 не хватает
код
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
#include <iostream>
using namespace std;
 
int x[100];
int N=15;
int U=2;
int R=3;
 
int main()
{
 
 x[0]=0;
 x[1]=0;
 x[2]=U;
 x[3]=(R>U)?R:U;
 for(int i=4;i<40;i++){
  x[i]=1000000000;
  int min=0;
  for(int j=1;i-2*j>1;j++)
  {
   if (R+x[i-2*j]>U+x[j]) min=R+x[i-2*j];
   else min=U+x[j];
   if (min<x[i]) x[i]=min;
  }
  if (0==i%2) {if (min>x[i/2]) min=R+x[i/2];}
 }
 for(int i=1;i<40;i++) cout<<x[i]<<" ";
 return 0;
}
Yandex
Объявления
23.05.2012, 17:26     Задача "Урюк"
Ответ Создать тему
Опции темы

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