Форум программистов, компьютерный форум 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) Как это расшифровать? подробнее

Показать сообщение отдельно
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
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/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
 
Текущее время: 09:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru