2007C †
回答者:七星(PLOW) #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; }
予選時:未回答 #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); } } ・解説 |