Задача "Урюк"

@Demsol · Регистрация: 16.11.2011

Студворк — интернет-сервис помощи студентам

Ребят, всем привет, помогите пожалуйста задачу решить
http://imcs.dvgu.ru/cats/stati... 50202.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 баллов
Подскажите пожалуйства в чем ошибка или посоветуйте другое решение, заранее благодарен

@Demsol · 28.04.2012, 11:39 **[ТС]**

upppp!!!

@-=ЮрА=- · 28.04.2012, 13:14

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 · 15.05.2012, 12:20 **[ТС]**

Твое решение неверно, "рандом умным не бывает(с)", нужно найти МИНИМАЛЬНОЕ количество урюка.
Проходит оно несколько тестов в середине, каждый раз они меняются. В среднем, это еще меньшее количество баллов чем у меня. Меня натолкнуло на мысль, если например N это степень двойки, и R и U сильно различаются, то решение рекурентным соотношением уже может быть неверным, (тесты скорее всего так и подобраны), нужно еще хорошо подумать.
Но все равно спасибо вам )

@-=ЮрА=- · 15.05.2012, 12:49

[OFF]Demsol,

Сообщение от Demsol

нужно найти МИНИМАЛЬНОЕ количество урюка.

- минимально количество урюка говоришь - тогда 1 на одной чаше весов все деньги а на другой фальшивая монета.

"рандом умным не бывает(с)"

- рандомно как раз моделируем реальные случаи разложения монет по кучам - надеюсь слышал такие понятия как событие, вероятность и прочее. В комбинаторике рандом положен во главу краеугольных камней всех выкладок, а ты мне тут свои копирайты подсовываешь...Если бы раскрыл глаза то увидел что для малого числа моент резултаты совпадают 1 к 1-му а для больше числа моент результаты поданные в ответах часто "проскакивают", как раз всё зависит от "настроения рандома".

Сообщение от Demsol

Меня натолкнуло на мысль, если например N это степень двойки

- кто тебе вообще это сказал что монет в куче под степень двойки - потому что так хочется?
А если в куче будет 4097 или 4098 монет или просто три - тоже под степень двойки говоришь

MrGluck · 15.05.2012, 15:38

Я бы делил вобще на 3 кучи и сравнивал. Если взвешиваемые кучи не равны - весы покажут. Если равны - монета в куче, которую не взвешивали.

valeriikozlov · 15.05.2012, 21:52

Сообщение от MrGluck

Я бы делил вобще на 3 кучи и сравнивал. Если взвешиваемые кучи не равны - весы покажут. Если равны - монета в куче, которую не взвешивали.

Не все так просто. Этим можно добится минимального количества взвешиваний, но не минимальное количество урюка. Пример: 9 монет, R=1, U=1000000.
Деля на на три кучки можно найти монету за два взвешивания, но урюка получится 2000000.
А если брать по 2 монеты, взвешивать только их, то получится 4 взвешивания, но всего 1000003 урюка.

@Demsol · 22.05.2012, 10:36 **[ТС]**

To-=ЮрА=-

- минимально количество урюка говоришь - тогда 1 на одной чаше весов все деньги а на другой фальшивая монета.

Минимальное кол-во урюка, необходимого для 100% выявления фальшивой монеты. Т.е. нужно разделить кол-во взвешиваний на наименее затратное, и из этой комбинации выбрать наихудший случай.

всё зависит от "настроения рандома".

Ну если ты слышал о правилах проведения всерос олимпиад, то жюри вправе сколь угодно много запускать твое решение и проверять его правильность. Если в структуре присутсвует рандом, то вероятнее всего так и будет. Если интересно, решение проходит(точно уже не помню) 5-6 тестов из примерно 30. Ну при "хорошем настроении рандома" впринципе можно 7-8 баллов получить, но не больше. Да для небольших N вероятность совпадения велика, а если для N=10^6? Да и вобще, если бы олимпиада была acm'овской, то такое решение НИКОГДА бы не получило правильности, надеюсь догадываешься почему.

кто тебе вообще это сказал что монет в куче под степень двойки - потому что так хочется?

Нет не потому что так хочется, а потому что такой случай наиболее прост и удобен в ручном разборе и его я выбрал для объяснения самому себе неправильности рекурентного соотношения. Да и вобще

если НАПРИМЕР N это степень двойки, и R и U СИЛЬНО РАЗЛИЧАЮТСЯ...

Вот тебе пример valeriikozlov, , N - вобще без разницы какое, R=1, U=1000000.

@AncinetHero · 22.05.2012, 11:10

Не по теме:

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

Добавлено через 8 минут
И еще, где можно сдать задачу, чтобы проверить решение?

@Demsol · 22.05.2012, 11:40 **[ТС]**

В этом году олимпиада проходила в казани, все материалы здесь
http://infoolimp.tatar.ru/abou... олимпиады/

