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


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

Ви не зайшли.

#1 2015-11-12 17:15:54

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

Розбір рішень Задача Sale

Можна записувати дати D M Y (dd mm y) у вигляді цілого п’ятизначного числа: ymmdd
тоді залишиться упорядкувати ці числа і кожне знову представити у вигдяді трьох чисел дати: dd mm y
Для зв’язку дати з кількістю K проданих операційних систем використаємо асоціативний масив map, де в якості ключа будуть неповторювані дати у вигляді п’ятизначних чисел
Оскільки асоціативний масив самоупорядковується за значенням ключа (в нашому випадку - це дати), то необхідність додаткового упорядковування дат відпадає.

Залишиться лише вивести результат в потрібному форматі.

Код:

#include <iostream>
#include <map>
using namespace std;
int main()
{
    int N,K,D,M,Y;
    cin >> N;
    
    map<int,long int> mp;
    for(int i=0; i<N;i++)
        {
            cin >> K >> D >> M >> Y; 
            mp[Y*10000+M*100+D]=K;
        }
    
    map<int,long int>::iterator it;
    for(it=mp.begin(); it!= mp.end(); it++)
    {
        D = (*it).first % 100;
        M = (*it).first / 100 % 100;
        Y =  (*it).first / 10000;
        cout<<(*it).second<<" "<<D<<" "<<M<<" "<<Y<<endl;
    }
    
return 0;
}

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

Поза форумом

 

#2 2015-11-14 01:30:45

illia
Новий користувач
Зареєстрований: 2015-11-14
Повідомлень: 5

Re: Розбір рішень Задача Sale

Хто може пояснити, чому на тестах розв'язок проходить на 20 балів у той час як в таблиці з результатами лише 18 балів? Розв'язок не змінювався абсолютно.

Поза форумом

 

#3 2015-11-14 09:44:46

skmg
Новий користувач
Зареєстрований: 2015-10-17
Повідомлень: 33

Re: Розбір рішень Задача Sale

illia написав:

Хто може пояснити, чому на тестах розв'язок проходить на 20 балів у той час як в таблиці з результатами лише 18 балів? Розв'язок не змінювався абсолютно.

Вам пощастило, бо у мене на тестах теж регулярно 20, а результат лише 6. Причому всі тести в межах 0.01 сек

Ще раз перевірив, тому уточнення - всі тести, крім останніх двох, в межах 0.01 сек. Два останні - в межаж 0,03 сек. Але при любих розкладах це може дати мінус 4 (ну, хай мінус 6) бали до повного результату (20 балів), але ж ніяк не мінус 14, як маємо в офіційному результаті. sad

Відредаговано skmg (2015-11-14 12:36:34)

Поза форумом

 

#4 2015-11-14 14:31:38

illia
Новий користувач
Зареєстрований: 2015-11-14
Повідомлень: 5

Re: Розбір рішень Задача Sale

Дякую за відповідь! Сподіваюся на коментар від журі, хоча б для загального розуміння, як проходить тестування до та після оголошення результатів.

Поза форумом

 

#5 2015-11-14 19:52:39

Gleb Piliets
Новий користувач
Зареєстрований: 2015-11-12
Повідомлень: 2

Re: Розбір рішень Задача Sale

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;

struct k
{
    int64_t a,b,c,d;
};
bool cmp(const k & a,const k & b)
{
    if(a.d == b.d)
    {
        if(a.c == b.c)
        {
            if(a.b == b.b) return a.a < b.a;
            return a.b < b.b;
        }
        return a.c < b.c;
    }
    return a.d < b.d;
}


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

    k a[10000];
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;

    }
    sort(a,a+n,cmp);
    for(int i = 0; i < n; i ++)
    {
        cout << a[i].a << " " << a[i].b << " " << a[i].c << " " << a[i].d << endl;
    }
    return 0;
}

Вот мой код если кому интересно

Поза форумом

 

#6 2015-11-14 22:17:43

skmg
Новий користувач
Зареєстрований: 2015-10-17
Повідомлень: 33

Re: Розбір рішень Задача Sale

Код, який на тестах РЕГУЛЯРНО, без жодного винятку, набирає 20 балів з 20 (з 1 по 6 та 8 - 0.01 сек, 7- 0.02 сек, 9 та 10 - 0.03 сек),
а офіційний результат всього 6 балів (коментарів не маю)

