Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2012-11-17 11:56:15

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Разбор задач

Соревнование завершено, результаты есть, так что, наверное, уже можно. Предоставленные ниже решения проходят все тесты.

1. Rectangle. Как один из вариантов решения - считать количество клеток, слева и сверху от которых находятся либо пустые клетки, либо конец таблицы.

2. Parket1. Задача, по видимому, на ветвления. В моём решении просто в определённом порядке просчитываются все возможные варианты распределения.

Код:

    int N[5];
    for(int i=0;i<5;i++)
    cin>>N[i];
    
    int ans=N[4]; // добавляем количество дощечек размера 1х5
    N[4]=0;
    int tmp;
    
    tmp=min(N[3],N[0]); // добавляем пары дощечек разме 1х1 и 1х4
    ans+=tmp;
    N[3]-=tmp;
    N[0]-=tmp;
    
    tmp=min(N[2],N[1]); // добавляем пары дощечек размера 1х2 и 1х3
    ans+=tmp;
    N[2]-=tmp;
    N[1]-=tmp;
    
    tmp=min(N[0],N[1]/2); // добавляем тройки дощечек размера 1х1, 1х2 и 1х2
    ans+=tmp;
    N[0]-=tmp;
    N[1]-=tmp*2;
    
    tmp=min(N[1],N[0]/3); // Добавляем четвёрки дощечек размера 1х2, 1х1, 1х1 и 1х1
    ans+=tmp;
    N[0]-=tmp*3;
    N[1]-=tmp;
    
    tmp=min(N[2],N[0]/2); // добавляем тройки дощечек размера 1х3, 1х1 и 1х1
    ans+=tmp;
    N[0]-=tmp*2;
    N[2]-=tmp;
    
    tmp=min(N[2],N[0]); // добавляем пары дощечек размера 1х3 и 1х1
    ans+=tmp;
    N[2]-=tmp;
    N[0]-=tmp;
    
    tmp=min(N[1],N[0]); // добавляем пары дощечек размера 1х2 и 1х1
    ans+=tmp;
    N[1]-=tmp;
    N[0]-=tmp;
    
    ans+=N[2]+N[3]; // добавляем оставшиеся единичные дощечки размера 1х3 и 1х4
    
    if(N[0]%5) // добавляем оставшиеся единичные дощечки
    ans+=N[0]/5+1;
    else
    ans+=N[0]/5;
    
    if(N[1]%2) // добавляем оставшиеся дощечки разме 1х2
    ans+=N[1]/2+1;
    else
    ans+=N[1]/2;
    
    cout<<ans<<endl;

UPD: проставил комментарии.

3. Birthday. Посчитаем количество различных квадратов со стороной от 1 до min(m,n). Для этого можно, например, вновь считать сумму клеток, образующих левые нижние углы таких квадратов.

Пример реализации:

Код:

    cin>>m>>n;
    
    int ans=m*n;
    
    for(int i=2;i<=min(m,n);i++)
    {
            ans+=(m-i+1)*(n-i+1);
    }
    cout<<ans<<endl;

4. Fazenda. Задача вида решить на листочке и вывести формулу. При этом следует использовать две формулы площади - формулу Герона
http://upload.wikimedia.org/math/7/a/5/7a5cb40e00e7e72368b2a6f4635fa31f.png
и полупроизведения высоты на сторону, к которой она проведена
http://upload.wikimedia.org/math/4/b/3/4b3344137a490405130a87d73608b604.png
и учитывать, что
http://upload.wikimedia.org/math/c/6/0/c60ccd4593b0ee22e919957970815cd2.png

Также следует помнить, что в условии задана точность вывода данных, поэтому стоит не забыть прописать её.
Если быть кратким, вот реализация программы на С++:

Код:

    cout.setf(ios::scientific);
    cout.precision(11);
    long double a,b,c;
    cin>>a>>b>>c;

    long double k1=a*b+b*c+a*c;
    
    long double k2=a*b+a*c-b*c;
    
    long double k3=b*a+b*c-a*c;
    
    long double k4=c*a+c*b-b*a;
    
    long double k=4*(a*a*c*c);
    
    if(k1*k2*k3*k4<=0)
    cout<<0.0<<' '<<0.0<<endl;
    else
    {
    long double S1=(sqrt(k1*k2*k3*k4))/k;
    
    long double bi=b/(2*S1);
    
    long double S2=0.5*bi*b;
    
    long double ai=(bi*b)/a,ci=(bi*b)/c;
    
    long double P=ai+bi+ci;
    
    cout<<S2<<' '<<P<<endl;
    }

(В качестве предмета для обдумывания для решивших задачу: возможно ли проделать такое не только с треугольником, но и с n-симплексом?)

5. Second. Как уже было сказано ранее, название задачи символическое smile. Задача на знание принципов динамического программирования, комбинаторики и длинной арифметики. Самая первая задача - увидеть, что:
1) Все числа, которые могут быть получены методами, указанными в условии будут рациональными.
2) Так как все числа простые, при любой расстановке скобок НЕ будет происходить сокращения итоговой дроби.
2) Начиная с N=2 количество ответов будет 2^(N-2), так как фактически все ответы, которые можно получить при N можно получить, "сдвинув" на одно число ответы, получаемые для N-1, то есть, их будет в два раза больше (что напоминает основные принципы динамического программирования). Приведу пример:
Для N=2 существует только один способ получить ответ:
(2/3)
Для N=3 будет два варианта:
(2/3)/5 и 2/(3/5)
И так далее. Сложность состоит в том, что 2^98 - это число, большее, чем максимальная вместительность какого-либо типа данных по умолчанию. Поэтому создаём массив цифр и реализуем для него умножение в столбик. Конечно, существуют более быстрые способы возведения в степень (бинарное возведение) и умножения (алгоритм Фюрера), но в данном тестовом наборе максимальное значение N достаточно невелико, так что можно обойтись более "медленными", но простыми с точки зрения написания алгоритмами.

Відредаговано adamant (2012-11-17 14:28:34)

Поза форумом

 

#2 2012-11-17 12:13:06

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

P.S.: какой-либо разбор чего-либо пишу впервые, так что буду рад критике с:

Поза форумом

 

#3 2012-11-17 12:19:02

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Разбор задач

adamant написав:

P.S.: какой-либо разбор чего-либо пишу впервые, так что буду рад критике с:

Ни в коем разе. Все корректно. Одно замечание (педагогическое :-). Задач простых не бывает, равно как и сложных. Бывают те, которые умеешь решать, и те, которые не умешь. Да и прграммирование - это болше на листочке, чем по кнопкам топтать...

Поза форумом

 

#4 2012-11-17 12:21:58

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Жюри_Пасихов написав:

Ни в коем разе. Все корректно. Одно замечание (педагогическое :-). Задач простых не бывает, равно как и сложных. Бывают те, которые умеешь решать, и те, которые не умешь. Да и прграммирование - это болше на листочке, чем по кнопкам топтать...

Учту на будущее, спасибо smile.

Поза форумом

 

#5 2012-11-17 13:59:24

Alex_Bulany
Новий користувач
Зареєстрований: 2009-01-26
Повідомлень: 17

Re: Разбор задач

Шановний adamant!
Ваш роз'язок задачі Fazenda  з доданими рядками
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  long double a,b,c;
  cin >> a >> b >> c;
...
набирає чомусь всього 2 бали.
З повагою,  Alex_Bulany.

Поза форумом

 

#6 2012-11-17 14:08:05

asdasd
Новий користувач
Зареєстрований: 2012-11-17
Повідомлень: 6

Re: Разбор задач

100 баллов.

Код:

program Birthday;
var m, n, k, score: longint;
begin
    read(m, n); score:=0;
    if m > n then begin
        k:=m; m:=n; n:=k;
    end;
    for k:=1 to m do inc(score, (m - k + 1) * (n - k + 1));
    write(score);
end.

Код:

{$N+}
program Fazenda;
var h1, h2, h3, a, b, c, pp, sp, r, trueA, trueB, trueC: extended;
begin
    read(h1, h2, h3);
    a:=h2 / h1; b:=1; c:=h2 / h3;
    pp:=(a + b + c) / 2;
    sp:=sqrt(abs(pp * (pp - a) * (pp - b) * (pp - c)));
    r:=1 / ((1 / h1) + (1 / h2) + (1 / h3));
    trueB:=r * pp / sp;
    trueA:=trueB * h2 / h1;
    trueC:=trueB * h2 / h3;
    if ((trueA >= trueB + trueC) or
        (trueB >= trueA + trueC) or
        (trueC >= trueA + trueB)) then begin
            pp:=0;
            write(pp, ' ', pp);
            halt;
        end;
    pp:=(trueA + trueB + trueC) / 2;
    sp:=sqrt(abs(pp * (pp - trueA) * (pp - trueB) * (pp - trueC)));
    write(sp, ' ', pp * 2);
end.

Код:

program Parket1;
var N1, N2, N3, N4, N5: longint;
    X1, X2, X3, X4, X5: longint; {!}
begin
    read(N1, N2, N3, N4, N5);
    X1:=N1; X2:=N2; X3:=N3; X4:=N4; X5:=N5; {!}
    inc(N5, N4); inc(N5, N3);
    if N2 > N3 then begin
        inc(N5, ((N2 - N3 + 1) div 2));
        inc(N4, ((N2 - N3 + 1) div 2));
        if (N2 - N3) mod 2 = 1 then inc(N4, 2);
    end;
    if N1 > N4 then begin
        inc(N5, ((N1 - N4) div 5));
        if (N1 - N4) mod 5 <> 0 then inc(N5);
    end;
    {write(N5);}
    {new code further}
    inc(X5, X4); inc(X5, X2);
    if X3 > X2 then begin
        inc(X5, X3 - X2);
        inc(X4, (X3 - X2) * 2);
    end;
    if X1 > X4 then begin
         inc(X5, ((X1 - X4) div 5));
         if (X1 - X4) mod 5 <> 0 then inc(X5);
    end;
    {final comparison}
    if N5 < X5 then write(N5) else write(X5);
end.

Код:

program Rectangle;
const nmax = 100;
var N, score: longint;
    arr, ena: array[1..nmax + 1, 1..nmax + 1] of byte;
    i, j: longint;
procedure AddRectangle(val1, val2: longint);
var xI, xJ, x1, x2: longint;
begin
    inc(score);
    xI:=val1 + 1;
    while arr[xI, val2] = 1 do inc(xI);
    dec(xI);
    xJ:=val2 + 1;
    while arr[val1, xJ] = 1 do inc(xJ);
    dec(xJ);
    for x1:=val1 to xI do
        for x2:=val2 to xJ do
            ena[x1, x2]:=1;
end;
begin
    fillchar(arr, sizeof(arr), 0);
    fillchar(ena, sizeof(ena), 0);
    read(N); score:=0;
    for i:=1 to N do
        for j:=1 to N do
            read(arr[i, j]);
    for i:=1 to N do
        for j:=1 to N do
            if ena[i, j] = 0 then begin
                if arr[i, j] = 1 then AddRectangle(i, j);
            end;
    write(score);
end.

Код:

program SecondGenerator;
var f: text;
    s: string;
    i: longint;
function SumX(val1, val2: string): string;
var funcRes, ts: string;
    x1, x2, xI, ost, xcode: integer;
