1 Тема від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 725
    • Репутація: 717

Тема: Олімпіадні задачі :)

Вітаю!

Сьогодні була районна олімпіада з програмування. Я брав участь. І хоч я більше люблю Python, прийшлось писати на pascal, оскільки, на Python не можна.. :(

Загалом, завдання - http://loippo.lviv.ua/files/2015/olimp2 … matuka.pdf
Або кожна в спойлері:

▼Задача A

Існує дві дороги: Одна пряма, а інша …
Цілий день члени виборчої комісії нудяться, спостерігають за
виборами, а потім ще й підраховують голоси. Зате вже після
підрахунку голосів члени виборчої комісії починають веселитися та
возити протоколи з виборчих дільниць в регіональні представництва.
Звісно, кожна з виборчих дільниць з’єднана дорогою зі своїм
регіональним представництвом. Та все не так просто. Так склалося,
що дороги прямі, а їх довжини є кратними тисячі метрів.
Пан Городний, який є членом виборчої комісії, задумався,
скільки кілометрів цього дня проїдуть автомобілі, що возитимуть
протоколи. Для того, щоб це дізнатися, він знайшов карту з
позначеними на ній виборчими комісіями та відповідними їм
регіональними представництвами.
Пан Городний знайшов карту. Ваше завдання – написати програму,
яка порахує скільки кілометрів проїдуть автомобілі, що возитимуть
протоколи в день виборів.
До кожної виборчої дільниці належить рівно один автомобіль,
який може їхати лише до відповідного регілнального представництва.
Вхідні дані:
Перший рядок містить одне натуральне число: N - кількість
виборчих дільниць.
Наступні N рядків містять по 4 цілі числа: X1, Y1, X2, Y2. Перші
два з них – координати виборчої дільниці. Наступні два –
координати відповідного регіонального представництва.
Вихідні дані:
Одне ціле невід’ємне число — кількість кілометрів, яку проїдуть
автомобілі, що возитимуть протоколи в день виборів.
Обмеження:
1 ≤ N ≤ 100 000
0 ≤ |X1|, |Y1|, |X2|, |Y2| ≤ 1 000
Приклад вводу:
3
-3 2 1 5
0 0 6 8
4 7 6 7
Приклад виводу:
17
Підказка:
Перший автомобіль проїде 5км. (З точки (-3;2) до точки (1;5))
Другий автомобіль проїде 10км. (З точки (0;0) до точки (6;8))
Третій автомобіль проїде 2км. (З точки (4;7) до точки (6;7))
Сумарно – 17км.


▼Задача B

Підрахунок голосів
О восьмій годині вечора всі виборчі дільниці зачиняються, і
виборчі комісії починають підрахунок голосів. Розглянемо процес
підрахунку голосів деякою виборчою комісією. Нехай в ній присутній
Голова комісії та N членів комісії (без голови). Також нехай на
виборчій дільниці всього є M урн для голосування. Кожна урна має
свій унікальний номер (ціле число від 1 до M). Відомо, що урна з
номером i містить ai бюлетенів.
Отож, члени комісії сідають за великий стіл, а Голова комісії
розподіляє їм урни для підрахунку голосів. Кожен член комісії
отримає деяку кількість урн, при чому номери цих урн повинні йти
підряд. Тобто член комісії може отримати урни з номерами (4, 5, 6,
7), або (1, 2, 3), але не може отримати урни з номерами (4, 7,
47).
Після розподілу може статися так, що деяка кількість членів
виборчої комісії залишиться без роботи — їм не дістанеться жодної
урни. Ваше завдання — знаючи максимальну кількість бюлетенів K,
яку може порахувати один член комісії, сказати, яка максимально
можлива кількість членів комісії може залишитися без роботи.
Вхідні дані:
Перший рядок містить три натуральні числа: кількість членів
комісії N, кількість урн для голосування M, та максимальну
кількість бюлетенів, які може порахувати один член комісії K.
Другий рядок містить M натуральних чисел ai — кількості
бюлетенів в урнах.
Вихідні дані:
Одне ціле невід’ємне число — максимально можлива кількість
членів комісії, що залишиться без роботи, або «-1» (без лапок),
якщо членів комісії не вистачить, щоб порахувати всі бюлетні.
Обмеження:
1 ≤ N, M ≤ 100 000
1 ≤ ai ≤ K ≤ 1 000 000 000
Приклад вводу:
7 4 11
7 4 8 5
Приклад виводу:
4
Підказка:
Першому члену комісії дістануться урни з 7 і 4 бюлетенями,
другому дістанеться урна з 8 бюлетенями, третьому дістанеться урна
з 5 бюлетенями. Решта членів комісії залишаться без роботи.


▼Задача C

Спостерігачі
Пан Петро – дуже відповідальний громадянин. На цьогорічних
виборах він був спостерігачем на дільниці №47, і уважно слідкував
за ходом волевиявлення своїх співгромадян. Разом з тим, він уважно
записував час, коли кожен виборець приходив на дільницю і покидав
її, щоб потім, проаналізувавши свої записи, знайти якісь
потенційні порушення.
Пан Петро довго аналізував дані і виявив один цікавий факт. Під
час виборів часто траплялося так, що на дільниці не було жодного
виборця. Петро, як відповідальний громадянин, запідозрив, що в цей
час могли статися жахливі порушення виборчого процесу, і захотів
розібратися, що до чого. Перше, що його зацікавило – сумарний час,
коли на виборчій дільниці не було жодного виборця. З цим пан Петро
звернувся до Вас. Ваше завдання: маючи інформацію пана Петра про
час приходу і виходу виборців, сказати сумарний час, коли на
виборчій дільниці не було жодного виборця.
Вхідні дані:
В першому рядку задано одне натуральне число N, кількість
виборців, що прийшли голосувати.
Наступні N рядків містять інформацію про виборців, по одному на
рядок. Кожен рядок містить 6 цілих чисел: H1, M1, S1, H2, M2, S2 –
година, хвилина і секунда, на початку якої прийшов виборець та,
відповідно, година, хвилина і секунда, на початку якої виборець
пішов. Ці числа будуть задані з ведучими нулями так, щоб довжина
кожного числа була рівною 2, тобто “09 47 04” замість “9 47 4”.
Гарантується, що кожен проміжок перебування виборця на дільниці
задає коректний проміжок часу (виборець покинув дільницю після
того, як прийшов на неї) між восьмою ранку і восьмою вечора.
Вихідні дані:
Одне ціле число – кількість секунд від восьмої ранку до восьмої
вечора, протягом яких на дільниці не було виборців.
Обмеження:
1 ≤ N ≤ 47474
8 ≤ H1 ≤ H2 ≤ 20
0 ≤ M1, S1, M2, S2 ≤ 59
Приклад вводу:
4
08 30 00 09 00 00
10 00 00 18 00 00
08 00 00 08 10 00
08 05 00 08 20 00
Приклад виводу:
11400


▼Задача D

Агітації
Перед виборами завжди є період агітації. Різні партії
влаштовують мітинги на площах міст, де постійно скандують гасла.
Одного передвиборчого дня Зеник вирішив прогулятися містом. Поки
він гуляв центральними вулицями свого рідного міста, то чув, як
звідусіль долинали різні гасла. Але він чув тільки кінцівки фраз,
тобто, якщо скандували “Слава Україні!”, то Зеник міг почути
“...ні”, або “...країні”.
На жаль, агітатори не є дуже креативними людьми, і скандують
постійно одне і те ж гасло. Проте вони є дуже наполегливими, і
скандують це гасло багато разів підряд. Зенику стало цікаво,
скільки ж раз вони скандували це гасло.
Вам відоме гасло P, яке скандували агітатори. Також, Вам
відомий рядок R, який є конкатенацією (з’єднанням) закінчень рядка
P — все те, що почув Зеник. Вам потрібно визначити, яку ж найменшу
кількість разів треба було повторити гасло P, щоб Зеник почув те,
що він почув.
Вхідні дані:
Перший рядок містить гасло P, яке скандували агітатори. Другий
рядок містить рядок R – те, що почув Зеник.
Кожен рядок складається виключно з малих літер латинського
алфавіту.
Вихідні дані:
Одне ціле число – мінімальна кількість закінчень рядка P, щоб
вийшов рядок R.
Гарантується, що результат завжди існує, тобто з закінчень
рядка P завжди можна скласти рядок R.
Обмеження:
1 ≤ |P|, |R| ≤ 100 000
Приклад вводу:
glorytoukraine
ukraineaineaine
Приклад виводу:
3
Підказка:
Гасло було “glorytoukraine”, а Зеник почув “ukraineaineaine”
Почути це він міг наступним чином: glorytoukraine glorytoukraine
glorytoukraine: ukraine + aine + aine = ukraineaineaine

2 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 725
    • Репутація: 717

Re: Олімпіадні задачі :)

Задача A
Тут нічого складного - додати відстані між всіма парама точок - зробив.

Задача Б. Тут трохи складніше. Але щось вийшло:

▼TaskB
program task_b;
var a: array [1..100000] of integer;
n,m,k,i,local:integer;
flag : string;
begin
readln(n,m,k);
for i:=1  to m do
read(a[i]);


local := 0;
flag := 'false';
for i:= 1 to m do
begin

if flag = 'true' then begin flag := 'false'; continue end;

local := local + a[i];
if local = k then begin n:= n-1; local:=0 end;
if (local < k) and ((local+a[i+1])=k) then begin  n:= n -1; flag := 'true'; local:= 0;end;
if (local < k) and ((local+a[i+1])>k) then begin n:= n-1; local :=0 end;
if (local < k) and (a[i+1]=0) then begin n:= n-1 end;
end;

if n<0 then writeln(-1) else writeln(n);
end.

Та цей код пройшов 23 з 25 тестів. В чому може бути проблема - немаю уявлення.

Задача C - Тут я нічого не встиг придумати, а тепер вже погуглив, що треба було використовувати стандартний модуль для обрахунку часу...

3 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 725
    • Репутація: 717

Re: Олімпіадні задачі :)

Ну і Задача C

▼Задача D

Агітації
Перед виборами завжди є період агітації. Різні партії
влаштовують мітинги на площах міст, де постійно скандують гасла.
Одного передвиборчого дня Зеник вирішив прогулятися містом. Поки
він гуляв центральними вулицями свого рідного міста, то чув, як
звідусіль долинали різні гасла. Але він чув тільки кінцівки фраз,
тобто, якщо скандували “Слава Україні!”, то Зеник міг почути
“...ні”, або “...країні”.
На жаль, агітатори не є дуже креативними людьми, і скандують
постійно одне і те ж гасло. Проте вони є дуже наполегливими, і
скандують це гасло багато разів підряд. Зенику стало цікаво,
скільки ж раз вони скандували це гасло.
Вам відоме гасло P, яке скандували агітатори. Також, Вам
відомий рядок R, який є конкатенацією (з’єднанням) закінчень рядка
P — все те, що почув Зеник. Вам потрібно визначити, яку ж найменшу
кількість разів треба було повторити гасло P, щоб Зеник почув те,
що він почув.
Вхідні дані:
Перший рядок містить гасло P, яке скандували агітатори. Другий
рядок містить рядок R – те, що почув Зеник.
Кожен рядок складається виключно з малих літер латинського
алфавіту.
Вихідні дані:
Одне ціле число – мінімальна кількість закінчень рядка P, щоб
вийшов рядок R.
Гарантується, що результат завжди існує, тобто з закінчень
рядка P завжди можна скласти рядок R.
Обмеження:
1 ≤ |P|, |R| ≤ 100 000
Приклад вводу:
glorytoukraine
ukraineaineaine
Приклад виводу:
3
Підказка:
Гасло було “glorytoukraine”, а Зеник почув “ukraineaineaine”
Почути це він міг наступним чином: glorytoukraine glorytoukraine
glorytoukraine: ukraine + aine + aine = ukraineaineaine