Код:

Program Sale; 
Const   Mx = 2000;
Var  MS: array[1..Mx] of int64;  
Var K:int64;
Var N,D,M,Y:integer;
Var i:integer;


BEGIN 
for i := 1 to Mx do MS[i]:=0;

Read(N); 
for i := 1 to N do 
 BEGIN          
 Read(K,D,M,Y);
 MS[D+32*M+500*Y]:= K;
 END; 

for i :=1 to Mx do 
if MS[i]>0 then
 BEGIN         
 K:=MS[i];
 Y:=i div 500;
 M:=(i-Y*500) div 32;
 D:=i -(Y*500) - (M*32);
 writeln(K,' ' ,D,' ', M,' ', Y);    
 END 
END.

Відредаговано skmg (2015-11-14 23:47:37)

Поза форумом

 

#7 2015-11-16 14:32:28

Жюри_Непомнящий
Журі
Зареєстрований: 2005-11-03
Повідомлень: 151

Re: Розбір рішень Задача Sale

Надішліть свій код на olymp@olymp.vinnica.ua.

skmg написав:

Код, який на тестах РЕГУЛЯРНО, без жодного винятку, набирає 20 балів з 20 (з 1 по 6 та 8 - 0.01 сек, 7- 0.02 сек, 9 та 10 - 0.03 сек),
а офіційний результат всього 6 балів (коментарів не маю)

Код:

Program Sale; 
Const   Mx = 2000;
Var  MS: array[1..Mx] of int64;  
Var K:int64;
Var N,D,M,Y:integer;
Var i:integer;


BEGIN 
for i := 1 to Mx do MS[i]:=0;

Read(N); 
for i := 1 to N do 
 BEGIN          
 Read(K,D,M,Y);
 MS[D+32*M+500*Y]:= K;
 END; 

for i :=1 to Mx do 
if MS[i]>0 then
 BEGIN         
 K:=MS[i];
 Y:=i div 500;
 M:=(i-Y*500) div 32;
 D:=i -(Y*500) - (M*32);
 writeln(K,' ' ,D,' ', M,' ', Y);    
 END 
END.

Поза форумом

 

#8 2015-11-16 15:21:57

skmg
Новий користувач
Зареєстрований: 2015-10-17
Повідомлень: 33

Re: Розбір рішень Задача Sale

Надіслав.

Відредаговано skmg (2015-11-16 20:00:54)

Поза форумом

 

#9 2015-11-16 20:01:09

skmg
Новий користувач
Зареєстрований: 2015-10-17
Повідомлень: 33

Re: Розбір рішень Задача Sale

skmg написав:

Надіслав.

Дякувати журі, результат виправили на 20.  Якщо в когось аналогічні проблеми з цією задачею, звертайтесь в журі, може й вам пощастить  smile

Поза форумом

 

#10 2015-11-17 10:57:48

by_andreyko
Новий користувач
Зареєстрований: 2015-11-14
Повідомлень: 4

Re: Розбір рішень Задача Sale

В мене та ж сама проблема задача проходить повністю в автоматичній перевірці хоча зараховано тільки 6 балів
program Sale;
var

c2:longint;
c:byte;
i,j,n:integer;
a:array[1..1200,2..4] of byte;
k:array[1..1200] of longint;
begin

  readln(n);
  for i:=1 to n do   readln(k[i],a[i,2],a[i,3],a[i,4]);
     

   
   for i:=1 to n-1 do
     begin
       for j:=1 to  n-i do
         begin
           if a[j,4]>a[j+1,4]then
             begin
               c:=a[j,4];
               a[j,4]:=a[j+1,4];
               a[j+1,4]:=c;
               
               c:=a[j,3];
               a[j,3]:=a[j+1,3];
               a[j+1,3]:=c;

               c:=a[j,2];
               a[j,2]:=a[j+1,2];
               a[j+1,2]:=c;
               
               c2:=k[j];
               k[j]:=k[j+1];
               k[j+1]:=c2;


             end else if (a[j,4]=a[j+1,4])and(a[j,3]>a[j+1,3])then
             begin
               c:=a[j,4];
               a[j,4]:=a[j+1,4];
               a[j+1,4]:=c;

               c:=a[j,3];
               a[j,3]:=a[j+1,3];
               a[j+1,3]:=c;

               c:=a[j,2];
               a[j,2]:=a[j+1,2];
               a[j+1,2]:=c;

               c2:=k[j];
               k[j]:=k[j+1];
               k[j+1]:=c2;
             end else if (a[j,4]=a[j+1,4])and(a[j,3]=a[j+1,3]) and(a[j,2]>a[j+1,2])then
             begin
               c:=a[j,4];
               a[j,4]:=a[j+1,4];
               a[j+1,4]:=c;

               c:=a[j,3];
               a[j,3]:=a[j+1,3];
               a[j+1,3]:=c;

               c:=a[j,2];
               a[j,2]:=a[j+1,2];
               a[j+1,2]:=c;

              c2:=k[j];
               k[j]:=k[j+1];
               k[j+1]:=c2;
             end;
         end;
     end;



  for i:=1 to n do
    begin
      write(k[i],' ',a[i,2],' ',a[i,3],' ');writeln(a[i,4]) ;
    end;