begin
    while length(val1) < length(val2) do val1:='0' + val1;
    while length(val2) < length(val1) do val2:='0' + val2;
    funcRes:=''; ost:=0;
    for xI:=length(val1) downto 1 do begin
        val(val1[xI], x1, xcode);
        val(val2[xI], x2, xcode);
        x1:=x1 + x2 + ost; ost:=0;
        if x1 >= 10 then begin
            ost:=1;
            dec(x1, 10);
        end;
        str(x1, ts);
        funcRes:=ts[1] + funcRes;
    end;
    if ost = 1 then SumX:='1' + funcRes else SumX:=funcRes;
end;
begin
    assign(f, 'Second.pas');
    rewrite(f);
    writeln(f, 'program Second;');
    writeln(f, 'var N: longint;');
    writeln(f, 'begin');
    writeln(f, '    read(N);');
    writeln(f, '    if N = 2 then writeln(''1'');');
    s:='1';
    for i:=3 to 100 do begin
        s:=SumX(s, s);
        writeln(f, '    if N = ', i, ' then writeln(''', s, ''');');
    end;
    writeln(f, 'end.');
    close(f);
end.

Поза форумом

 

#7 2012-11-17 14:25:28

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Alex_Bulany написав:

Шановний adamant!
Ваш роз'язок задачі Fazenda  з доданими рядками
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  long double a,b,c;
  cin >> a >> b >> c;
...
набирає чомусь всього 2 бали.
З повагою,  Alex_Bulany.

Это связано с тем, что надо также отдельно задавать параметры вывода вот этими двумя строками:

Код:

    cout.setf(ios::scientific);
    cout.precision(11);

Как я уже писал в соседней теме.

Сейчас обновлю верхнее сообщение.

Поза форумом

 

#8 2012-11-17 14:49:16

Lorderot
Новий користувач
Звідки: Чернівці
Зареєстрований: 2012-11-15
Повідомлень: 22
Вебсайт

Re: Разбор задач

Програма Birthday:

var n,m,i,c,max,a: longint;

begin
read(n,m);
  if n>m then begin c:=m; max:=n end else begin c:=n; max:=m; end;
  for i:=1 to c do
   a:=a+(max-i)*(c-i);
  writeln(a+n*m);
end.

Програма Parket1:

Program Parket1;

var a,b,c,n1,n2,n3,a1,a4,a2,a3,n4,n5,sum,k,i: longint;


begin
read(n1,n2,n3,n4,n5);

k:=n5;
k:=k+n4;
a1:=n4;
k:=k+n3;
b:=b+k;
k:=0;
a2:=n3;
  if n2>a2 then begin
  n2:=n2-a2;  a2:=0;
if odd(n2) then begin k:=(n2+1) div 2; a4:=1; a3:=k-1 end else
  begin  k:=n2 div 2; a3:=k; end;
  end else a2:=a2-n2;
b:=b+k;
k:=0;
  if n1>(a1+a2*2+a3+a4*3) then begin n1:=n1-(a1+a2*2+a3+a4*3);
    if (n1 div 5=0) or(n1 mod 5<>0) then k:=((n1 div 5)+1)  else k:=n1 div 5; end
    else n1:=0;
  b:=b+k;
k:=0;
writeln(b);
end.

Програма Second:

Program Second;

var x:array[0..10000] of byte;
     n:integer;


procedure f;
var i:integer;
    c,b:byte;
begin
c:=0;
for i:=1 to n do
  begin
   b:=x[i]*2+c;
   x[i]:=b mod 10;
   c:=b div 10;
  end;
if c>0 then
  begin
   inc(n);
   x[n]:=c;
  end;
end;

var a:integer;
    i:integer;
begin
readln(a);
n:=1;
x[1]:=1;
for i:=1 to a-2 do
  f;
for i:=n downto 1 do
  write(x[i]);
writeln;

end.
ДАні задачі пройшли всі тести!

Відредаговано Lorderot (2012-11-17 14:49:56)

Поза форумом

 

#9 2012-11-17 21:26:07

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Разбор задач

Мне больше всего понравилась задача Parket1. Исчерпывающе четкое и однозначное условие из которого трудно что либо выбросить. Непростое, как мне кажется, решение, требующее умения мыслить логически. Кстати вопросов по этой задаче ни у кого не было, а баллов за решение она отобрала у участников пожалуй больше, чем любая другая задача I тура.

Меньше всего понравилась задача Fazenda. Это чисто математическая задача. Условие носит словоблудный характер с элементами запутывания на ровном месте: "указаны расстояния от каждой вершины до прямой, проходящей через две другие вершины (высоты треугольника)". Вместо сочинения на вольную тему можно было обойтись одной строчкой: "найти периметр и площадь треугольника по заданным высотам". Навыки программирования при решении задачи заключаются лишь в умении записывать арифметические выражения и извлекать квадратный корень. Мнимое достоинство этой задачи в умении представлять число в экспоненциальной форме с определённой степенью точности вызвало много вопросов и недовольств потому что в предварительном онлайн-тестировании выполнение этого условия невозможно было проверить из-за целых результатов. И пробное тестирование успешно проходило при целых 600 и 120 вместо 6.0000000000Е+02    1.2000000000Е+02

В условии задачи Birthday, чтобы избежать лишних вопросов стоит, добавить, что неделимые плитки имеют каждая свой неповторимый вкус, и что выламывать плитки Ваня может с любого места в шоколадке .

Задача Second - неплоха. Немного "путает" требование в условии, чтобы числа были рациональными, в то время как по определению и условию они иррациональными просто не могут быть. Даже без всякого решения бросается в глаза закономерность 1,2,4... 2^(N-2) Тех, кто поверил в лёгкий успех, ожидает "неприятность" работы с длинными числами. Правда небольшой диапазон для n (от 2 до 100) позволяет лентяям эту неприятность обойти с помощью обычного Windows-калькулятора. Я так и сделал, заранее вписав большие числа (больше, чем 2^58) в строковый массив. И получил свои 20 баллов не мудрствуя над длинными чмслами.

К Rectangle - претензий нет. Хорошая задача. Продуманное, лаконичное условие. И алгоритм решения не лежит на поверхности...

P.S. Авторов задач прошу не обижаться на моё чисто субьективное и возможно ошибочное мнение.

Відредаговано LVV (2012-11-18 12:13:12)


Вік живи - вік навчайся.

Поза форумом

 

#10 2012-11-17 21:51:10

IskanderUA
Новий користувач
Зареєстрований: 2012-07-07
Повідомлень: 9

Re: Разбор задач

LVV написав:

Я так и сделал, заранее вписав большие числа (больше, чем 2^58) в строковый массив. И получил свои 20 баллов не мудрствуя над длинными чмслами.

Ну эта олимпиада также носит несколько учебный характер и я бы посоветовал вам все-таки реализовать длинную арифметику для этого случая (чисто для себя), благо пишется она за 5-10 минут smile

Відредаговано IskanderUA (2012-11-17 21:51:26)

Поза форумом

 

#11 2012-11-18 00:00:52

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Разбор задач

Розвязок задачі Birthday динамікою
function min(a,b:longint):longint;
begin
if a<b then min:=a else min:=b;
end;
var
m,n,i,j:longint;
f:array[1..1000,1..1000]of longint;
begin
readln(m,n);
for i:=1 to n do f[1,i]:=i;
for i:=1 to m do f[i,1]:=i;
for i:=2 to n do
  for j:=2 to m do
     f[j,i]:=f[j,i-1]+f[j-1,i]-f[j-1,i-1]+min(i,j);
writeln(f[m,n]);
end.

Поза форумом

 

#12 2012-11-18 00:02:28

Lorderot
Новий користувач
Звідки: Чернівці
Зареєстрований: 2012-11-15
Повідомлень: 22
Вебсайт

Re: Разбор задач

IskanderUA написав:

LVV написав:

Я так и сделал, заранее вписав большие числа (больше, чем 2^58) в строковый массив. И получил свои 20 баллов не мудрствуя над длинными чмслами.

Ну эта олимпиада также носит несколько учебный характер и я бы посоветовал вам все-таки реализовать длинную арифметику для этого случая (чисто для себя), благо пишется она за 5-10 минут smile

Завдяки цій задачі я і навчився реалізовувати множення у стовпчик(раніше не розумів);

Поза форумом

 

#13 2012-11-18 05:55:41

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Разбор задач

IskanderUA написав:

... я бы посоветовал вам все-таки реализовать длинную арифметику для этого случая (чисто для себя), благо пишется она за 5-10 минут smile

Разумеется, IskanderUA, Вы правы.

Код:

//Second
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int M[102]={0};
M[100]=1;
n-=2;
//вычисление 2^n
for(int i = 1; i <=n; i++)
    for (int j=100; j>0; j--){
        M[j]=M[j]*2+bool(M[j+1]/10);
        M[j+1]%=10;
    }
//вывод
for (int j=1; j<101; j++)
    if (M[j]){
        for (int k=j; k<101; k++)
            cout << M[k];
        break;
    }    
return 0;
}

Відредаговано LVV (2012-11-18 06:22:01)


Вік живи - вік навчайся.

Поза форумом

 

#14 2012-11-18 16:38:16

IskanderUA
Новий користувач
Зареєстрований: 2012-07-07
Повідомлень: 9

Re: Разбор задач

Lorderot написав:

IskanderUA написав:

LVV написав:

Я так и сделал, заранее вписав большие числа (больше, чем 2^58) в строковый массив. И получил свои 20 баллов не мудрствуя над длинными чмслами.

Ну эта олимпиада также носит несколько учебный характер и я бы посоветовал вам все-таки реализовать длинную арифметику для этого случая (чисто для себя), благо пишется она за 5-10 минут smile

Завдяки цій задачі я і навчився реалізовувати множення у стовпчик(раніше не розумів);

Я думаю авторам задач буде дуже приємно це почути smile

Поза форумом

 

#15 2012-11-18 18:02:49

PIXEL
Новий користувач
Зареєстрований: 2012-01-11
Повідомлень: 3

Re: Разбор задач

Решение Birthdey без цикла:
-----------------------------------------
program Birthday;
  var min,n,m:longint;
begin
  read(n,m);
  min:=n;
  if m<min then min:=m;
  writeln((min+1)*n*m-(n+m)*((min*(min+1)) div 2)+(min*(min+1)*(2*min+1)) div 6);
  end.
-----------------------------------------

Поза форумом

 

#16 2012-11-18 18:17:02

asdasd
Новий користувач
Зареєстрований: 2012-11-17
Повідомлень: 6

Re: Разбор задач

PIXEL написав:

Решение Birthdey без цикла

Круто.

Поза форумом

 

#17 2012-11-18 18:31:33

Andrey1998
Новий користувач
Зареєстрований: 2011-11-17
Повідомлень: 17

Re: Разбор задач

PIXEL написав:

Решение Birthdey без цикла:

Оригинально, а как вывели такое?

Відредаговано Andrey1998 (2012-11-18 18:31:48)

Поза форумом

 

#18 2012-11-18 19:21:33

asdasd
Новий користувач
Зареєстрований: 2012-11-17
Повідомлень: 6

Re: Разбор задач

Andrey1998 написав:

PIXEL написав:

Решение Birthdey без цикла:

Оригинально, а как вывели такое?

Насколько я могу судить из своего решения, которое
    for k:=1 to m do inc(score, (m - k + 1) * (n - k + 1));
то там получается что-то типа 1*x + 2*(x+1) + 3*(x+2) и тд, первая часть — 1x, 2x, 3x, ..., вторая — 0*1, 1*2, 2*3... — и отсюда уже выводится закономерность.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt