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

@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 баллов
Подскажите пожалуйства в чем ошибка или посоветуйте другое решение, заранее благодарен

@AncinetHero · 23.05.2012, 18:20

http://imcs.dvgu.ru/cats/main.... cid=850112

14 \ 6 \ 1

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

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

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

Я придумал еще одно решение) Прошло 20 \ 9 \ 3

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

Добавлено через 2 минуты
Функция НЕ возрастает. Контрпример 100 100 1

@vndtta · 24.05.2012, 09:43

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

@AncinetHero · 24.05.2012, 12:12

Везде ВА.

@Demsol · 24.05.2012, 17:01 **[ТС]**

Теперь проходит первые 7 тестов, и еще 2 в середине. Остальные WA

@AncinetHero · 24.05.2012, 20:01

Что проходит?

Добавлено через 18 секунд
Какой то "внезапный" пост.

@vndtta · 25.05.2012, 09:34

вобщем я зарегался там
и

вот это

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

@AncinetHero · 25.05.2012, 10:11

Опиши, пожалуйста, что ты добавил, а то по коду мне ничего не понять!

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

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

@vndtta · 25.05.2012, 10:23

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

@AncinetHero · 02.06.2012, 11:35

Ап. Ищем умных программистов.

valeriikozlov · 04.06.2012, 09:46

Могу дать небольшую подсказку. Я немного потестировал эту задачу на сайте и выяснил, что есть такие случаи:
например имеем кучку с фальшивой монетой и уже проверенную кучу без фальшивой монеты. Так вот иногда выгоднее продолжать работать не просто с кучей, где есть фальшивая монета, а добавить одну или несколько монет из проверенной кучи в кучу с фальшивой монетой.

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

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

	Задача "Урюк" 27.04.2012, 10:53. Показов 3371. Ответов 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

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	23.05.2012, 18:20
	http://imcs.dvgu.ru/cats/main.... cid=850112 14 \ 6 \ 1 Добавлено через 1 минуту Блин, не понимаю где ошибка в решении. ( в алгоритме ) Чего так много ВА всегда.. Добавлено через 2 минуты Блин. Ты был прав про функцию, она не возрастающая на любых промежутках. Не знаю как решать, все остальные решения заходили из-за корявых тестов. Добавлено через 20 минут Я придумал еще одно решение) Прошло 20 \ 9 \ 3 Добавлено через 8 минут Тупой перебор, который я писал раньше, с исправлением ошибок - 20 11 1 Всего 4 ВА! Это значит, что алгоритм верный. Неверно было лишь то, что при увеличении х , f( x ) возрастает . Простой перебор всех возможных кучек все-таки проходит, а значит нужно просто упростить задачу. Пока что сложность квадрат. Добавлено через 2 минуты Функция НЕ возрастает. Контрпример 100 100 1 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	24.05.2012, 12:12
	Везде ВА. 0

@Demsol 43 / 43 / 14 Регистрация: 16.11.2011 Сообщений: 125
	24.05.2012, 17:01 [ТС]
	Теперь проходит первые 7 тестов, и еще 2 в середине. Остальные WA 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	24.05.2012, 20:01
	Что проходит? Добавлено через 18 секунд Какой то "внезапный" пост. 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	25.05.2012, 10:11
	Опиши, пожалуйста, что ты добавил, а то по коду мне ничего не понять! Добавлено через 1 минуту Кстати тебе тут map вообще не нужен, убери его и создай массив. Просто занесение элемента в map и проверка его присутствия там осуществляется за логарифм, поэтому, возможно и 3 ТЛЕ. Добавлено через 36 секунд Я использовал map чтобы заносить туда некоторые значения, а ты высчитываешь от 1 до n. 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	02.06.2012, 11:35
	Ап. Ищем умных программистов. 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	04.06.2012, 09:46
	Могу дать небольшую подсказку. Я немного потестировал эту задачу на сайте и выяснил, что есть такие случаи: например имеем кучку с фальшивой монетой и уже проверенную кучу без фальшивой монеты. Так вот иногда выгоднее продолжать работать не просто с кучей, где есть фальшивая монета, а добавить одну или несколько монет из проверенной кучи в кучу с фальшивой монетой. 0