Programlama yarismasi

[picusta]

http://www.cclub.metu.edu.tr  'de alintidir

Soru 2 - Sinema Salonu

Alphan'ın koridordan bozma sinema salonunda gösterilen film çok başarılı olduğundan olsa gerek ki salonda hiç boş koltuk kalmamıştır. Fakat müşteriler sinema perdesini iyi göremedikleri için biraz sinirlenmişlerdir. Her müşterinin sinir seviyesi, önünde oturan kendinden uzun insan sayısına eşittir. Alphan seyircilerin boylarını merak etmekte, ama salon karanlık olduğu için görememektedir. Sinirli müşterilerin homurtlularından hangi koltuktaki müşterinin ne kadar sinirli olduğunu söyleyebilmektedir. Sizden istenilen, Alphan'ın verdiği sinir seviyelerinden yola çıkarak her koltuktaki müşterinin boyunu bulmanız.
Varsayımlar

   * Sinema salonu 1'erli N sıra koltuktan oluşmaktadır. (1 ≤ N ≤ 500000)
   * Her müşterinin sinir seviyesi en az 0, en fazla N-1 olabilir.
   * Her müşterinin boyu 1 ve N arasında (1 ve N dahil) bir tam sayıdır ve salonda boyu eşit herhangi iki müşteri yoktur.

Girdi (sinema.gir)

   * Girdi dosyası sinema.gir'in ilk satırında sinema salonundaki koltuk sayısı olan N tamsayısı bulunacaktır.
   * İkinci satırda N adet müşterinin sinir seviyesi sinema perdesine en yakın koltukta oturan müşteriden başlamak üzere aralarında birer boşlukla verilecektir.

Çıktı (sinema.cik)

   * Programınız sinema.cik dosyasının ilk (ve tek) satırına N adet müşterinin boyunu sinema perdesine en yakın koltukta oturan müşteriden başlamak üzere aralarında birer boşluk bırakarak yazacaktır.

Örnek

sinema.gir:

5
0 0 2 3 2
   

sinema.cik:

4 5 2 1 3

Nasil bir algoritma kullanabiliriz ?

[picusta]

Aklima bir fikir geldi, en uzun kisi her zaman 0 olacak, çünkü görüsünü engelleyecek kimse yok, en arkada olsa bile.
Yani en son baslarsak, ilk buldugumuz 0 en uzun kisiye denk gelecek ve boyu  N olacak. Bundan yola çikarak en uzun ikinci, üçüncü , N'inci izleyiciyi bulabiliriz.
C veya BASIC veya java'da nasil yazilir?
diyelim girdileri bir tabloya kaydettik, çikis tablosunu nasil olusturacagiz? Nasil bir döngü yapmaliyiz ?

[ferdem]

Ben bir algoritma düşündüm ancak C diline henüz dökemedim. Sıradaki adamların boylarını tespit etmek için en arkadaki adamdam başlamak mantıklı:

sinema.gir:

5
0 0 2 3 2

En arkadaki adam "benden uzun 2 kişi var abi" diyor, o zaman bu adam bu grupta 3 birim boylu olandır.

Kalan gruptakiler: 1,2,4,5

Bir önündeki adam "benden uzun 3 kişi var abi" diyor, o zaman bu adam ancak 1 birim boylu olabilir.

Kalan grup: 2,4,5

Bir öndeki "benden uzun 2 kişi var" diyor, o zaman bu adam ancak 2 birim boylu olandır.

Kalan grup: 4,5

Sıradaki "benden uzun 0 diyor", o zaman bu adam 5 birim boylu..

ve son kalan 4.

4 5 2 1 3

Kodu yazmaya çalışacağım.

Düzenleme:
Kodu yazdım ama hiç eniyileme yapmaya çalışmadım, belki de çok daha kısa ve kolay yoldan yazılabilir. Örneği ve yedi kişilik başka bir grubu denedim, çalışıyor:

#include "stdio.h"
#define boyut 5
#include <conio.h>
void main(){
int giris[boyut]={0,0,2,3,2};
int musvedde[boyut];
int cikis[boyut];
int i,j=0,p=0; 
clrscr();

for(i=0;i<=boyut-1;i++){ //boy sirasina dizilmis musvedde dizisini olusturalim 1, 2, 3, 4, 5...
	musvedde[i]=i+1;
}

for(i=boyut-1;i>=0;i--){ //cikis dizisini olusturacak dongu
j=boyut-1; //siranin sonundan basliyoruz
p=0; 
	while(p<giris[i]){ // onunde giris[i] kadar kendisinden uzun olan kisiyi bulan kısım
	if(musvedde[j]!=0){ //silinmis adamları sayma
		p++; //sayilan adam sayisi
	}
	j--;
	}

	while(musvedde[j]==0) { //indis silinmis yerde kaldıysa ilk adamı bulana kadar devam et
	j--;
	}

	cikis[i]=musvedde[j]; 
	musvedde[j]=0; // bulunan adamı sil==yerine 0 yaz.

}


for(i=0;i<=boyut-1;i++){ //output
	printf("%d ",cikis[i]);
}


}

[picusta]

Güzel düsünmüssün.
Ne aradigimizin bir listesi, sonra o listeden bulduklarimizi çikartiyoruz ona göre yeniden arama yapiyoruz.
Dedigim yöntem döngüde her zaman en uzunu arama (arkadan baslayarak ilk sifir), bulduktan sonra onu çikis tablosuna kaydediyoruz ve sonra onu çikartiyoruz (0'dan -1'e düsüyor), onu çikarttigimiz için onun arkasindakiler artik bir kisi daha az görüyor, ona göre listeyi tekrar hesapliyoruz. Arkasinda 1 varsa o 0 oluyor. Sonra tekrardan en uzunu ariyoruz ve böyle sürüp gidiyor.

Asagida fonksyonu yazdim, test etmedim.
Giris dizisi soruya göre ters olmasi lazim (yoksa döngüyü tersten kurmak gerekiyor)

#define NMAX[50000]    // Tablonun maksimum uzunlugu

/*
 * BoyBul
 * Giris -> TabIn : giris dizisi, 0 endeksli ekrana en uzak oturan
 *       <- TabOut : çikis dizisi, giris dizisi ile ayni sirada
 *       -> Boyut : dizilerin uzunlugu
 * çikis <- çözüm bulunamadi ise false
 */

bool BoyBul(int *TabIn, int *TabOut , int Boyut )
{
bool Donus;       // Fonksyonun dönüs degeri
int  ii, jj,      // Döngü degiskenleri
     EnUzunAdam;  // O an aradigimiz en uzun adamin indisi

// Baslangiç
Donus = true;

// Bütün boylari tara : Boy = Boyut - ii 
for (ii = 0; ii < Boyut && Donus; ii++)
   {
   // En uzun adami bul
   for (EnUzunAdam = 0; EnUzunAdam < Boyut && TabIn[EnUzunAdam] != 0; EnUzunAdam++ );
   // Aradigimizi buldugumuzu test ediyoruz
   if (EnUzunAdam == Boyut)
      {
      Donus = false;
      }
   else
      {
      // Boyu kaydet 
      TabOut[EnUzunAdam] = Boyut - ii;
      // En uzun adami listeden çikardik, buna göre yeniden giris dizisini hesapliyoruz
      for (jj = 0; jj < EnUzunAdam-1; jj++ )
         TabIn[jj] = TabIn[jj] -1;
      }
   }
// çikis
return Donus;
}