end.

Поза форумом

 

#11 2015-11-18 22:27:48

illia
Новий користувач
Зареєстрований: 2015-11-14
Повідомлень: 5

Re: Розбір рішень Задача Sale

Дякую, листував на olymp@olymp.vinnica.ua - результати змінилися.

Поза форумом

 

#12 2015-11-18 23:15:31

skmg
Новий користувач
Зареєстрований: 2015-10-17
Повідомлень: 33

Re: Розбір рішень Задача Sale

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

Все расхождения связаны с таймингами. Они у нас очень жесткие... Время считаем до 0.01 с. ...
При официальной проверке...  (результат защитывастся, если он одинаков при 3-х разовом прохождении теста).

Это цитата с прошлогодней олимпиады. Нужно ли буквально понимать утверждение в скобках?
Т.е., к примеру, при тайминге 0.09 сек, трехразовое прохождение теста дало результаты 0.04 сек, 0.03 сек и еще раз 0.04 сек, будет ли такой результат не засчитан, как утверждается в цитате(в скобках)?

Хочется понять, почему на этой задаче столько СУЩЕСТВЕННО заниженных при проверке результатов, чтобы избежать в дальнейшем.

Тому що, дійсно, на тесті 10 результат в основному 0.03 сек, але приблизно один раз з восьми-десяти спроб буває 0.04 сек.

Відредаговано skmg (2015-11-18 23:40:20)

Поза форумом

 

#13 2015-11-19 08:34:21

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

Re: Розбір рішень Задача Sale

illia написав:

Дякую, листував на olymp@olymp.vinnica.ua - результати змінилися.

Мы провели повторное официальное тестирование ВСЕЙ базы решений задачи  Sale, увеличив на 0.01 с время на тест. Исключительно в интересах участников.

Поза форумом

 

#14 2015-11-19 12:16:34

illia
Новий користувач
Зареєстрований: 2015-11-14
Повідомлень: 5

Re: Розбір рішень Задача Sale

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

illia написав:

Дякую, листував на olymp@olymp.vinnica.ua - результати змінилися.

Мы провели повторное официальное тестирование ВСЕЙ базы решений задачи  Sale, увеличив на 0.01 с время на тест. Исключительно в интересах участников.

Красно дякуємо!

Поза форумом

 

#15 2015-11-23 14:51:39

Belitoron
Новий користувач
Зареєстрований: 2015-11-13
Повідомлень: 5

Re: Розбір рішень Задача Sale

Як на мене, логічним рішенням в цій задачі було б:
1) створити тривимірний масив R[3][12][31] заповнений нулями
2) для кожної введеної стрічки чисел зробити R[Y][M][D]=K
3) пройтись по всьому масиву, і якщо R[i][j][k] > 0 вивести R[i][j][k], k, j, i


Тому мені прикро, що жюрі взяли такі невеликі обмеження на дату, всього 3 роки, тобто ~1000 днів.
На мою думку, в цій задачі потрібно було брати звіт не за 3 роки а за 30. Це дало б ~11000 можливих дат, і можливість більш чітко по таймліміту відрізнити лінійний розв"язок або ефективне сортування N(logN) від зовсім неефективних алгоритмів.

Відредаговано Belitoron (2015-11-23 14:54:44)

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt