Олимпиада по информатике

← →
Footballer © (2007-01-14 12:47) [0]

В пятницу у нас проходила олимпиада по информатике среди 9 - 11 кл
Если кому-то интересно проверить себя, ниже идут задачи:

Всероссийская олимпиада по информатике III (зональный) этап

Задача 1. Таймер (10 баллов)
Таймер - это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал.
Формат входных данных:
В первой строке входного файла записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям:
ЧЧ - от 00 до 23, ММ и СС - от 00 до 59.
Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 119, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0. При этом 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.
Формат выходных данных:
В выходной файл выведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол во> days Например, если сигнал прозвучит на следующий день - то +1 days
Примеры:
a.in
01:01:01
48:0:0.
а.out
01:01:01+2 days
a.in
01:01:01
58:119
а.out
02:01:00
а.in
23:59:59
1
a.out
00:00:00 +1 days

Задача 2. Равновеликие прямоугольники. (15 баллов)
Прямоугольники, площади которых равны, называются равновеликими. Написать программу. находящую все возможные целочисленные стороны равновеликих прямоугольников заданной площади. Одинаковые прямоугольники, получающиеся заменой сторон. печатать не надо.
Входные данные:
Площадь четырехугольника (1<=n<=50000).
Выходные данные:
Стороны четырехугольника (А*В) ; -
Пример входных данных:
12
Пример выходных данных:
1*12
2*6
3*4

Задача 3. Трамвайные билеты. (20 баллов)
Написать программу определения количества шестизначных «счастливых» трамвайных билетов, у которых сумма первых трех цифр совпадает с суммой трех последних. Оптимизировать решение по времени выполнения. Количество билетов вывести в файл

Задача 4. (25 баллов)
Из-за экономического кризиса многие предприятия не могут получить долги от покупателей и рассчитаться с продавцами за свои долги. Банк намерен уменьшить общий долг своих клиентов, выполнив взаимозачет долгов. Для этого банк может изменять долги клиентов любым образом при условии, что для каждого клиента останется неизменным сальдо - разница между суммой долгов ему и суммой его долгов. Написать программу, которая преобразует заданный список долгов в имеющий как можно меньшую общую сумму долгов.
Технические условия
1 . Ваша программа должна прочитать входные данные для нескольких тестов из одного текстового ASCII-файла DEDTS.DАТ. Данные для различных тестов отделены пустой строкой. Каждая строка файла соответствует одному долговому обязательству и содержит три натуральных числа: номер должника, номер предприятия, которому он должен, и сумму долга. Соседние числа отделены пробелом.
2. Ваша программа должна записать результаты для всех тестов в один текстовый ASCII-файл DEDTS.SOL, отделяя результаты различных тестов пустой строкой. Результат каждого теста имеет содержать список долгов, оставшихся после взаимозачетов. Этот список должен иметь такую же структуру, что и входной. За ним надо вывести список сальдо всех клиентов, которые были должниками или имели должников. Каждая строка этого списка содержит номер предприятия и его сальдо, отделенные пробелом. В конце результатов теста надо в отдельной строке вывести общую сумму долгов.
3. Количество предприятий не превышает 100, денежные суммы не превышают 30000 единиц.
4. Имя файла с исходным текстом программы - DEBTS.*
Пример входного файла:
1 2 100
2 3 50
3 1 75

1 2 15
2 3 11
4 1 14

Пример выходного файла:
1 2 25
3 2 25
1 -25
2 50
3 -25
50

1 2 1
4 2 4
4 3 11
1 -1
2 4
3 11
4 -14
15

Задача 5. Домино (30 баллов)
Написать программу DOMINO.*, подсчитывающую количество вариантов покрытия прямоугольника 2xN прямоугольниками 2x1. Покрытия, которые преобразуются одно в другое симметриями, считать различными.
Входные данные:
Входной файл DOMINO.ВАТ содержит число N (0 < N < 65536).
Выходные данные:
Выходной файл DOMINO.SOL должен содержать одно число: количество вариантов.
Примеры ввода и вывода
DOMINO.ВАТ : 1
DOMINO.SOL : 1

