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

traveller6 · 2012-01-03 10:26:09

Вот моё решение Sorting на все 40 баллов. При отправке у меня прошел только 1 балл, а сейчас я немножко подправил.
Я просто меняю место елемента, который не равен индексу, и ставлю его на своё место. Так прохожусь по всему массиву trunc(sqrt(n)) раз, чтобы отсортировать все елементы (хотя место trunc(sqrt(n)) можно поставить 13 (считал по самому большому тесту), и все тесты тоже проходят (самый последний за 0,09 сек)). Если оставить trunc(sqrt(n)), то самый последний проходит за 0.10 сек.

program Sorting;
var
n, i, j, c, kol: longint;
a: array [1..32767] of int64;
begin
read(n);
for i := 1 to n do
read(a[i]);
kol := 0;
for j := 1 to trunc(sqrt(n)) do
for i := 1 to n do
if a[i] <> i then
begin
kol := kol + 1;
c := a[a[i]];
a[a[i]] := a[i];
a[i] := c;
end;
writeln(kol);
end.

Відредаговано traveller6 (2012-01-03 10:33:46)

Зевс · 2012-01-03 13:29:35

Уважаемое Жюри, мне все-таки хотелось бы узнать, как устроена проверка тестов в задаче SumOfPowers и почему программа:

#include <iostream>
using namespace std;

int main()
{
int k, m, n;
scanf("%d%d", &k, &m);
for (int i=0; i<m; printf(" "), ++i) {
scanf("%d", &n);
if (k >= 20) printf("0"); else
if (k >= 13) printf("0"); else
if (k == 1) printf("0"); else
printf("0");
}
}

на некоторых тестах на онлайн проверке получает ТЛ?
Мне хотелось бы выяснить это, чтобы в будущем не делать таких же ошибок.
Заранее спасибо!

yaa · 2012-01-03 17:47:27

LVV написав:
А взагалі, я хочу подякувати авторам, що умови задач перших двох турів були продуманими, вичерпними і чіткими. Завдяки цому на форумі майже не "ломали списів" стосовно умов завдань, чи результатів туру.
Усіх з Новим роком.

На мою думку, тут умови доже не чіткі, трактувати можна по-різному.
Наприклад, в задачі ТС100 ні де не сказано, що танкі рушають тільки 1 раз...весь час треба щось додумувати...

Жюри_Пасихов · 2012-01-04 11:36:38

Зевс написав:
Еще ни на одной олимпиаде, ни на одной проверяющей системе такой проблемы я не встречал. Хотя все-равно довольно странным остается то, что большинство тестов проходят.

Уважаемое Жюри, если проблема действительно в поочередном вводе/выводе, можете написать, пожалуйста, об этом. Мне хотелось бы разобраться с образовавшейся ситуации, чтобы в следующий раз не делать подобных ошибок. Заранее спасибо.

Как вы сами заметили, большинство тестов проходит в режиме поочередного ввода/вывода, так что проблема, очевидно, не в этом. И не в проверяющей системе вообще. Тут много писалось (точнее - спрашивалось, отвечалось меньше) о режимах компиляции. Я всех адресовал к правилам, где ЧЕТКО сказано о АNSI - совместимости исходного кода.

Жюри_Пасихов · 2012-01-04 11:42:25

yaa написав:
LVV написав:
А взагалі, я хочу подякувати авторам, що умови задач перших двох турів були продуманими, вичерпними і чіткими. Завдяки цому на форумі майже не "ломали списів" стосовно умов завдань, чи результатів туру.
Усіх з Новим роком.
На мою думку, тут умови доже не чіткі, трактувати можна по-різному.
Наприклад, в задачі ТС100 ні де не сказано, що танкі рушають тільки 1 раз...весь час треба щось додумувати...

Притча. Очередь у газетного киоска. Комментарий опозиционного политика: "Вот до чего доруководились! Газеты - и тех не хватает! Люди в очереди стоят!". Комментарий власть имущего: "Вот как здорово! Мировой экономический кризис! Всем трудно! А у нас на все у людей хватает, даже на газеты! В очереди стоят!"

Dim_ov · 2012-01-04 16:35:23

yaa написав:
На мою думку, тут умови доже не чіткі, трактувати можна по-різному.
Наприклад, в задачі ТС100 ні де не сказано, що танкі рушають тільки 1 раз...весь час треба щось додумувати...

Але про ТС100 дуже швидко з'явилася відповідь автора на форумі. В усих же інших задачах я щось не помітив якихось значних неточностей. Умови були досить чіткі.

Те, що більшість з нас у п'ятій задачі не здогадалися, що для квадратів може бути вигідно стрибати назад - це проблема виключно наша, аж ніяк не автора, чи умови задачі.

Програмування - це взагалі така штука, що "весь час треба щось додумувати".

LVV · 2012-01-04 17:23:34

Жюри_Пасихов написав:
.... А у нас на все у людей хватает, даже на газеты! В очереди стоят!"

Мабуть сприйняття умов задач - процес дуже суб'єктивний. Комусь одні задачі здаються не дуже зрозумілими, а комусь інші... Все залежить багато від чого... від досвіду... і навіть від настрою.
У мене теж багато зауважень до умов задач (то "надлишковість", то "недосказанність", то перебір з "художнім оформленням"...)
Авторам задач можна тішитись тим, що "всім не догодиш", і завжди знайдуться чимось невдоволені.

Але, шановний yaa, на відміну від NetOI-2010
(згадати хоча б обговорення умови задачі GearSet (І тур), або помилкові обмеження на розмір вхідних даних задачі Division (ІІІ тур))
цього року поки що не було "проколів" в умовах, які б унеможливлювали рішення задачі. А тому, все ж таки, мабуть можна вважати умови цьогорічних задач чіткими і вичерпними, незважаючи на всі зауваження (в тому числі і мої

Відредаговано LVV (2012-01-04 17:26:39)

Зевс · 2012-01-04 20:12:05

Все-таки хотелось бы вернуться к вопросу о поочередном вводе/выводе, и вообще проблеме с ТЛ в задаче SumOfPowers.

Я отправил две простенькие программки на онлайн проверку (и вроде бы никаких проблем с АNSI - совместимостью в них нет):

Код:

#include <iostream>
using namespace std;

int main()
{
  int m, n;
  cin>>m>>m;
  for (int i=0; i<m; ++i) cin>>n;
  for (int i=0; i<m; ++i) cout<<"0 ";
}

Код:

#include <iostream>
using namespace std;

int main()
{
  int m, n;
  cin>>m>>m;
  for (int i=0; i<m; ++i) {
    cin>>n;
    cout<<"0 ";
  }
}

Так вот первая программа на всех тестах работает быстро (без ТЛ), а вторая на некоторых (в общем-то на тех же, что и раньше) выдает ТЛ.
Может ли Жюри подробнее объяснить, в чем проблема?

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

#26 2012-01-03 10:26:09

Re: Розв’язки задач 2 туру

#27 2012-01-03 13:29:35

Re: Розв’язки задач 2 туру

#28 2012-01-03 17:47:27

Re: Розв’язки задач 2 туру

LVV написав:

#29 2012-01-04 11:36:38

Re: Розв’язки задач 2 туру

Зевс написав:

#30 2012-01-04 11:42:25

Re: Розв’язки задач 2 туру

yaa написав:

LVV написав:

#31 2012-01-04 16:35:23

Re: Розв’язки задач 2 туру

yaa написав:

#32 2012-01-04 17:23:34

Re: Розв’язки задач 2 туру

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

#33 2012-01-04 20:12:05

Re: Розв’язки задач 2 туру

Код:

Код:

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