Результати турніру "Приваблива жадність"

Зведена таблиця результатів

Учасник\Тест
Add
Scouts
Strings
Sum
1351_Андрій Макаревич 2 20 30 52
1467_Іван Здомський 2 20 30 52
0595_Саша Шевчук 2 0 30 32
0528_Dima Soroka 6 18 0 24
0598_Володимир Братащук 2 0 22 24
0667_Назар Старушок 2 0 0 2
1043_Люба Ярушинська 2 0 0 2

 

Результати тестів по задачі "Add"

Учасник\Тест
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
Sum
0528_Dima Soroka + + + - - - - - - - - - - - - 6,0
0595_Саша Шевчук + - - - - - - - - - - - - - - 2,0
0598_Володимир Братащук + - - - - - - - - - - - - - - 2,0
0667_Назар Старушок + - - - - - - - - - - - - - - 2,0
1043_Люба Ярушинська + - - - - - - - - - - - - - - 2,0
1351_Андрій Макаревич + - - - - - - - - - - - - - - 2,0
1467_Іван Здомський + - - - - - - - - - - - - - - 2,0

 

Результати тестів по задачі "Scouts"

Учасник\Тест
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
Sum
0528_Dima Soroka - - - - - - - - - - + + - + + + + + + + 18,0
0595_Саша Шевчук - - - - - - - - - - - - - - - - - - - - 0,0
0598_Володимир Братащук - - - - - - - - - - - - - - - - - - - - 0,0
0667_Назар Старушок - - - - - - - - - - - - - - - - - - - - 0,0
1043_Люба Ярушинська N N N N N N N N N N N N N N N N N N N N 0,0
1351_Андрій Макаревич + - - - - - - - - - + + - + + + + + + + 20,0
1467_Іван Здомський + - - - - - - - - - + + - + + + + + + + 20,0

 

Результати тестів по задачі "Strings"

Учасник\Тест
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
Sum
0528_Dima Soroka N N N N N N N N N N N N N N N 0,0
0595_Саша Шевчук + + + + + + + + + + + + + + + 30,0
0598_Володимир Братащук + + + + + + + + + + + - - - - 22,0
0667_Назар Старушок w w w w w w w w w w w w w w w 0,0
1043_Люба Ярушинська N N N N N N N N N N N N N N N 0,0
1351_Андрій Макаревич + + + + + + + + + + + + + + + 30,0
1467_Іван Здомський + + + + + + + + + + + + + + + 30,0

 

Легенда:
T - перевищений ліміт часу
W - помилка вводу-виводу, використання модуля Crt.
R - помилка виконання
N - відсутній розв'язок
P - штраф

Авторські розв"язки

Add

 
#include "stdafx.h"
#include <fstream>
#include <set>

using namespace std;

int n,num;
int _tmain(int argc, _TCHAR* argv[])
{
multiset< int> s;
ifstream dat("add.in");
ofstream sol("add.out");
dat >> n;
while(n)
{
   s.clear();
   for(int i=0;i< n;i++)
        dat >> num,s.insert(num);
  int res,a,b; 
  res = 0;
  while(s.size() > 1)
  {
    a = *s.begin(); s.erase(s.begin());
    b = *s.begin(); s.erase(s.begin());
    s.insert(a+b);
    res += a + b;
  }
  sol < <  res < <  endl;
  dat >> n;
}
return 0;
}


	  
	  

 

Scouts

 

		type  vector    = array[0..1001] of longint;

var m           : vector;
    fi,fo       : text;
    n,tests,i   : longint;
    res         : longint;

procedure qsort(var a : vector);

    procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
begin
    sort(0,n-1);
end;

function go(n,visible:longint):longint;
var first,second,best : longint;
begin
        if n=1 then
             begin
		if visible=1 then writeln(fo,m[0]);
                go:=m[0];exit;
             end else
             if n=2 then
	            begin
			if visible=1 then writeln(fo,m[0],' ',m[1]);
			go:=m[1];exit;
                    end else
		    if n=3 then
                        begin
	                  if visible=1 then
                            begin
			        writeln(fo,m[0],' ',m[1]);
			        writeln(fo,m[0]);
			        writeln(fo,m[0],' ',m[2]);
		            end;
		            go:=m[0]+m[1]+m[2];exit;
	                end;
        first:=m[0] + 2*m[1] + m[n-1];
	second:=2*m[0] + m[n-2] + m[n-1];
	if first<second then best:=first else best := second;
	if visible=1 then
	begin
		if best=first then
		begin
			writeln(fo,m[0],' ',m[1]);
			writeln(fo,m[0]);
			writeln(fo,m[n-2],' ',m[n-1]);
			writeln(fo,m[1]);
		end else
		begin
			writeln(fo,m[0],' ',m[n-2]);
			writeln(fo,m[0]);
			writeln(fo,m[0],' ',m[n-1]);
			writeln(fo,m[0]);
		end
	end;
        go:=best+go(n-2,visible);
