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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Преобразование кода http://www.cyberforum.ru/cpp-beginners/thread559931.html
Добрый день. Не могли бы вы помочь мне разобраться с таким заданием, заранее Спасибо! По некоторому каналу связи передается сообщение, имеющее вид последовательности нулей и единиц. Из-за помех возможен ошибочный прием некоторых сигналов: нуль может быть воспринят как единица и наоборот. Для повышения вероятности правильного приема сигналов было решено передавать каждый сигнал трижды. Теперь...
C++/CLI Debug компилируется, а Release - нет Есть код, который компилируется в дебаг режиме и отказывается в релиз режиме, пишет следующие ошибки:1>d:\vc\vihretok\vihretok\Def.h(306) : error C2653: Devart: не является именем класса или пространства имен 1>d:\vc\vihretok\vihretok\Def.h(306) : error C2143: синтаксическая ошибка: отсутствие ";" перед "^" 1>d:\vc\vihretok\vihretok\Def.h(306) : error C4430: отсутствует спецификатор типа -... http://www.cyberforum.ru/cpp-beginners/thread559930.html
C++ Тетрис разбор неясностей
Всем доброго времени суток нужна помощь в комментировании желательно как можно подробнее Программы в Visual Studio 2008 всё работает нужны только коментарии!!! Или нужна программа из данной темы http://www.cyberforum.ru/cpp-builder...read78738.html поскольку исходник скачать не удаётся,а имеется только его часть .cpp файл Спасибо за какаю нибудь помощь заранее =) В любом случае благодарен
C++ Вычислить с заданной точностью значение функции , используя ее разложение в ряд:
:impossible: помогите пожалуйста!!! С++
C++ Решение системы http://www.cyberforum.ru/cpp-beginners/thread559890.html
Два задания: Помогите пожалуйста.
C++ Непонятный синтаксис. В VC 2010 вместо int main(int argc, char *argv) написано int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpcmdline, int ncmdshow) Как это расшифровать? подробнее

Показать сообщение отдельно
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
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
 
Текущее время: 20:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru