Задачи заочного тура региональной олимпиады по информатике 2006

Вот известная последовательность простых чисел: 2, 3, 5, 7, 11, 13, 17, … Найдите 1) `1\ 000`-е, 2) `100\ 000`-е и 3) `10\ 000\ 000`-е число в этой последовательности.

В качестве решения необходимо отправить файл, содержащий 3 строки, в каждой строке должно быть одно число. Ответы должны идти в порядке, указанном в задаче. Если какой-либо из ответов неизвестен, укажите вместо него число 0.

Оценка задачи: 5 баллов за каждый правильный ответ.

Выпишите в одну строку, не разделяя их пробелами, числа от 1 до `N`, а затем, считая с первой цифры, вычеркивайте каждую `K`-ю цифру в последовательности цифр, пока не будут вычеркнуты все цифры. При достижении конца строки счет продолжается с начала строки. Определите, какая цифра будет вычеркнута последней для заданных `N` и `K`. Например, для `N=10` и `K=3` будет следующий порядок вычеркиваний:

12345678910
12_45678910
1245_78910
124578_10
_2457810
24_7810
2478_0
2_780
278_
27_
_7
_

Последней будет вычеркнута цифра 7. Решите эту задачу для

1) `N=100`, `K=2`

2) `N=1\ 000`, `K=7`

3) `N=1\ 000\ 000`, `K=13`

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

Оценка задачи: 5 баллов за каждый правильный ответ.

Квадратное озеро разделено сеткой на `N`x`N` клеток, в узлах сетки расположены острова. Каждый остров может построить только один мост на соседний (по горизонтали или вертикали) остров или до берега озера (если он также находится по соседству). После завершения строительства мостов с каждого острова должна быть возможность дойти до берега озера и до любого другого острова, переходя с острова на остров по построенным мостам и/или двигаясь по берегу озера. Например, для `N=2` существует 4 варианта строительства мостов с соблюдением условий: с единственного острова можно построить мост вверх, вниз, влево или вправо.

На рисунке показан один из допустимых способов строительства мостов для озера 3x3. Стрелка выходит с острова, построившего соответствующий мост.

Определите количество способов строительства мостов, соблюдая указанные условия, для 1) `N=3`, 2) `N=4` и 3) `N=5`.

В качестве решения необходимо отправить файл, содержащий 3 строки, в каждой строке должно быть одно число. Ответы должны идти в порядке, указанном в задаче. Если какой-либо из ответов неизвестен, укажите вместо него число 0.

Оценка задачи: 5 баллов за каждый правильный ответ.