2007C の変更点

https://densanken.com/wiki/index.php?2007C

[ トップ ]   [ 編集 | 差分 | バックアップ | 添付 | リロード ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ | ログイン ]

• 追加された行はこの色です。
• 削除された行はこの色です。
• 2007C へ行く。
• 2007C の差分を削除

---

[[07年度-ACM-ICPC国内予選]]

***2007C [#p73b9dad]
-''Blue Screenの解答''

回答者：[[七星(PLOW)]]&br;
所要時間：１時間&br;
予選時：クリア

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <math.h>
 #include <conio.h>
 class CCake
 {
 public:
	CCake();
	void Cut(int s, CCake* pNext);
	int w;
	int h;
 };
 CCake::CCake()
 {
	memset(this, 0, sizeof(CCake));
 }
 int comp(const void* p1, const void* p2)
 {
	CCake* pC1 = (CCake*)p1;
	CCake* pC2 = (CCake*)p2;
	return ((pC1->w * pC1->h) - (pC2->w * pC2->h));
 }
 void CCake::Cut(int s, CCake* pNext)
 {
	bool bo;
	bo = true;
	while(1)
	{
		if(bo)//横
		{
 			if(w > s)
			{
				pNext->w = w - s;
				pNext->h = h;
				w = s;
				break;
			}
			else
			{
				s -= w;
				bo = false;
			}
		}
		else//縦
		{
			if(h > s)
			{
				pNext->w = w;
				pNext->h = h - s;
				h = s;
				break;
			}
			else
			{
				s -= h;
				bo = true;
			}
		}
	}
 }
 int main()
 {
	//ファイル処理-----------------
	char FileName[256];
	printf("ファイル名を入れて〜");
	scanf("%256s", FileName);
	FILE* fpIn = fopen(FileName, "r");
	FILE* fpOut = fopen("outputC.txt", "w");
	//-----------------------------
	int cut, w, h, p, s;
	while(1)
	{
		fscanf(fpIn, "%d %d %d", &cut, &w, &h);
		if(cut == 0&& w == 0&& h == 0)
		{
			break;
		}
		CCake* pCake;
		CCake buf;
		pCake = new CCake [cut + 1];
		pCake->w = w;
		pCake->h = h;
		for(int i = 0;i < cut;i++)
		{
			fscanf(fpIn, "%d %d", &p, &s);
			pCake[p - 1].Cut(s, &pCake[i + 1]);
			memcpy(&buf, &pCake[p - 1], sizeof(CCake));
			for(int k = p;k < i + 1;k++)
			{
				memcpy(&pCake[k - 1], &pCake[k], sizeof(CCake));
			}
			if((buf.h * buf.w) > (pCake[i + 1].h * pCake[i + 1].w))
			{
				memcpy(&pCake[i], &pCake[i + 1], sizeof(CCake));
				memcpy(&pCake[i + 1], &buf, sizeof(CCake));
			}
			else
			{
				memcpy(&pCake[i], &buf, sizeof(CCake));
			}
		}
		qsort((void*)pCake, cut + 1, sizeof(CCake), comp);
		for(int i = 0;i < cut;i++)
		{
			fprintf(fpOut,"%d ", pCake[i].h * pCake[i].w);
		}
		fprintf(fpOut,"%d", pCake[cut].h * pCake[cut].w);
		fprintf(fpOut,"\n");
		delete [] pCake;
	}
	//終了処理---------------------
	fclose(fpOut);
	printf("終了！");
	getch();
	return 0;
 }

--解説&br;
ケーキの１ピースのクラスCCakeを配列で確保しメンバ関数Cutで切り分ける処理を行った&br;
最終的なCCakeの数は(切り分ける回数+1)になるのでCCakeはこれに必要な分のみ動的に確保した。&br;
Cutを呼び出す毎にその後ろの配列の前詰めを行い。&br;
さらに新しくできたピースを面積を比較して整列してから最後尾に代入した。&br;
&br;
すべての切り分け作業を終えた後にqsortを用いてクイックソートを行い面積順に並べ替えてから出力した。

-''include studioの解答''

予選時：未回答&br;
回答者：ほへい&br;
所要時間：２時間強&br;
&br;
プログラムを差し替えようか悩んでたんですが、&br;
変えても大して問題にはならないかな、と思ったので差し替えました。&br;
&br;
どっちにしてもデータセットは一瞬で終わります。&br;
インクルードしたのにクイックソートを自前で作ってる辺りなんだかなって感じです。&br;

 #include <stdio.h>
 #include <stdlib.h>
 #define UNKNOWN -1;
 
 int num_cutting;
 
 typedef struct __Cake {
   int width, height;
    int answer;
   struct __Cake *prev, *next;
 } Cake;
 
 Cake start_cake, end_cake;
 
 typedef struct {
   int cut_index;
   int length;
 } Cutting;
 Cutting cuttings[100];
 
 FILE *fp_in, *fp_out;
 static char *f_source = "C_in.txt";
 static char *f_answer = "C_out.txt";
 
 void getAnswer(void);
 void setCutting(void);
 void cutCake(int index);
 void calc(void);
 void sort(Cake *start);
 void push(Cake *append);
 void initStack(void);
 void deleteCake(Cake *del_cake);
 void swap(Cake*, Cake*);
 
 int main(void)
 {
    fp_in = fopen(f_source, "r");
    fp_out = fopen(f_answer, "w");
    start_cake.next = &end_cake;
    end_cake.prev = &start_cake;
    
    while (1) {
        Cake *cake = (Cake*)malloc(sizeof(Cake));
        initStack();
        push(cake);
        fscanf(fp_in, "%d %d %d", &num_cutting, &cake->width, &cake->height);
        if(num_cutting == 0 && cake->width == 0 && cake->height == 0) break;
       
        setCutting();
       
        getAnswer();
   }
   fclose(fp_in);
   fclose(fp_out);
   
   return 0;
 }
 
 
 void push(Cake *append)
 {
    append->answer = UNKNOWN;
    append->next = &end_cake;
    append->prev = end_cake.prev;
 
    (append->prev)->next = append;
    end_cake.prev = append;
 }
 
 
 void deleteCake(Cake *del_cake)
 {
    del_cake->prev->next = del_cake->next;
    del_cake->next->prev = del_cake->prev;
    free(del_cake);
 }
 
 
 void initStack()
 {
    Cake *temp = start_cake.next;
    while(temp != &end_cake) {
        Cake *del_cake = temp;
        temp = temp->next;
        deleteCake(del_cake);
    }
    start_cake.answer = UNKNOWN;
    end_cake.answer = UNKNOWN;
    start_cake.next = &end_cake;
    end_cake.prev = &start_cake;
 } 
 
 
 void setCutting()
 {
   int i;
   for(i = 0; i < num_cutting; i++) {
       fscanf(fp_in, "%d %d", &cuttings[i].cut_index, &cuttings[i].length);
   }
 }
 
 
 void getAnswer()
 {
    int i;
    Cake *temp_cake;
    for( i = 0; i < num_cutting; i++) {
        cutCake(i);
    }
    
    calc();
    
    temp_cake = start_cake.next;
    while(temp_cake != end_cake.prev) {
        fprintf(fp_out, "%d ", temp_cake->answer);
        temp_cake = temp_cake->next;
    }
    fprintf(fp_out, "%d\n", temp_cake->answer);
 }
 
 
 void cutCake(int index) {
    int temp;
    int count = 0, temp_len;
    Cake *new_small_cake = (Cake*)malloc(sizeof(Cake));
    Cake *new_big_cake = (Cake*)malloc(sizeof(Cake));
    Cake *temp_cake;
    
    temp_cake = start_cake.next;
    while(1) {
        count++;
        if(count == cuttings[index].cut_index) break;
        temp_cake = temp_cake->next;
    }

 
    
    *new_small_cake = *temp_cake;
    *new_big_cake = *temp_cake;
    
    deleteCake(temp_cake);
    
    temp_len = cuttings[index].length % (new_small_cake->width + new_small_cake->height);
   
   if(temp_len < new_small_cake->width) {
       temp = new_small_cake->width - temp_len;
       if(temp > temp_len) {
           new_small_cake->width = temp_len;
           new_big_cake->width = temp;
       }
       else {
           new_small_cake->width = temp;
           new_big_cake->width = temp_len;
       }
   }
   else {
       temp = temp_len - new_small_cake->width;
       if(temp > new_small_cake->height - temp) {
           new_small_cake->height -= temp;
           new_big_cake->height = temp;
       }
       else {
           new_big_cake->height -= temp;
           new_small_cake->height = temp;
       }
   }
    push(new_small_cake);
    push(new_big_cake);
 }
 
   
 void calc()
 {
    Cake *temp = start_cake.next;
    while(temp != &end_cake) {
        temp->answer = temp->width * temp->height;
        sort(temp);
        temp = temp->next;
   }
 }
 
 
 void swap(Cake *cake_early, Cake *cake_late)
 {
    Cake *temp = cake_early->prev;
    
    cake_early->next = cake_late->next;
    cake_early->prev = cake_late;
    cake_late->next->prev = cake_early;
    
    cake_late->next = cake_early;
    cake_late->prev = temp;
    cake_late->prev->next = cake_late;
 }
 
 
 void sort(Cake *sort_cake)
 {
    if( (sort_cake->prev)->answer > sort_cake->answer) {
        swap(sort_cake->prev, sort_cake);
        sort(sort_cake);
    }
 }

・解説&br;
考え方は七星先輩とほぼ同じ…はずです。&br;
詰め替えが無い代わりに、カットするケーキを探すのにループを使わないといけない構造です。&br;
ちゃんと勉強できていれば、このようなプログラムになることを意図していました。&br;
&br;

       

Site admin: CCS

PukiWiki 1.5.1 © 2001-2016 PukiWiki Development Team. Powered by PHP 7.0.33-0ubuntu0.16.04.3. HTML convert time: 0.003 sec.