@AncinetHero · 22.05.2012, 11:40

По крайней мере половину задачи можно решить. Если 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 · 22.05.2012, 11:49 **[ТС]**

Ну если хочешь проверить решения, можно тут
http://imcs.dvgu.ru/cats/main.... cid=850112
Но тут только с первого тура задачи

@AncinetHero · 22.05.2012, 12:17

Да у них сайт какой то глючный! Там сдать невозможно. Другую бы ссылку...

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

Добавлено через 1 минуту
Все таки думаю, что во всех остальных 44 тестах: u > r

@Demsol · 22.05.2012, 12:48 **[ТС]**

да нормальный сайт, просто серваки во владике расположены. У меня отлично и без тормозов работает

Добавлено через 4 минуты
хм, ну вот вишь всего 6 тестов проходит, а там задания по блокам развешены, т.е минимально нужно 30 баллов набрать, а так Solution rejected

@AncinetHero · 22.05.2012, 21:40

Нет, я был не прав. В половине 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 · 23.05.2012, 10:29

Сообщение от 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 · 23.05.2012, 12:58

Сообщение от vndtta

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

Она возрастающая, для фиксированных r и u я перебрал множество n и ответ возрастал. Попробуй привести контрпример, я не нашел!

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

@vndtta · 23.05.2012, 14:10

Сообщение от 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 · 23.05.2012, 15:57

Рабочий, 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/in... %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

@vndtta · 23.05.2012, 17:26

Сообщение от 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;
}

Новые блоги и статьи Все статьи Все блоги /
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .

@Demsol 43 / 43 / 14 Регистрация: 16.11.2011 Сообщений: 125

	Задача "Урюк" 27.04.2012, 10:53. Показов 2988. Ответов 29 Метки нет (Все метки) Ребят, всем привет, помогите пожалуйста задачу решить http://imcs.dvgu.ru/cats/stati... 50202.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[2i]= a[i]+U a[2i+1]=max(R, a[i]+U) поэтому по 2 и 3 значению можно собрать массив до милионного элемента Вроде бы логично, но повторюсь что набрал всего 14 баллов Подскажите пожалуйства в чем ошибка или посоветуйте другое решение, заранее благодарен 0

@Demsol 43 / 43 / 14 Регистрация: 16.11.2011 Сообщений: 125
	28.04.2012, 11:39 [ТС]
	upppp!!! 0

@Demsol 43 / 43 / 14 Регистрация: 16.11.2011 Сообщений: 125
	15.05.2012, 12:20 [ТС]
	Твое решение неверно, "рандом умным не бывает(с)", нужно найти МИНИМАЛЬНОЕ количество урюка. Проходит оно несколько тестов в середине, каждый раз они меняются. В среднем, это еще меньшее количество баллов чем у меня. Меня натолкнуло на мысль, если например N это степень двойки, и R и U сильно различаются, то решение рекурентным соотношением уже может быть неверным, (тесты скорее всего так и подобраны), нужно еще хорошо подумать. Но все равно спасибо вам ) 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	15.05.2012, 15:38
	Я бы делил вобще на 3 кучи и сравнивал. Если взвешиваемые кучи не равны - весы покажут. Если равны - монета в куче, которую не взвешивали. 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	22.05.2012, 11:10
	Не по теме: А где можно посмотреть результаты Всероссийской олимпиады и все задачи сразу? Можно ссылку, пожалуйста? Добавлено через 8 минут И еще, где можно сдать задачу, чтобы проверить решение? 0

@Demsol 43 / 43 / 14 Регистрация: 16.11.2011 Сообщений: 125
	22.05.2012, 11:40 [ТС]
	В этом году олимпиада проходила в казани, все материалы здесь http://infoolimp.tatar.ru/abou... олимпиады/ 0

@Demsol 43 / 43 / 14 Регистрация: 16.11.2011 Сообщений: 125
	22.05.2012, 11:49 [ТС]
	Ну если хочешь проверить решения, можно тут http://imcs.dvgu.ru/cats/main.... cid=850112 Но тут только с первого тура задачи 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	22.05.2012, 12:17
	Да у них сайт какой то глючный! Там сдать невозможно. Другую бы ссылку... Добавлено через 21 минуту Прошло 6 первых тестов Добавлено через 1 минуту Все таки думаю, что во всех остальных 44 тестах: u > r 0

@Demsol 43 / 43 / 14 Регистрация: 16.11.2011 Сообщений: 125
	22.05.2012, 12:48 [ТС]
	да нормальный сайт, просто серваки во владике расположены. У меня отлично и без тормозов работает Добавлено через 4 минуты хм, ну вот вишь всего 6 тестов проходит, а там задания по блокам развешены, т.е минимально нужно 30 баллов набрать, а так Solution rejected 0