end;

begin
   assign(fi,'scouts.in');reset(fi);
   assign(fo,'scouts.out');rewrite(fo);
   readln(fi,tests);
   while tests>0 do begin
      readln(fi);
      readln(fi,n);
      for i:=0 to n-1 do readln(fi,m[i]);
      qsort(m);
      res:=go(n,0);
      writeln(fo,res);
      res:=go(n,1);
      if tests>1 then writeln(fo);
      tests:=tests-1;
   end;
   close(fi);close(fo);
end.

		
		 

 

Strings

	var a,b         : array[1..1000000] of char;
    fi,fo       : text;
    n,i         : longint;
    res         : longint;
    ch          : char;


begin
   assign(fi,'strings.in');reset(fi);
   assign(fo,'strings.out');rewrite(fo);
   While not Eof(fi) do begin
        i:=1;
        repeat
                read(fi,a[i]);
                inc(i);
        until a[i-1]=#32;
        n:=i-2;
        i:=1;
        while not Eoln(fi) do begin
                read(fi,ch);
                if (a[i]=ch) and (i<=n) then inc(i);
        end;
        if i-1=n then writeln(fo,'Yes') else writeln(fo,'No');
        readln(fi);
   end;

   close(fi);close(fo);
end.

	
	
	 

Ідеї розв"язків задач

 

Add

Кожен раз треба додавати два найменші числа. Тоді сумарна вартість додавання чисел буде найменшою. Зрозуміло, що результат додавання чергових двох чисел треба ставити на своє місце у відсортований масив. Треба ще правильно вибрати типи змінних. Це все.


Scouts

Відсортуємо час, за який плазуни перетнуть річку за зростанням. Позначимо через mi час переходу річки i – им плазуном (m1 <= m2 <= … <= mn).  Розглянемо як треба проходити через міст одному, двом і трьом плазунам. При n = 1 и n = 2 оптимальна швидкість переходу моста відповідно рівна  m1 і m2 = max(m1, m2). При наявності трьох (n = 3) перший і другий переходять на іншу сторону, самий швидкий (перший) повертається з ліхтарем назад і переводить третього. Таким чином, оптимальний час переходу дорівнює  m1 + m2 + m3.
Розглянемо випадок, коли n > 3. Нехай A, B, …, Y, Z – пластуни, відсортовані за зростанням часу перетину моста (A – самий швидкий, Z – самий повільний). Нехай J – пластун, з яким переходить Z. Якщо J залишиться на другому березі і ніколи більше не піде по мості, то оптимально вибрати його рівним Y.  Якщо J буде повертатися, то його  оптимально вибрати самим швидким, тобто   А. Таким чином  Z може переходити міст або із Y, або з А. Обчислимо час переходу двох самих повільних плазунів (Y і Z) відповідно до цих стратегій.
1. Z іде з Y. Але тоді до цього там повинен бути хтось, що поверне ліхтар, наприклад K. Але цього K також на інший берег повинен провести хтось, щоб повернути ліхтар, віддати його Y і Z. Нехай ним буде L. Таким чином, K і L повинні повертатися. Для мінімізації часу в якості K і L слід вибрати самих швидких, тобто A і B. Час переходу Y і Z рівний mA + 2mB + mZ.
2. Z йде з  A, A повертається. Аналогічно A переводить Y і також повертається. Час переведення Y і Z рівний 2mA + mY + mZ.
В обох випадках через міст переводяться тільки двоє самих повільних плазунів. Стратегія (перша чи друга) вибирається в залежності від того, яке із значень (mA + 2mB + mZ чи  2mA + mY + mZ) менше. Якщо спочатку треба було перевести n плазунів, то дальше рекурсивно слід перевести n – 2 плазунів.

Приклад

Відсортуємо час переходу моста плазунами: 1, 2, 5, 10. Тут mA = 1, mB = 2, mY = 5, mZ = 10. Час переходу двох самих повільних плазунів відповідно першій і другій стратегіям рівні mA + 2mB + mZ = 1 + 2 * 2 + 10 = 15, 2mA + mY + mZ = 2 * 1 + 5 + 10 = 17. Оскільки перше значення менше, то треба Z вести з Y. Z з Y переводяться за час 15, після чого залишається перевести на інший берег A і B. Це робиться за час max{mA, mB} = 2.

Strings

Задача розв’язується жадним алгоритмом. Читаємо перше слово a0a1…an-1 в символьний масив. Друге слово читаємо посимвольно. Присвоємо i = 0. Якщо прочитаний символ другого слова рівний ai, то значення i збільшуємо на 1. Якщо після проходження друго слова i = n, то перше слово є підпослідовністю другого.