Вт, 19.03.2019, 16:55
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

 
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Модератор форуму: Ktara, Bandalak, НІКОЛЯ, volevikt  
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Всеукраїнська олімпіада з інформатики (програмування) (Висталяємо завдання та розв'язки)
Всеукраїнська олімпіада з інформатики (програмування)
Ковальчук_Олександр Дата: Вт, 20.11.2007, 20:07 | Повідомлення № 1
Ветеран спілкування
Повідомлень: 3703
Нагороди: 18
Рейтинг: 209
Шановні учасники форуму! Скоро районна олімпіада по інформатиці. Допоможіть мені та іншим вчителям інформатикам, які погано розуміються на задачах олімпіадного рівня, підвищити свої знання в області програмування.

Увага! При публікуванні розв’язку обов’язково, окрім самої паскаль-програми писати математичну модель задачі і роз’яснювати ваш розв’язок максимально зрозуміло. Бо із самого тексту програм, не завжди все зрозуміло для пересічного інформатика.


[admin]Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!![/admin]
Пилипчук_О_П Дата: Пт, 23.11.2018, 00:09 | Повідомлення № 391
Ветеран спілкування
Повідомлень: 4292
Нагороди: 38
Рейтинг: 401
Цитата mio ()
Друзі, задача зводиться до сумування чисел на парних і непарних місцях?

Це було б непорядно з боку автора задачі і тестів: зробити тести, де слід просто обчислити суми на парних і непарних місцях, але не сказати про це в умові задачі. Фактично це означало б, що учасники розв'язують одну задачу, а автор - іншу, і саме під цю іншу розроблено тести.
Випробуйте на тесті, що додається до задачі. Я один раз спробував переставити місцями вхідні дані - тест пройдено.
Bandalak Дата: Пт, 23.11.2018, 00:41 | Повідомлення № 392
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Цитата mio ()
Друзі, задача зводиться до сумування чисел на парних і непарних місцях? Знаючі, доступ для перервірки на сервері в когось є?

olimp012 ih78waiq http://35.237.131.59/cgi-bin/new-client?contest_id=4

Сказали, що працює до п'ятниці
Bandalak Дата: Пт, 23.11.2018, 00:49 | Повідомлення № 393
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Цитата mio ()
зводиться до сумування чисел на парних і непарних місцях

Просто так, чи спочатку відсортувати?
Пилипчук_О_П Дата: Пт, 23.11.2018, 00:54 | Повідомлення № 394
Ветеран спілкування
Повідомлень: 4292
Нагороди: 38
Рейтинг: 401
Цитата Bandalak ()

Просто так, чи спочатку відсортувати?

"Ця дорога не веде до храму..." (С)
Принаймні, якщо тести коректні.
Bandalak Дата: Пт, 23.11.2018, 00:56 | Повідомлення № 395
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Запустив без сортування - дало 22 бали.

Код
var n,i:byte;
    j,f,s1,s2:int64;
begin
readln(n);s1:=0;s2:=0;
for i:=1 to n do
begin
read(f); if i mod 2 = 1 then s1:=s1+f else s2:=s2+f
end;
if s1>s2 then writeln(s1) else writeln(s2)
end.
Bandalak Дата: Пт, 23.11.2018, 00:57 | Повідомлення № 396
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Цитата Пилипчук_О_П ()
Ця дорога не веде до храму...

Я розумію. Але що тоді написано в авторському розв'язку?
Пан mio стверджує що саме це. Мені розібратися важко, але схоже на правду.
Bandalak Дата: Пт, 23.11.2018, 01:29 | Повідомлення № 397
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Зробив суми парних і не парних після сортування.

Код
var i,j,n,kmax:byte;
    max:longint;
    s1,s2:int64;
    f:array[1..22] of longint;
begin
readln(n);
for i:=1 to n do
read(f[i]);
for i:=1 to n-1 do
    begin
         max:=f;kmax:=i;
         for j:=i+1 to n do
         if f[j]>max then begin max:=f;kmax:=j end;
         f[kmax]:=f;f:=max
    end;
s1:=0;s2:=0;
for i:=1 to n do
if i mod 2 = 0 then s1:=s1+f else s2:=s2+f;
if s1>s2 then writeln(s1) else writeln(s2)
end.

Отримано 28 балів. Це не те.

Мене продовжує мучити питання, який алгоритм описує авторський розв'язок?
Чи тут оптимізований повний перебір?
Не розумію цього: mask >>= 1;
Пилипчук_О_П Дата: Пт, 23.11.2018, 13:56 | Повідомлення № 398
Ветеран спілкування
Повідомлень: 4292
Нагороди: 38
Рейтинг: 401
Цитата Bandalak ()
Пан mio стверджує що саме це.
У пана mio в кінці речення був знак питання :)
Цитата Bandalak ()
Не розумію цього: mask >>= 1;
Двійкове подання числа mask зсувається вправо на 1 біт і записується в mask. Тобто те саме, що ділення націло на 2.
Bandalak Дата: Пт, 23.11.2018, 19:22 | Повідомлення № 399
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Для чого там взагалі полізли у двійкове подання? Щоб мало хто код зрозумів?
fox11 Дата: Сб, 24.11.2018, 05:05 | Повідомлення № 400
Прописаний назавжди
Повідомлень: 319
Нагороди: 3
Рейтинг: 76
Писал уже выше, можно так:
min = (a < b) ? a : b;
и так:
if (a<b)
  min=a
else
  min=b
Результат один, но хочется поумничать. )))
Bandalak Дата: Сб, 24.11.2018, 09:23 | Повідомлення № 401
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
fox11, Ви можете написати увесь цей алгоритм без структур якими "поумничали".
Код
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> k;
long long best = 1LL * 1e18;

long long solve(int mask)
{
    long long sum1 = 0;
    long long sum2 = 0;

    for (int file : k)
    {
        if (mask & 1)
        {
            sum1 += file;
        }
        else
        {
            sum2 += file;
        }

        mask >>= 1;
    }

    return max(sum1, sum2);
}

int main()
{
    cin >> n;
    k.resize(n);

    for (int i = 0; i < n; ++i)
    {
        cin >> k;
    }

    for (int i = 0; i < (1 << n); ++i)
    {
        best = min(best, solve(i));
    }

    cout << best << endl;

    return 0;
}[/i]


Те що там є підпрограма-функція - то зрозуміло, це добре. Але без всяких надрозумних варіантів запису звичних команд та операцій!
Дякую!
Пилипчук_О_П Дата: Сб, 24.11.2018, 10:14 | Повідомлення № 402
Ветеран спілкування
Повідомлень: 4292
Нагороди: 38
Рейтинг: 401
Цитата Bandalak ()
Для чого там взагалі полізли у двійкове подання? Щоб мало хто код зрозумів?

Існує думка, що це додає швидкодії. Хоча:
1) для перевірки треба поекспериментувати;
2) на тлі того, що деяким мовам дають неабиякі преференції (наприклад, значне збільшення часу для Python), виглядало б дивним підбирати такі тести, що розмежовують різні версії компіляторів однієї мови.
Bandalak Дата: Сб, 24.11.2018, 15:52 | Повідомлення № 403
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Так який саме алгоритм реалізований у задачі Е? Той самий перебір, але пришвидчений певними нюансами побітового програмування?
fox11 Дата: Нд, 25.11.2018, 10:56 | Повідомлення № 404
Прописаний назавжди
Повідомлень: 319
Нагороди: 3
Рейтинг: 76
Цитата Bandalak ()
fox11, Ви можете написати увесь цей алгоритм без структур якими "поумничали".
Здесь более менее понятно
#include <fstream>
#include <cmath>
//#include <iostream>
using namespace std;

int ar[20];
bool v[3000000];
int n, mi = 987654321, sum = 0;

int main()
{
ifstream fin("input.txt");
if (!fin) return 22;
ofstream fout("output.txt");
if (!fout) return 23;

fin >> n;
for(int i = 0; i < n; i++)
{
fin >> ar;
sum += ar;
}
v[0] = true;
for(int i = 0; i < n; i++)
for(int j = sum; j >= 0; j--)
if(v
)
v[j+ar] = true;
for(int i = 0; i <= n; i++)
if(v)
mi = min(mi, abs(sum-2*i));
fout << mi;
fin.close();
fout.close();
//return 0;
}

Источник

Правда у него в этом варианте в последнем цикле была ошибка
Да и не тестировал, не понял где ваша система.


Відредаговано: fox11 - Нд, 25.11.2018, 10:59
Bandalak Дата: Нд, 25.11.2018, 11:03 | Повідомлення № 405
Лідер форуму
Повідомлень: 6158
Нагороди: 43
Рейтинг: 285
Тестуюча система була відкрита після олімпіади для роботи над помилками. Вже закрили.
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Всеукраїнська олімпіада з інформатики (програмування) (Висталяємо завдання та розв'язки)
Пошук:


© Форум інформатиків України, 2007-2019.