Заочная олимпиада (г. Омск 2005 год)

← →
_Sergey_ (2005-11-20 14:57) [0]

Недавно участвовал в данной олимпиаде, остались задания.
Хотелосб ьы узнать ваши мысли по поводу рационального решения.
Вот задания:

Задача 1. (5 баллов) Найдите все числа, сумма делителей которых равна N. Число N находится во входном файле (N≤10). В выходном файле должны быть выписаны все искомые числа в порядке возрастания в виде столбца по одному числу в каждой строке. Единицу также считать делителем числа.

Задача 2. (5 баллов) Память на жестком диске компьютера разбита на блоки, называемые параграфами, каждый размером по 16 Кб. Файл может занимать только целое количество параграфов, даже если параграф занят не весь, то он все равно отдается файлу полностью. Во входном файле в одной через пробелы указаны размеры файлов в байтах. Определите объем, занимаемый директорией на жестком диске. В выходном файле должно быть указано одно число – объем директории в байтах.

Задача 3. (10 баллов) В файле задано некоторое количество цифр N (N≤10000). Цифры расположены в одну строку и разделены пробелами. Требуется определить, можно ли из данных цифр составить N-значное простое число (нужно использовать все заданные числа и только их). Если возможно составить несколько N-значных простых чисел, программа должна определять их все. В первой строке выходного файла должно быть указано количество простых чисел, далее в каждой строке по одному числу.

Задача 4. (10 баллов) На шахматной доске расположены ладья и слон белого цвета. Сколько на данной шахматной доске клеток, на которые можно «безопасно» поставить черную пешку? То есть пешку надо расположить так, чтобы слон или ладья не могли срубить ее следующим ходом. Друг через друга слон и ладья перепрыгивать не могут. Во входном файле заданы через пробел положение сначала слона, а затем ладьи (например, h7 a4). В выходном файле находится ровно одно число – количество «безопасных» клеток.

Задача 5. (20 баллов) На листе бумаги расположены точки в N рядов по M точек в ряду (N≤10, M≤10). Расстояния между соседними точками по вертикали и по горизонтали одинаковые. Напишите программу, которая определяет количество способов, которым можно провести ломаную линию, проходящую через все точки без самопересечения. Концами отрезков ломаной обязательно должны быть точки заданные на листе бумаги (самому точки дорисовывать нельзя). Во входном файле указаны два числа через пробел (N M). В выходном файле указывается одно число. Ломаные получаемые друг из друга поворотом листа бумаги на 900 или 1800 градусов считать одними и теми же.

← →
default © (2005-11-20 15:06) [1]

ой ты не во время, тут недавно пятничные задачки были, перенасыщение дык...

← →
default © (2005-11-20 15:23) [2]

дам совет: напиши(на словах) своё решение задач ясным языком тогда возрастёт вероятность что кто-то тебе ответит (ну любят люди указывать на нерациональность решений других, а не решать рационально за других:))

← →
Yegorchic © (2005-11-20 15:38) [3]

> _Sergey_ (20.11.05 14:57)

А это олимпиада на кого расчитана (какие классы, например)?

← →
_Sergey_ (2005-11-20 16:02) [4]

Вообще проводит эту олимпиаду вуз (ОМГУ), а участвуют все желающие школьники.

Мое решение:
1). Перебираем все числа от 1 до n.
Ищем сумму делителей текущего числа. Если она равна n, то пишем число в файл.
2). Читаем размеры файлов. Если остаток деления размера файла на 16K равен нулю, тогда файл занимает целый блок, иначе файл занимает [Размер файла div 16K + 1 ] блоков. Суммируем все блоки и умножаем на 16K. Результат пишем в файл.
3,4,5 задачу как-то не сообразил :-(

← →
Lamer@fools.ua © (2005-11-20 17:07) [5]

2.

const
Granularity = 16 * 1024;
var
I: Integer;
DirSize: Int64;
Sizes: array of Int64;
begin
// [skipped] читаем Sizes...

DirSize := 0;
for I := Low(Sizes) to High(Sizes) do
Inc(DirSize, (Sizes[I] + (Granularity - 1)) div Granularity * Granularity);

WriteLn("Dir size: ", DirSize);
end.

← →
Sha © (2005-11-20 17:25) [6]

> _Sergey_
> участвуют все желающие школьники

Что-то ты напутал в условиях задачи №3 :)

← →
_Sergey_ (2005-11-20 17:27) [7]

Подумал тут немного и все-таки решил 4 задачу. Эх, зачем я уже сдал решения...