← →
Footballer © (2007-01-14 12:47) [1]

Задача 1 и Задача 2:
Их я решил и получил свои баллы

Задача 3:
Её то я тоже решил, но... когда её стали проверять, сказали НЕПРАВИЛЬНО
Я ошарашен... Вот, посмотрите ответ: 50412. Попросил решить эту задачу Geller"а и у него 50412! Уверен в правильности на 99,9 %. ТУПО! Может они поймут свою ошибку...

Задача 4:
А тут совсем смешно получилось: все 4 преподователя, которые сидели в жюри пытались решить эту задачу, и не смогли :))) Ну, что касается меня, я успел сделать только считывание данных из файла, но может и за это пару баллов дадут...

Задача 5:
Тут у меня даже идей никаких нет...

← →
Footballer © (2007-01-14 12:49) [2]

И что касается 3-ей задачи:
Вот исходный код:
program n3; uses crt; var i, n1, n2, n3, n4, n5, n6, S:longint; begin s:=0; clrscr; for i:= 100000 to 999999 do begin n1:= i div 100000; n2:= (i div 10000) mod 10; n3:= (i div 1000) mod 10; n4:= (i div 100) mod 10; n5:= (i div 10) mod 10; n6:= i mod 10; if n1 + n2 + n3 = n4 + n5 + n6 then inc(S); end; writeln(S); readkey; end.

ЗЫ Забыл сказать, что все задачи пишутся на Pascal

← →
MeF Dei Corvi © (2007-01-14 12:52) [3]

Странные какие-то у вас олимпиады... У нас запрещали использование всяких дополнительных модулей + автоматическая проверка.

← →
MBo © (2007-01-14 12:52) [4]

3 - номера билетов с 0, а не с 100000 идут.
Кроме того, твое решение требует около порядка миллиона операций, а для олмпиады нужно решение более быстрое

← →
ProgRAMmer Dimonych © (2007-01-14 13:41) [5]

У В.М. Котова в "Методах алгоритмизации" было...

Count:=0;
for T:=0 to 13 do
begin
CT:=0;
for a1:=Max(0,T-18) to min(9,T) do
CT:=CT+min(9,T-a1)-max(0,T-a1-9)+1;
Count:=Count+CT*CT;
end;
Count:=Count*2;

Вот вам.

← →
J_f_S (2007-01-14 13:43) [6]

По третьей, решение на С
int main(int argc, char* argv[]) { int sum[27]; int sum2[27]; for (int i = 0; i< 27; i++) sum[i] = sum2[i] = 0; for (i = 100; i < 999; i++) sum[i / 100 + (i / 10) % 10 + i % 10 - 1]++; for (i = 1; i < 999; i++) sum2[i / 100 + (i / 10) % 10 + i % 10 - 1]++; int total = 0; for (i = 0; i< 27; i++) total += sum[i]*sum2[i]; printf("result = %d\n", total); return 0; }

Ответ: 50411. И гораздо меньше вычислений. И то можно уменьшить.

← →
J_f_S (2007-01-14 13:47) [7]

Табы ёкарный парсер побил.

← →
ProgRAMmer Dimonych © (2007-01-14 13:48) [8]

Люди, а подумать??? :)

По условию надо, чтобы был выходной файл с правильным ответом... Это же подарок!!! Почти как задачи с открытыми тестами. Пишем любую программу, которая выдаёт ответ, а сдаём программу, которая сразу выводит ответ в файл. Хотя на регионалке иногда в исходник заглядывают. :(

← →
Footballer © (2007-01-14 14:15) [9]

> У нас запрещали использование всяких дополнительных модулей
> + автоматическая проверка.

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

> MBo © (14.01.07 12:52) [4]
> 3 - номера билетов с 0, а не с 100000 идут.

определения количества шестизначных «счастливых» трамвайных билетов

> а для олмпиады нужно решение более быстрое

Например...

> J_f_S (14.01.07 13:43) [6]
> По третьей, решение на С

В Си я не разбираюсь, но помоему у тебя билиты с 0 номируются, а не со 100000

> ProgRAMmer Dimonych © (14.01.07 13:48) [8]

Не-а, не прокатит. Предупреждали даже, что будут исходники проверять, не хочу рисковать...

← →
Gero © (2007-01-14 14:18) [10]

> [8] ProgRAMmer Dimonych © (14.01.07 13:48)
> Пишем любую программу, которая выдаёт ответ, а сдаём программу,
> которая сразу выводит ответ в файл

Это что еще за бред ты придумал? Поясни гениальную мысль.

← →
Gero © (2007-01-14 14:19) [11]

> [1] Footballer © (14.01.07 12:47)
> Уверен в правильности на 99,9 %.

Ты слишком самоуверен.

← →
Gero © (2007-01-14 14:21) [12]

> [2] Footballer © (14.01.07 12:49)
> clrscr;

Это не нужно писать, в некоторых случаях за такое могут снизить баллы. Вобще Crt не нужно использовать, вам должны были об этом сообщить.

← →
MBo © (2007-01-14 14:21) [13]

>определения количества шестизначных «счастливых» трамвайных билетов

Ты билеты видел? На них всегда 6 цифр (с ведущими нулями при необходимости)

← →
J_f_S (2007-01-14 14:22) [14]

> Footballer © (14.01.07 14:15) [9]
> > а для олмпиады нужно решение более быстрое
>
> Например...
>
> > J_f_S (14.01.07 13:43) [6]
> > По третьей, решение на С
>
> В Си я не разбираюсь, но помоему у тебя билиты с 0 номируются,
> а не со 100000

Например, моё решение. Билеты нумеруются с 100.000. Посмотри алгоритм. Он очень прост и быстр.

← →
Gero © (2007-01-14 14:22) [15]

> [13] MBo © (14.01.07 14:21)

А если не видел, то задачу не может написать? Минус составителю.

← →
MBo © (2007-01-14 14:24) [16]

5. Нарисовав несколько первых конфигураций доминошек, можно понять закономерность, приводящую к числам Фибоначчи

← →
Ricks © (2007-01-14 14:37) [17]

правильный ответ на 3-ю задачу: 55252

делал для себя (т.е для интереса - в смысле оптимизацией не занимался), получилось вот что:
var a1, a2, a3 : byte; b1, b2, b3 : byte; f : TextFile; tT, hT : Cardinal; begin tT:=0; hT:=0; AssignFile(f, "ticket.txt"); Rewrite(f); for a1:=0 to 9 do for a2:=0 to 9 do for a3:=0 to 9 do for b1:=0 to 9 do for b2:=0 to 9 do for b3:=0 to 9 do begin if ( a1 + a2 + a3 ) = (b1 + b2 + b3) then begin WriteLn(f, a1, a2, a3, b1, b2, b3); Flush(f); Inc(hT); end; Inc(tT); end; WriteLn(f, "Всего билетов : ", tT ); WriteLn(f, "из них счастливых : ", hT ); WriteLn(f, "Вероятность : ", (hT/tT):7:7, " (", (100 * hT/tT):7:7, "%)"); CloseFile(f);

Но все номера находит очень быстро!

← →
J_f_S (2007-01-14 14:42) [18]

> Ricks © (14.01.07 14:37) [17]
>
> правильный ответ на 3-ю задачу: 55252
>
> делал для себя (т.е для интереса - в смысле оптимизацией
> не занимался), получилось вот что:

Га-га-га-га....
У тебя программа- аналог авторской. Только к тому же абсолютно неверная.
За стиль кодирования - на пересдачу экзамена по ЯВУ, или как там у вас.

← →
Gero © (2007-01-14 14:48) [19]

> [17] Ricks © (14.01.07 14:37)

Представляю, если бы номер был 20-значным&#133

← →
Ricks © (2007-01-14 14:51) [20]

> J_f_S

Во-первых, у меня билеты все-таки с нуля. А ты наверное работал кондуктором и точно знаешь что с 100000?
Во-вторых у тебя офигенно верная программа, но не на паскале а на С, так что если бы кто-нибудь написал на assembler тоже мог бы выделываться что мол у меня программа самая лучшая итд итп...

← →
PHPdeveloper (2007-01-14 14:53) [21]

g6prog.narod.ru
тут есть пример решения задачи про билеты

← →
J_f_S (2007-01-14 14:56) [22]

> PHPdeveloper (14.01.07 14:53) [21]
>
> g6prog.narod.ru
> тут есть пример решения задачи про билеты

Зашибись. Моё решение :))) Единственно, там номера билетов идут с 0, а у меня модификация для случая с 100.000 (по условию).