Тут найбільша проблема.
Мій код: 

program task_d;
var count_sym, i, counter: integer;
n,n_1, p,r:string;
begin
readln(p);
readln(r);
count_sym := 1;
counter  := 1;
for i:=1 to length(r) do
begin
     n := Copy(r, i, count_sym);
     n_1 :=  Copy(r, i, count_sym+1);
     if (Pos(n, p)<>0 ) and (Pos(n_1, p)=0) then
        begin
        count_sym := 1;
        counter:=counter+1;
        end
     else count_sym := count_sym+1;

end;

writeln(counter);
end.

І пройшов цей код лише 3 з 25 тестів... :( Що я тут не врахував?

4 Відповідь від Joker Востаннє редагувалося Joker (21.11.2015 21:44:18)

  • Joker
  • Користувач
  • Поза форумом
  • Дата реєстрації: 27.04.2014
  • Повідомлень: 953
    • Репутація: 121

Re: Олімпіадні задачі :)

▼a
#include <iostream>
#include <iomanip>
#include <vector>
#include <time.h>
#include <cstdlib>
#include <conio.h>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main ()
{
    int n;
    cin >> n;

    int arr[100001][4];

    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<4; ++j)
            cin >> arr[i][j];
    }

    int sum = 0;

    for (int i=0; i<n; ++i)
        sum+= sqrt((arr[i][2]-arr[i][0])*(arr[i][2]-arr[i][0]) + (arr[i][3]-arr[i][1])*(arr[i][3]-arr[i][1]));

