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

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

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

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

27.04.2012, 10:53. Просмотров 1523. Ответов 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++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

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

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

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

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

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - 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Эксперт С++
7209 / 4375 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
15.05.2012, 15:38 #6
Я бы делил вобще на 3 кучи и сравнивал. Если взвешиваемые кучи не равны - весы покажут. Если равны - монета в куче, которую не взвешивали.
valeriikozlov
Эксперт C++
4669 / 2495 / 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 минут
Подчистил код
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.05.2012, 21:40
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.05.2012, 21:40
Ответ Создать тему
Опции темы

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