program zadanie2; uses CRT; var desk:array[1..8,1..8] of byte; f1,f2:text; s1:string[6]; s2:string[6]; x,y:integer; x1,y1:integer; x2,y2:integer; a,i,s,all:longint; procedure vyvod; begin for y:=8 downto 1 do begin for x:=1 to 8 do write(desk[x,y]," "); writeln; end; end; begin clrscr; assign(f1,"INPUT.TXT"); assign(f2,"OUTPUT.TXT"); reset(f1); rewrite(f2); read(f1,s1); s2:=copy(s1,4,2); s1:=copy(s1,1,2); for x:=1 to 8 do for y:=1 to 8 do desk[x,y]:=0; x1:=ord(s1[1])-ord("a")+1; y1:=ord(s1[2])-ord("0"); desk[x1,y1]:=1; writeln(x1,y1); x2:=ord(s2[1])-ord("a")+1; y2:=ord(s2[2])-ord("0"); desk[x2,y2]:=2; writeln(x2,y2); x:=x1; y:=y1; while (desk[x,y]<>2) and (x<=8) do begin desk[x,y]:=3; inc(x); end; x:=x1; y:=y1; while (desk[x,y]<>2) and (x>=1) do begin desk[x,y]:=3; dec(x); end; x:=x1; y:=y1; while (desk[x,y]<>2) and (y<=8) do begin desk[x,y]:=3; inc(y); end; x:=x1; y:=y1; while (desk[x,y]<>2) and (y>=1) do begin desk[x,y]:=3; dec(y); end; x:=x2; y:=y2; while (desk[x,y]<>1) and (x>=1) and (y>=1) do begin desk[x,y]:=4; dec(x); dec(y); end; x:=x2; y:=y2; while (desk[x,y]<>1) and (x<=8) and (y<=8) do begin desk[x,y]:=4; inc(x); inc(y); end; x:=x2; y:=y2; while (desk[x,y]<>1) and (x<=8) and (y>=1) do begin desk[x,y]:=4; inc(x); dec(y); end; x:=x2; y:=y2; while (desk[x,y]<>1) and (x>=0) and (y<=8) do begin desk[x,y]:=4; dec(x); inc(y); end; desk[x1,y1]:=1; desk[x2,y2]:=2; a:=0; for y:=1 to 8 do for x:=1 to 8 do if desk[x,y]=0 then inc(a); vyvod; writeln(f2,a); close(f1); close(f2); readln; end.

Но задача решена "через задницу" и как-то долго. Нет ли чего попроще?

← →
_Sergey_ (2005-11-20 17:29) [8]

> Что-то ты напутал в условиях задачи №3 :)

Мне почему-то тоже так кажется... И напутал не я, а составители заданий. Ну как может быть цифр быть <=10000? Разве что они могут повторяться...

← →
SergProger © (2005-11-20 22:04) [9]

Люди. Готовлюсь к олимпиаде. Кому не лень, отправьте какие-нибудь задачки на e-mail sergmail@atnet.ru. Можно без решений.

← →
SergP. (2005-11-20 22:28) [10]

> _Sergey_ (20.11.05 16:02) [4]
> 2). Читаем размеры файлов. Если остаток деления размера
> файла на 16K равен нулю, тогда файл занимает целый блок,
> иначе файл занимает [Размер файла div 16K + 1 ] блоков.

[(Размер файла-1) div 16K + 1]

← →
Lamer@fools.ua © (2005-11-20 22:53) [11]

>>SergP. (20.11.05 22:28) [10]

А если "Размер файла" = 0?

← →
Lamer@fools.ua © (2005-11-20 22:54) [12]

P.S. К тому же, Вы на 16K забыли умножить.

← →
SergP. (2005-11-20 23:16) [13]

> Lamer@fools.ua © (20.11.05 22:54) [12]
> P.S. К тому же, Вы на 16K забыли умножить.

Это было в блоках...

> Lamer@fools.ua © (20.11.05 22:53) [11]
> >>SergP. (20.11.05 22:28) [10]
>
> А если "Размер файла" = 0?

Забыл про это... Просто файлы с нулевым размером не очень часто встречаются...

В таком случае:

(размерфайла+16383) and -16384

← →
Думкин © (2005-11-21 08:30) [14]

> _Sergey_ (20.11.05 17:29) [8]

Ну пусть повторяются. А вот как определить влегкую простоту числа в 10000 знаков?
Да и чисел из 10000 знаков можно составить - мама не горюй сколько.

← →
Булат Шакиров © (2005-11-21 08:56) [15]

> SergProger © (20.11.05 22:04) [9]
> Люди. Готовлюсь к олимпиаде. Кому не лень, отправьте какие-
> нибудь задачки на e-mail sergmail@atnet.ru. Можно без решений.
>

http://www.dstu.edu.ru/informatics/olimp/mtd1/mtd_ol.html

← →
_Sergey_ (2005-11-21 12:24) [17]

> Да и чисел из 10000 знаков можно составить - мама не горюй
> сколько.

Вроде бы их можно составить 10000!/9990!/10!. Что тоже очень много, да и в longint не поместится. Можно использовать массив, но как-то все это криво.
А насчет 5-ой задачи есть какие-нибудь мысли?

← →
_Sergey_ (2005-11-21 13:23) [18]

Кстати, в 3 задаче действительно косяк (узнал у составителей заданий), только какого рода пока говорить не хотят (не проверили еще все решения).

← →
имя (2005-11-21 14:34) [19]

Удалено модератором

← →
имя (2005-11-21 14:35) [20]

Удалено модератором

> Вроде бы их можно составить 10000!/9990!/10!. Что тоже очень
> много, да и в longint не поместится.

Можно и массив array of byte. Но как долго будет происходить поиск простых...

Заочная олимпиада (г. Омск 2005 год) Найти похожие ветки