← →
Ricks © (2007-01-14 14:58) [23]

Глянь, наехали на меня!
Перечитайте то, что я написал перед кодом - я ничего не оптимизировал!!!

А решение оно находит (вместе с записью в файл ВСЕХ номеров) примерно за секунду на моем PIII, 650Hz

← →
_uw_ (2007-01-14 15:23) [24]

А и в самом деле, с небольшой поправкой алгоритм J_f_S дает верный результат:

function LuckyNumbers: Integer; var sum: array[0..27] of Integer; i, j, k: Integer; begin for i := 0 to 26 do sum[i] := 0; for i := 0 to 9 do for j := 0 to 9 do for k := 0 to 9 do Inc(sum[i + j + k]); Result := 1; for i := 0 to 26 do Inc(Result, sum[i]*sum[i]); end;
Почему - не понимаю!

← →
iXT © (2007-01-14 15:34) [25]

Помнится как-то Microsoft кучу бабок предлагала за первое простое число содержащее млн. знаков. Может переберем? .... :)

← →
PHPdeveloper (2007-01-14 15:54) [26]

Кто начнет :) ?

← →
ProgRAMmer Dimonych © (2007-01-14 16:05) [27]

> Gero © (14.01.07 14:18) [10]
> > [8] ProgRAMmer Dimonych © (14.01.07 13:48)
> > Пишем любую программу, которая выдаёт ответ, а сдаём программу,
> > которая сразу выводит ответ в файл
> Это что еще за бред ты придумал? Поясни гениальную мысль.
Ответ вычисляем как угодно, а программа только создаёт файл с ответом :)

> PHPdeveloper (14.01.07 15:54) [26]
Я у меня числа до 10000000 есть, осталось всего ничего... :)

Да, кстати, варианты с 6-ю и 3-мя вложенными циклами - медленные, они у того же Котова идут олько как первый и второй способы. А самый быстрый - четвёртый, см. выше: [5]

← →
vidiv © (2007-01-14 16:11) [28]

> iXT © (14.01.07 15:34) [25]
> Помнится как-то Microsoft кучу бабок предлагала за первое
> простое число содержащее млн. знаков. Может переберем? .
> ... :)

а докажем как?

← →
vidiv © (2007-01-14 16:26) [29]

Помнится я на районной олимпиаде первое место занял =))

← →
ProgRAMmer Dimonych © (2007-01-14 16:30) [30]

> vidiv © (14.01.07 16:11) [28]
> а докажем как?
А за доказательство они нам не платят :) Пусть сами доказывают, может быть у них написать проверяющую программу получится лучше, чем операционную систему...

← →
Footballer © (2007-01-14 16:46) [31]

> Помнится я на районной олимпиаде первое место занял =))

А на зональной чё занял?

← →
vidiv © (2007-01-14 16:47) [32]

Если взять любое простое число большее 20 к примеру, умножить его на 10 и прибавить 11, получим ли мы всегда простое число?