cout << sum << endl;


    _getch();
    return 0;
}
▼b
  #include <iostream>
#include <iomanip>
#include <vector>
#include <time.h>
#include <cstdlib>
#include <conio.h>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> urna(m + 1);

    for (int i = 0; i<m; ++i)
        cin >> urna[i];

    int res = n;
    int key = k;


    int err_sum = 0;
    for (int i=0; i<m; ++i)
        err_sum+=urna[i];
    if (err_sum > n*k)
    {
        cout << -1 << endl;
        _getch();
        return 0;
    }


    for (int i = 0; i<m;)
    {
        key = k;
        while (key >= urna[i] && i<m)
        {
            key = key - urna[i];
            i++;
        }
        res--;
    }

    cout << res << endl;

    _getch();
    return 0;
}
▼C
#include <iostream>
#include <iomanip>
#include <vector>
#include <time.h>
#include <cstdlib>
#include <conio.h>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a[47474][6];

    for (int i = 0; i<n; ++i)
    {
        for (int j = 0; j<6; ++j)
            cin >> a[i][j];
    }

    int sum = 0;    // у sec

    // 8 рану - 28800
    const int start = 28800;
    const int end = 72000;

    int in[47475];
    int out[47475];

    for (int i = 0; i<n; ++i)
    {
        in[i] = a[i][0] * 3600 + a[i][1] * 60 + a[i][2];
        out[i] = a[i][3] * 3600 + a[i][4] * 60 + a[i][5];
    }

    // Start day
    int Min = in[0], ix = 0;
    for (int i = 1; i<n; ++i)
    {
        // Min = min(Min, in[i]);
        // ix=i;

        if (Min>in[i])
        {
            Min = in[i];
            ix = i;
        }
    }

    sum += Min - start;
    int pause = out[ix];

    while (ix != -1)
    {
        int drako = ix;    //
        Min = end, ix = -1;
        
        for (int i = 0; i<n; ++i)
        {
            if (in[i]>pause)
            {
                if (Min>in[i])
                {
                    Min = in[i];
                    ix = i;
                }
            }
        }
        ///////////////
        
        for (int z = 0; z < n; ++z)
        {
            if (in[z]>in[drako] && in[z] < pause)
            {
                if (out[z] > pause)
                {
                    pause = out[z];
                }
            }
        }
        ////////////////
        sum += Min - pause;
        pause = out[ix];
    }

//    sum += end - pause;

    cout << sum << endl;

    _getch();
    return 0;
}
▼D

робив рандомом. :)

5 Відповідь від Torbins

  • Torbins
  • Torbins
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 07.05.2012
  • Повідомлень: 3 079
    • Репутація: 2276

Re: Олімпіадні задачі :)

Q-bart
Припустимо агітатори були ельфами, а тому кричали "aineaine". А Зеник почув "aineaineainene".

Подякували: Q-bart1

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 594
    • Репутація: 13305

Re: Олімпіадні задачі :)

Torbins написав:

Q-bart
Припустимо агітатори були ельфами, а тому кричали "aineaine". А Зеник почув "aineaineainene".

Айнене-нене - це не ельфи, я вам скажу :)

Подякували: 0xDADA11C71

koala вебсайт

7 Відповідь від VTrim

  • VTrim
  • VTrim
  • =)
  • Поза форумом
  • Дата реєстрації: 07.09.2014
  • Повідомлень: 3 319
    • Репутація: 2297

Re: Олімпіадні задачі :)

Задача Б на php..

$n=7;
$m=4;
$k=11;
$u='7 4 8 5';
$u=explode(' ',$u);
$o=0;
$c=0;
for($i=0; $i<$m; $i++){
$o+=$u[$i];
if($o>$k){
$o=$u[$i];
$c++;
if($i==$m-1) $c++;
}
}
echo array_sum($u) < ($n*$k) ? $n-$c : -1;

8 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 594
    • Репутація: 13305

Re: Олімпіадні задачі :)

Q-bart написав:

І пройшов цей код лише 3 з 25 тестів... :( Що я тут не врахував?

Десь на одиничку розійшлися: http://ideone.com/oLgVma - має бути 3, знаходить 5

Подякували: Q-bart1

koala вебсайт

9 Відповідь від КиївОболонь

  • Звідки: Десь в Дніпрі (в межах Києва)
  • Дата реєстрації: 27.07.2015
  • Повідомлень: 233
    • Репутація: 11

Re: Олімпіадні задачі :)

VTrim написав:

Задача Б на php..

але Php не схожий на Pascal *PARDON*

10 Відповідь від VTrim

  • VTrim
  • VTrim
  • =)
  • Поза форумом
  • Дата реєстрації: 07.09.2014
  • Повідомлень: 3 319
    • Репутація: 2297

Re: Олімпіадні задачі :)

КиївОболонь написав:
VTrim написав:

Задача Б на php..

але Php не схожий на Pascal *PARDON*

Так, але алгоритм буде зрозумілий.

11 Відповідь від Torbins

  • Torbins
  • Torbins
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 07.05.2012
  • Повідомлень: 3 079
    • Репутація: 2276

Re: Олімпіадні задачі :)

VTrim
Ті m, n, k, u, o, c не мають нічого спільного зі словом "зрозумілий".

12 Відповідь від VTrim

  • VTrim
  • VTrim
  • =)
  • Поза форумом
  • Дата реєстрації: 07.09.2014
  • Повідомлень: 3 319
    • Репутація: 2297

Re: Олімпіадні задачі :)

Torbins написав:

VTrim
Ті m, n, k, u, o, c не мають нічого спільного зі словом "зрозумілий".

Воно писалося з телефону і виконувалося в онлайн-інтерпретаторі PHP, тому для зручності позначав змінні коротко :)

13 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 594
    • Репутація: 13305

Re: Олімпіадні задачі :)

КиївОболонь написав:
VTrim написав:

Задача Б на php..

але Php не схожий на Pascal *PARDON*

▼та ну...

http://www.lisperati.com/casting-spels-emacs/images/lisp-is-different.jpg

koala вебсайт

14 Відповідь від КиївОболонь

  • Звідки: Десь в Дніпрі (в межах Києва)
  • Дата реєстрації: 27.07.2015
  • Повідомлень: 233
    • Репутація: 11

Re: Олімпіадні задачі :)

koala написав:
КиївОболонь написав:
VTrim написав:

Задача Б на php..

але Php не схожий на Pascal *PARDON*

▼та ну...

http://www.lisperati.com/casting-spels-emacs/images/lisp-is-different.jpg

мені, наприклад, мало що зрозуміло (якщо зрозуміло) з закинутого коду

15 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 725
    • Репутація: 717

Re: Олімпіадні задачі :)

Torbins написав:

Q-bart
Припустимо агітатори були ельфами, а тому кричали "aineaine". А Зеник почув "aineaineainene".

І яка тут буде правильна відповідь?

aine, aine, aine (3 рази) чи

aineaine aine(2 рази)?

16 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 725
    • Репутація: 717

Re: Олімпіадні задачі :)

Трохи переробив:
http://ideone.com/hCMpXj

Тепер виводить добре, але далі проходить лише 3 тести, далі 5 - неправильно і решта - TimeLimitExceeded

17 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 594
    • Репутація: 13305

Re: Олімпіадні задачі :)

Операції довгі. Ви кожного разу копіюєте великі масиви і шукаєте в них з нуля. Ось нашвидкоруч: http://ideone.com/nbqs7t

koala вебсайт