«Создать программу, которая по последовательности сгибов и переворачиваний географической карты выдает последовательность расположения квадратов карты друг относительно друга в полностью сложенной карте».
http://zdnet.ru/news.asp?ID=2972
Как понял, карта здесь не причем. Лучще сказать так - дан лист бумаги в клеточку (крупную) и задана последовательность сгибов. Каждая клеточка была пронумерована. Отгадать последовательность клеточек после сгибания.
Задача Московской олимпиады по программированию
-
- Новичок
- Posts: 55
- Joined: 01 Apr 2001 10:01
- Location: Redmond
-
- Уже с Приветом
- Posts: 281
- Joined: 28 Jul 2000 09:01
- Location: Minsk > CA > NC > WA > CA
Задача Московской олимпиады по программированию
Я так понимаю, что если есть возможность сохранить каким-то образом нумерацию, т.е. "проэмулировать" все сложения, то проблем нет. Т.е. заполняем поле 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]
Видимо стояла задача сделать это ьез использования памяти, т.е. чтобы все рассчитывалось... С этим видимо все не так просто... [img:d5b9a8b02f]images/smiles/icon_smile.gif[/img:d5b9a8b02f]
-
- Уже с Приветом
- Posts: 1257
- Joined: 03 Oct 2001 09:01
- Location: Valinor->Utumno->Angband
Задача Московской олимпиады по программированию
<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, было бы, если бы надо было восстановить сгибы по сложенному состоянию.
<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, было бы, если бы надо было восстановить сгибы по сложенному состоянию.
-
- Уже с Приветом
- Posts: 242
- Joined: 03 Jan 2000 10:01
- Location: TX > MA/NH > NJ/NYC
Задача Московской олимпиады по программированию
ссылка с задачами с ICPC. просто чтоб было: http://icpc.baylor.edu/past/default.htm
-
- Новичок
- Posts: 38
- Joined: 07 Oct 2001 09:01
- Location: Donetsk, Ukraine
Задача Московской олимпиады по программированию
По моему всё легко
чисто рекурсивная задача.
Делим лист на две части и смотрим, как расплолжены страницы внутри....
Это я так, сходу, возможно позже алгоритм напишу сюда...
чисто рекурсивная задача.
Делим лист на две части и смотрим, как расплолжены страницы внутри....
Это я так, сходу, возможно позже алгоритм напишу сюда...
-
- Уже с Приветом
- Posts: 1257
- Joined: 03 Oct 2001 09:01
- Location: Valinor->Utumno->Angband
Задача Московской олимпиады по программированию
<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Arty:
<STRONG>По моему всё легко
чисто рекурсивная задача.
Делим лист на две части и смотрим, как расплолжены страницы внутри....
Это я так, сходу, возможно позже алгоритм напишу сюда...</STRONG><HR></BLOCKQUOTE>
Я так думаю, сгибы могут быть не обязательно строго пополам.
<STRONG>По моему всё легко
чисто рекурсивная задача.
Делим лист на две части и смотрим, как расплолжены страницы внутри....
Это я так, сходу, возможно позже алгоритм напишу сюда...</STRONG><HR></BLOCKQUOTE>
Я так думаю, сгибы могут быть не обязательно строго пополам.
-
- Новичок
- Posts: 55
- Joined: 01 Apr 2001 10:01
- Location: Redmond
Задача Московской олимпиады по программированию
Да, действительно. Если можно использовать память, то вроде ничего сложного. Может там правда можно было сгибать и не по линиям, паралельным сторонам...
-
- Новичок
- Posts: 38
- Joined: 07 Oct 2001 09:01
- Location: Donetsk, Ukraine
Задача Московской олимпиады по программированию
???????????????//
Обязательно, как же ещё им быть??? [img:483c2978a9]images/smiles/icon_eek.gif[/img:483c2978a9]
Обязательно, как же ещё им быть??? [img:483c2978a9]images/smiles/icon_eek.gif[/img:483c2978a9]
-
- Уже с Приветом
- Posts: 1257
- Joined: 03 Oct 2001 09:01
- Location: Valinor->Utumno->Angband
Задача Московской олимпиады по программированию
<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, и т.д.
<STRONG>???????????????//
Обязательно, как же ещё им быть??? [img:b74cb7f446]images/smiles/icon_eek.gif[/img:b74cb7f446]</STRONG><HR></BLOCKQUOTE>
Ну как, есть, скажем, лист 10х10, мы загибаем крайне правую колонку, получается 10х9, и т.д.
-
- Новичок
- Posts: 79
- Joined: 22 Oct 2001 09:01
Задача Московской олимпиады по программированию
Всё верно.
Ещё лист бумаги можно складывать по диагонали и вырезать из него звёздочки!
В условии про это ничего не сказано [img:3c6c0ff039]images/smiles/icon_wink.gif[/img:3c6c0ff039]
Ещё лист бумаги можно складывать по диагонали и вырезать из него звёздочки!
В условии про это ничего не сказано [img:3c6c0ff039]images/smiles/icon_wink.gif[/img:3c6c0ff039]
-
- Новичок
- Posts: 79
- Joined: 22 Oct 2001 09:01
Задача Московской олимпиады по программированию
Как обещал,даю решение
Условие зажачи некорректно, так как не указана последовательность
сгибов, а так же порядок нумерации.
я беру слева направо сниз вверх, одностороняя нумерация листа
#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]);
}
Условие зажачи некорректно, так как не указана последовательность
сгибов, а так же порядок нумерации.
я беру слева направо сниз вверх, одностороняя нумерация листа
#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]);
}