> А на зональной чё занял?

У нас это назвается областной олимпиадой... занял почетное 4ое место =))

3. решается обобщённым треугольником паскаля. Я за секунду 100 значные нормально искал на джаве. Да, и кстати, по всем канонам решение writeln("55252") должно засчитываться.

5. Должно быть чила Фибоначчи.

> [27] ProgRAMmer Dimonych © (14.01.07 16:05)
> Ответ вычисляем как угодно

Если ты можешь вычилисть ответ, но написание кода не будет являться прорблемой.

> [35] ferr © (14.01.07 17:53)
> Да, и кстати, по всем канонам решение writeln("55252") должно
> засчитываться.

Конечно.

А вобще задача без входныъх данных не должна быть на олимпиаде подобного уровня, еще один минус составителю.

Билет должен быть n-значым, где n — четное натуральное число, тогда все становится на свои места.

Вот програмка, вычисляющая первое простое число содержащее млн. знаков :)))
var i:integer; f:TextFile; s:string; begin Randomize; s:= "1"; //чтобы не вызвать подозрений :) for i:= 1 to 99999 do s:= s + inttostr(trunc(random(10000000000))); AssignFile(f, "C:/q.txt"); Rewrite(f); Write(f, s); CloseFile(f);

Получился файлик ровно 900 KB, остаётся только отдать его Microsoft и забрать честно заработанные бабки :-D

Кстати, насчёт олимпиады, распределения баллов по-моему тупое:

2-ая задача (15 баллов) самая лёгкая, ну вообще делать нечего;
3-ья задача (20 баллов) тоже очень лёгкая, если не обламаться как я :)
1-ая задача (10 баллов) вроде как не очень сложная, но там очень много писать;
4-ая задача (25 баллов) самая сложная, её даже взрослые преподаватели не смогли решить
5-ая задача (30 баллов) Вроде не очень сложная, просто надо знать числа Фибоначчи (кстати что это такое?), а без этого тут делать нечего...

> 5-ая задача (30 баллов) Вроде не очень сложная, просто надо
> знать числа Фибоначчи (кстати что это такое?), а без этого
> тут делать нечего...

Ты явно не читал Дэна Брауна. =) И не читай. =) Это самое попсовое реккурентное соотношения. F(n) = F(n - 1) + F(n - 2). 1 1 2 3 5 8 13 ... Появляется во многих задачах.

То есть каждое новое число образуется суммой 2-х предыдущих?

← →
PHPdeveloper (2007-01-14 20:06) [44]

> числа Фибоначчи (кстати что это такое?

http://g6prog.narod.ru/books.html

Такс.. Посмотерел 4. Она действительно сложнее 5-ой.
Какое могу предложить решение : Выделяем все циклы в графе. Это можно сделать одним проходом dfs за O(V^2). Имеем цикл и надо сделать сумму весов рёбер как можно меньшей (по модулю). Для этого складываем все веса рёбер цикла и делим на количество рёбер. Получившееся число вычитаем из весов всех рёбер цикла.

Проблемы могут возникнуть если один цикл содержит другой, но вроде не должны..

Для первого теста, матрица смежности выглядит так

1 2 100 2 3 50 3 1 75 1 2 3 1 - 100 -75 2 -100 - 50 3 75 -50 -

vidiv © (14.01.07 16:11) [28]
а докажем как?
допустим так:
Тест на основе малой теоремы Ферма. если n простое, то выполняется условие:
При всех а из {2, 3,…n-1} имеет место сравнение a^(n-1)=1 mod n

vidiv © (14.01.07 16:47) [32]

есть такая теорема:

Теорема (Диемитко): Пусть n = qR+1 > 1,
где q - простое, R - четное и R<4(q+1).
Если существует целое а такое, что
а^(n-1) = 1 mod n
a^((n-1)/q) <> 1 mod n
то n - простое.

вперёд.

Олимпиада по информатике Найти похожие ветки