Розв'язки та коментарі до нульового туру.

P1T0 (30 балів)

Дано два цілих числа М і N.
Обчисліть суму всіх цілих чисел від меншого до більшого 
з даних чисел (включно).
Вхідні дані: перший рядок - число М 
		(-2000000000 < M < 2000000000);
             другий  рядок - число N 
		(-2000000000 < N < 2000000000).
Вихідні дані: відповідне число.
Приклад вхідних даних:		Приклад вихідних даних:
1				3
2

Розв'язки учасників можна поділити на декілька груп.
Одні просто знаходили суму всіх чисел від М до N.
Такі розв'язки отримували максимум 9 балів.
Якщо додавання проводилось від меншого до більшого:
сума типу лонгінт - 14 балів, 
сума типу екстендед - 17 балів.
Всі інші тести не проходили за часом.

Деякі з учасників здогадалися,  що суму чисел від 
від'ємного до додатного  шукати недоцільно.
Наприклад, від -10 000 000 до 10 000 001. Зрозуміло, 
що сума від -10 000 000 до 10 000 000 дорівнює 0.
Якщо додавання проводилось з урахуванням можливості 
зменшення діапазону, то результати були такі:
сума типу лонгінт - 15 балів, 
сума типу екстендед - 20 балів.
Всі інші тести все одно не проходили за часом.

Ті учасники, які знають, що таке арифметична  прогресія,
або помітили, що послідовність чисел можна поділити 
на пари: перше число + останнє
друге + передостаннє і так далі.
Прислали розв'язок типу:
{$N+}
Var  N,M,t,Sum: Extended;
Begin
     Readln(M);
     Readln(N);
     If M>N Then Begin t:=M; M:=N; N:=t End;
     Sum:=(M+N)/2*(N-M+1);
     Writeln(Sum:0:0);
     Readln;
End.

Такий   розв'язок отримав 23 бали з 30.
Як з'ясувалося тип Extended зберігає 18 знаків цілої 
частини числа, а сума може бути 19-ти значною.
Згідно довідників - мантиса типу Extended рівна 19-20 
знакам, а виявилося тільки - 18.
Автор цю проблему вирішив за рахунок довгої арифметики.
Авторський розв'язок i тести додаються в окремому архіві.

Але виявилася єдина цілком правильна робота одного 
учасника, яка вразила мене своєю простотою:
{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}

var a,b,t:extended;
begin
    Readln (a);
    Readln (b);
    t:=(a+b)/2*(abs(b-a)+1)/10;
    if int(t)<>0 then write(int(t):0:0);
    if abs(t)<1 Then Writeln(round(frac(t)*10))
                Else Writeln(abs(round(frac(t)*10)));
end.

Як виявляється, в змінній типу екстендед можуть 
одночасно зберігатись 18 знаків цілої частини і 2 знаки 
дробової частини. Виходить 19-ти значне число можна 
зберігати, якщо поділити його на 10 
і виводити окремо знаки цілої і дробової частин.


P2T0 (70 балів)

	В місті Безвиграшне раз в тиждень організовують 
таку інтелектуальну лотерею програмістів:
1) протягом тижня програмісти міста телефонують до 
організаторів лотереї;
2) випадковим чином вибираються і запрошуються в студію 
претендентів на головний приз;
3) з кожним претендентом окремо проводять розіграш 
описаний в пунктах 4) та 5) та 6);
4) в лототрон закладають 1000) пронумерованих куль з 
номерами від 1 до 1000;
5) робот GIRL достає 1000 разів випадковім чином кулі 
з барабана, а програма претендента на виграш вгадує 
номер кожної кулі;
6) доки програма претендента не назве правильно номер 
кулі, наступна куля не виймається з лототрона.
7) головний приз дістається тому претенденту, програма 
якого витратить на відгадування всіх номерів  найменшу 
сумарну кількість запитів.

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

Програмістам, що пишуть на мові Pascal буде надано 
модуль GIRL.TPU, в якому буде реалізована така функція: 
FUNCTION Zapyt(Number:Integer):Integer
Програмістам, що пишуть на мові С++ буде надана 
бібліотека GIRL. H, в якій буде реалізована така 
функція: int zapyt( int Number)

Функція повертає   1, якщо число в запиті більше номера 
кулі.
Функція повертає -1, якщо число в запиті менше номера 
кулі.
Функція повертає   0, якщо число в запиті дорівнює 
номеру кулі.

Наведений нижче приклад правильний, але не дає 
виграшного результату:

   USES GIRL; 
   VAR   i,j : Integer;
   BEGIN    
                   For i : = 1 to 1000 do 
                     For j: = 1 to 1000 do 
                      If  Zapyt(j)=0 Then Break;
    END.


Останнім часом на багатьох олімпіадах зустрічаються 
задачі, в яких необхідно використовувати тестуючi 
модулі, текст яких журі приховує від учасників. 
В таких випадках необхідно написати не тільки розв'язок 
задачі, але й модуль для тестування.

В нашому випадку модуль міг бути такий:

Unit Girl;

interface

Function Zapyt(Number: Integer): Integer;

implementation

Function Zapyt(Number: Integer): Integer;
Var Res: integer;
Begin
      Writeln(Number);
      Readln(Res);
      Zapyt:=Res;
End;

Begin
End.
 
Зрозуміло, що журі під час перевірки використовує 
інший "хитрий" модуль.

Розв'язки учасників перевірялися за допомогою двох 
модулів.
Один модуль "піддавався" програмі учасників:
Якщо модуль отримував запит на кульку, яку ще не 
було вгадано, він повертав 0 - "кульку вгадано".
Правильна програма з таким модулем повинна вгадати 
1000 кульок за 1000 запитів.
Як виявилося, програми учасників робили багато 
непотрібних  запитів.
Вгадавши  раз кульку 500, такі програми продовжували 
запитувати, а чи не вона є наступною кулею.

Другий модуль навпаки відповідав завжди так, щоб 
Ваша програма, якомога довше не могла вгадати кожну 
кулю. Правильна програма з таким модулем повинна 
вгадувати 1000 кульок за 8987 запитів.

Правильним є алгоритм двійкового поділу з урахуванням 
вгаданих кульок.

Оцінка за програму складалася за формулою:

  (1000/кількість запитів з модулем 1)*35   +  
  (8987/ кількість запитів з модулем 2)*35

Авторський розв'язок і модулі для тестування додаються 
в архіві.


Окреме зауваження!

Майже всі учасники виводили на екран зайві повідомлення 
і пропуски перед числами.
Згідно з правилами обласної і Всеукраїнської олімпіад - 
це помилка.



Бажаю успіхів, 
Голова журі Сергій Савчук.