Задача Московской олимпиады по программированию

и задачки для интервью.
skier
Новичок
Posts: 55
Joined: 01 Apr 2001 10:01
Location: Redmond

Задача Московской олимпиады по программированию

Post by skier »

«Создать программу, которая по последовательности сгибов и переворачиваний географической карты выдает последовательность расположения квадратов карты друг относительно друга в полностью сложенной карте».
http://zdnet.ru/news.asp?ID=2972

Как понял, карта здесь не причем. Лучще сказать так - дан лист бумаги в клеточку (крупную) и задана последовательность сгибов. Каждая клеточка была пронумерована. Отгадать последовательность клеточек после сгибания.
sha
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задача Московской олимпиады по программированию

Post by sha »

Я так понимаю, что если есть возможность сохранить каким-то образом нумерацию, т.е. "проэмулировать" все сложения, то проблем нет. Т.е. заполняем поле N*M номерами от 1 до N*M, а потом преобразуем массив 1*M*N в 2*(N/2)*M... и т.д. до (M*N)*1*1.

Видимо стояла задача сделать это ьез использования памяти, т.е. чтобы все рассчитывалось... С этим видимо все не так просто... [img:d5b9a8b02f]images/smiles/icon_smile.gif[/img:d5b9a8b02f]
User avatar
Melkor
Уже с Приветом
Posts: 1257
Joined: 03 Oct 2001 09:01
Location: Valinor->Utumno->Angband

Задача Московской олимпиады по программированию

Post by Melkor »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by sha:
<STRONG>Я так понимаю, что если есть возможность сохранить каким-то образом нумерацию, т.е. "проэмулировать" все сложения, то проблем нет. Т.е. заполняем поле N*M номерами от 1 до N*M, а потом преобразуем массив 1*M*N в 2*(N/2)*M... и т.д. до (M*N)*1*1.

Видимо стояла задача сделать это ьез использования памяти, т.е. чтобы все рассчитывалось... С этим видимо все не так просто... [img:9f6c3ea3bb]images/smiles/icon_smile.gif[/img:9f6c3ea3bb]</STRONG><HR></BLOCKQUOTE>

Но все равно как-то скучно звучит. На организацию оптимального bookkeeping. Типа, на разных прямоугольных участках карты после каждого сгиба появляется определенная формула для каждого слоя (может, конечно, и есть более красивое решение). Может, никто ее не стал решать, т.к. скучная больно? А вот интересней, imho, было бы, если бы надо было восстановить сгибы по сложенному состоянию.
Drom
Уже с Приветом
Posts: 242
Joined: 03 Jan 2000 10:01
Location: TX > MA/NH > NJ/NYC

Задача Московской олимпиады по программированию

Post by Drom »

ссылка с задачами с ICPC. просто чтоб было: http://icpc.baylor.edu/past/default.htm
Arty
Новичок
Posts: 38
Joined: 07 Oct 2001 09:01
Location: Donetsk, Ukraine

Задача Московской олимпиады по программированию

Post by Arty »

По моему всё легко

чисто рекурсивная задача.

Делим лист на две части и смотрим, как расплолжены страницы внутри....

Это я так, сходу, возможно позже алгоритм напишу сюда...
User avatar
Melkor
Уже с Приветом
Posts: 1257
Joined: 03 Oct 2001 09:01
Location: Valinor->Utumno->Angband

Задача Московской олимпиады по программированию

Post by Melkor »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Arty:
<STRONG>По моему всё легко

чисто рекурсивная задача.

Делим лист на две части и смотрим, как расплолжены страницы внутри....

Это я так, сходу, возможно позже алгоритм напишу сюда...</STRONG><HR></BLOCKQUOTE>

Я так думаю, сгибы могут быть не обязательно строго пополам.
skier
Новичок
Posts: 55
Joined: 01 Apr 2001 10:01
Location: Redmond

Задача Московской олимпиады по программированию

Post by skier »

Да, действительно. Если можно использовать память, то вроде ничего сложного. Может там правда можно было сгибать и не по линиям, паралельным сторонам...
Arty
Новичок
Posts: 38
Joined: 07 Oct 2001 09:01
Location: Donetsk, Ukraine

Задача Московской олимпиады по программированию

Post by Arty »

???????????????//

Обязательно, как же ещё им быть??? [img:483c2978a9]images/smiles/icon_eek.gif[/img:483c2978a9]
User avatar
Melkor
Уже с Приветом
Posts: 1257
Joined: 03 Oct 2001 09:01
Location: Valinor->Utumno->Angband

Задача Московской олимпиады по программированию

Post by Melkor »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Arty:
<STRONG>???????????????//

Обязательно, как же ещё им быть??? [img:b74cb7f446]images/smiles/icon_eek.gif[/img:b74cb7f446]</STRONG><HR></BLOCKQUOTE>

Ну как, есть, скажем, лист 10х10, мы загибаем крайне правую колонку, получается 10х9, и т.д.
Stonehange
Новичок
Posts: 79
Joined: 22 Oct 2001 09:01

Задача Московской олимпиады по программированию

Post by Stonehange »

Всё верно.

Ещё лист бумаги можно складывать по диагонали и вырезать из него звёздочки!

В условии про это ничего не сказано [img:3c6c0ff039]images/smiles/icon_wink.gif[/img:3c6c0ff039]
Stonehange
Новичок
Posts: 79
Joined: 22 Oct 2001 09:01

Задача Московской олимпиады по программированию

Post by Stonehange »

Как обещал,даю решение

Условие зажачи некорректно, так как не указана последовательность
сгибов, а так же порядок нумерации.

я беру слева направо сниз вверх, одностороняя нумерация листа


#include <stdio.h>
void main()
{
int a[1024];int b[1024];
int i,j,xx,k,c=2;//кол-во складываний
for(i=0;i<1024;i++) a[i]=0;
a[0]=1;
for(i=0;i<c;i++)
{
k=1;
for(xx=0;xx<i;xx++) k*=2;
for(j=0;j<k;j++) a[j+k]=k+a[k-j-1];
}
printf(" \n");
for(i=0;i<k*2;i++) printf("%d ",a[i]);
}

Return to “Головоломки”