С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

Ребят, всем привет, помогите пожалуйста задачу решить
http://imcs.dvgu.ru/cats/static/problem_text-cpid-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 баллов
Подскажите пожалуйства в чем ошибка или посоветуйте другое решение, заранее благодарен
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2012, 10:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача "Урюк" (C++):

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

29
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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
0
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 по отдельности не имеют значения. Я раньше тоже так думал, потом пришел к последнему!
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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
блин код не рабочий
0
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
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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;
}
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
23.05.2012, 18:20 #21
http://imcs.dvgu.ru/cats/main.pl?f=r...060;cid=850112

14 \ 6 \ 1

Добавлено через 1 минуту
Блин, не понимаю где ошибка в решении. ( в алгоритме ) Чего так много ВА всегда..

Добавлено через 2 минуты
Блин. Ты был прав про функцию, она не возрастающая на любых промежутках. Не знаю как решать, все остальные решения заходили из-за корявых тестов.

Добавлено через 20 минут
Я придумал еще одно решение) Прошло 20 \ 9 \ 3

Добавлено через 8 минут
Тупой перебор, который я писал раньше, с исправлением ошибок - 20 11 1
Всего 4 ВА! Это значит, что алгоритм верный.
Неверно было лишь то, что при увеличении х , f( x ) возрастает . Простой перебор всех возможных кучек все-таки проходит, а значит нужно просто упростить задачу. Пока что сложность квадрат.

Добавлено через 2 минуты
Функция НЕ возрастает. Контрпример 100 100 1
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
24.05.2012, 09:43 #22
Цитата Сообщение от AncinetHero Посмотреть сообщение
Функция НЕ возрастает. Контрпример 100 100 1
тут еще нюанс есть
вот например у нас N=100, R=100, U=1
тогда при промежуточном подсчете для f(3) f(3)=100, но если добавить 1 монету то f(3)=f(4)=2
как то так, т.е. если N=3 f(3)=100 а если N>3 то f(3)=2

это кстати значит, что придется считать все промежуточные значения

Добавлено через 21 минуту

попробуй так
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
int r, u ;
map < int , int > f ;
 
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;  
}
 
int main()
{
      int n ;
      
      n=100;
      r=100;
      u=1;
      for(int i=1;i<n;i++){
       solve(i);
       //cout<<f[i]<<" ";
       for(int k=i-1;f[k]>f[i] && k>2 ;k--) f[k]=f[i];
      }
      cout<<endl;      
      //for(int l=1;l<n;l++) cout << solve( l ) << " ";
      cout<<endl<<solve(n);
}
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
24.05.2012, 12:12 #23
Везде ВА.
0
Demsol
43 / 43 / 9
Регистрация: 16.11.2011
Сообщений: 125
24.05.2012, 17:01  [ТС] #24
Теперь проходит первые 7 тестов, и еще 2 в середине. Остальные WA
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
24.05.2012, 20:01 #25
Что проходит?

Добавлено через 18 секунд
Какой то "внезапный" пост.
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
25.05.2012, 09:34 #26
вобщем я зарегался там
и
вот это
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
#include <fstream> 
#include <map> 
using namespace std ;
 
ifstream cin("apricot.in");
ofstream cout("apricot.out");
 
  
int N, r, u, pos ;
map < int , int > f ; 
   
#define MIN(x,y) ((x<y)?x:y)
#define MAX(x,y) ((x>y)?x:y)
   
int solve( int n )
{
    if( n < 2 )       return 0 ;
    if( f[n] != 0 )      return f[n];
 
    int L, M, R, min=0, f1=0, f2=0;
    L=1;M=n/3;R=n/2;
 
    if ( f[pos]+u == f[n-2*pos]+r ) min=f[pos]+u;
    else if ( f[pos]+u < f[n-2*pos]+r )
    {
        for(min=100000000; (f[pos]+u<f[n-2*pos]+r ) && (pos<=(n+1)/2) && (pos<=N/2) ; pos++);
        if (2*pos>=n) min=f[pos]+u;
        else min=MAX(f[pos]+u,f[n-2*pos]+r);
        if (pos>1) min=MIN(min,MAX(f[pos-1]+u,f[n-2*pos+2]+r));
    }
    else if ( f[pos]+u > f[n-2*pos]+r )
    {
        for(min=100000000; (f[pos]+u>f[n-2*pos]+r ) && (pos>1); pos--);
        if (2*(pos+1)>=n) min=f[pos]+u;
        else min=MAX(f[pos+1]+u,f[n-2*pos-2]+r);
        min=MIN(MAX(f[pos]+u,f[n-2*pos]+r),min);
    }
    
    f[n]=min;
    return min;  
} 
 
   
int main() 
{ 
    int n ; 
    cin>>n>>r>>u;     
    N=n;pos=1;
    
    f[1]=0;f[2]=u;
    f[4]=MIN((u+u),(r+u));
    f[3]=MIN(MAX(u,r),f[4]);
    
    for(int i=5;i<n;i++) solve(i);
    cout<<solve(n);
 
    return 0;
}
сдал
19/11/9
3 TLE остальные WA
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
25.05.2012, 10:11 #27
Опиши, пожалуйста, что ты добавил, а то по коду мне ничего не понять!

Добавлено через 1 минуту
Кстати тебе тут map вообще не нужен, убери его и создай массив. Просто занесение элемента в map и проверка его присутствия там осуществляется за логарифм, поэтому, возможно и 3 ТЛЕ.

Добавлено через 36 секунд
Я использовал map чтобы заносить туда некоторые значения, а ты высчитываешь от 1 до n.
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
25.05.2012, 10:23 #28
Цитата Сообщение от 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
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
#include <fstream> 
#include <map> 
using namespace std ;
 
ifstream cin("apricot.in");
ofstream cout("apricot.out");
 
  
int N, r, u, pos ;
map < int , int > f ; 
   
#define MIN(x,y) ((x<y)?x:y)
#define MAX(x,y) ((x>y)?x:y)
   
int solve( int n )
{
    if( n < 2 )       return 0 ;
    if( f[n] != 0 )      return f[n];
 
    int L, M, R, min=0, f1=0, f2=0;
    L=1;M=n/3;R=n/2;
 
    if ( f[pos]+u == f[n-2*pos]+r ) min=f[pos]+u;
    else if ( f[pos]+u < f[n-2*pos]+r )
    {
        for(min=100000000; (f[pos]+u<f[n-2*pos]+r ) && (pos<=(n+1)/2) && (pos<=N/2) ; pos++);
        if (2*pos>=n) min=f[pos]+u;
        else min=MAX(f[pos]+u,f[n-2*pos]+r);
        if (pos>1) min=MIN(min,MAX(f[pos-1]+u,f[n-2*pos+2]+r));
    }
    else if ( f[pos]+u > f[n-2*pos]+r )
    {
        for(min=100000000; (f[pos]+u>f[n-2*pos]+r ) && (pos>1); pos--);
        if (2*(pos+1)>=n) min=f[pos]+u;
        else min=MAX(f[pos+1]+u,f[n-2*pos-2]+r);
        min=MIN(MAX(f[pos]+u,f[n-2*pos]+r),min);
    }
    
    f[n]=min;
    return min;  
} 
 
   
int main() 
{ 
    int n ; 
    cin>>n>>r>>u;     
    N=n;pos=1;
    
    f[1]=0;f[2]=u;
    f[4]=MIN((u+u),(r+u));
    f[3]=MIN(MAX(u,r),f[4]);
    
    for(int i=5;i<n;i++) solve(i);
    cout<<solve(n);
 
    return 0;
}
сдал
19/11/9
3 TLE остальные WA
я заменил вот это
C++
1
for(min=100000000; (f[pos]+u<f[n-2*pos]+r ) && (pos<=(n+1)/2) && (pos<=N/2) ; pos++);
на
C++
1
for(min=100000000; (f[pos]+u<f[n-2*pos]+r ) && (pos<=(n+1)/2) && (pos<N/2) ; pos++);
и тепер 21/14/10 2 WA 3 TLE

Добавлено через 7 минут
Цитата Сообщение от AncinetHero Посмотреть сообщение
Опиши, пожалуйста, что ты добавил, а то по коду мне ничего не понять!

Добавлено через 1 минуту
Кстати тебе тут map вообще не нужен, убери его и создай массив. Просто занесение элемента в map и проверка его присутствия там осуществляется за логарифм, поэтому, возможно и 3 ТЛЕ.

Добавлено через 36 секунд
Я использовал map чтобы заносить туда некоторые значения, а ты высчитываешь от 1 до n.
я скорее убрал ного чего

тут проверка по предыдущему решению есть
т.е. сохранена минимальная конфигурация f[n]=f[pos]+u=f[n-2*pos]+r
следующий шаг это проверка для f[n+1] - f[pos]+u ? f[n+1-2*pos]+r
если равно значит ответ уже найден
если больше идем по индексу pos влево - при этом f[pos]+u уменьшается, а f[n+1-2*pos]+r
увеличивается
если меньше - идем по индексу pos вправо

если идем по индексу pos вправо то ограничиваем себя индексом (n+1)/2 т.е. типа знимаем одну монетку из проверенных
это устраняет немнотонность промежуточных значений
для нечетных очень полезно
вот пример
у нас 100 100 1
f[63]=100 если мы возьмем две кучки по 31 и сравним
а если добавить 1 доп. монету то f[63]=f[64]=1+f[32]=2+f[16]=..=7
но если у нас 127 100 1
то для 127 неоткуда взять еще одну монету, поэтому есть еще ограничение по индексу N/2

насчет map, если так не нарвится замени на int[1000000]
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
02.06.2012, 11:35 #29
Ап. Ищем умных программистов.
0
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.06.2012, 09:46 #30
Могу дать небольшую подсказку. Я немного потестировал эту задачу на сайте и выяснил, что есть такие случаи:
например имеем кучку с фальшивой монетой и уже проверенную кучу без фальшивой монеты. Так вот иногда выгоднее продолжать работать не просто с кучей, где есть фальшивая монета, а добавить одну или несколько монет из проверенной кучи в кучу с фальшивой монетой.
0
04.06.2012, 09:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.06.2012, 09:46
Привет! Вот еще темы с ответами:

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Реализовать структуру "Анкета" с полями "Фамилия", "Пол" и "Адрес" - C++
Здравствуйте. Проходим тему Структуры, не могу понять, как определить количество, само задание: #include &lt;iostream&gt; #include...

по строкам.замените в слове сочетание "му" на "а" , а букву "ы" на "ца". очень нужно - C++
замените в слове сочетание &quot;му&quot; на &quot;а&quot; , а букву &quot;ы&quot; на &quot;ца&quot;. очень нужно Добавлено через 21 час 4 минуты неужели никто не знает...


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.