[白準C++14891ギア


質問する


合計8個のギアの4個が一列に並んでいて、下図のようになっています.また、鋸歯はN極またはS極のいずれかを表す.ギアはナンバー、一番左のギアは1番、右のギアは2番、右のギアは3番、一番右のギアは4番です.

このとき、ギアは常にK回回転します.歯車の回転は一節に準ずる.回転は時計回りと反時計回りがあり、下図のように回転します.


ギアを回転させるには、回転するギアと回転の方向を決めなければなりません.ギアが回転すると、互いに接触する極に応じて隣のギアを回転させてもよいし、回転させなくてもよい.ギアAを回転させる際に、その隣のギアBと互いに接触するギアの極性が異なると、BはAの回転方向とは逆になる.例えば、以下の状況を見てみましょう.

2つのギアの噛み合い部分は緑色の破線で縛られた部分です.ここで、ギア3ポチを反時計回りに回すと、ギア4ポチが時計回りに回ります.2番ギアの噛み合い部分がS極なので回転せず、1番ギアは2番が回転していないので回転しません.したがって、下図のような形状が作成されます.

上記の状態では、1番ギアを時計回りに回転させ、2番ギアを反時計回りに回転させ、2番ギアを回転させるので、3番も同時に時計回りに回転させます.4番は3番回転ですが、接触が極めて同じなので回転しません.このため、次の状態になります.

ギアの初期状態とギアの回転方法を指定する場合は、最終ギアの状態を求めるプログラムを作成します.

入力


1行目は1番ギアの状態、2行目は2番ギアの状態、3行目は3番ギアの状態、4行目は4番ギアの状態を示します.状態は8個の整数からなり,12時方向から時計回りに与えられる.Nは極めて0,Sは極めて1である.
5行目は回転数K(1≦K≦100)を与える.次のK行は順番に回転の方法を与えます.各方法は2つの整数からなり、第1の整数は回転歯車の番号であり、第2の整数は方向である.方向が1の場合は時計回り、-1の場合は反時計回りです.

しゅつりょく


合計K回回転した後、4個のギアの積分の和を出力します.点数は次のように計算されます.
  • 1号ギヤ12点方向N極0点、S極1点
  • 番歯車12点方向N極0点、S極2点
  • 3号ギヤ12点方向N極0点、S極4点
  • 4号ギヤ12点方向N極0点、S極8点
  • https://www.acmicpc.net/problem/14891

    Vector VS Dequeコンセプトアレンジ



    Vectorは、要素を追加するたびにメモリを再割り当てし、メモリをコピーします.
    dequeは、メモリが不足している場合にのみ、新しいメモリブロックのサイズを割り当てます.(メモリXのコピーが必要)
    したがって、挿入削除が頻繁に行われたり、回転が必要になったりすると、deque以外のvectorのパフォーマンスが向上します.

    解答(エラー改善プロセス)


    最初はQで回転を実現して、それからねじって、方向を間違えて、何時間も無駄にしました.
    4つの歯車がそれぞれ噛み合う3つの位置が回転可能なgaps[3]配列であるかどうかを調べる.
    2個2個2個2個2個(同時に回転可能かどうかを決める場合)=8
    これは縮んで使って、ねじってまた何時間も飛んだ.
    その後、データ構造をdequeに変更し、dequeのfrontを12時方向にし、最初にbackからデータを入れます.
    デックの構造は、ここでは、後に要素を加えると、一つずつ前に進みます.

    逆に、前に置くと、要素が後ろに押されます.
    中央の要素を削除し、前後のグループのより少ないグループを大きなグループに引き寄せます.
    作成したコードは繰り返しですが、読みやすさは良いと思います.
    #define _CRT_SECURE_NO_WARNINGS 
    #include <bits/stdc++.h>
    using namespace std;
    deque<int> gear[4];
    int K = 0;
    vector<pair<int, int>> rot; //회전시킨방법들
    bool gaps[3] = { false, };	//3구간이 각각 돌아가는가?
    int cnt = 0;
    
    void gear_r(int gearNum, int r);
    int gear_p(int gearNum, bool right);
    void cw(int gearNum);
    void ccw(int gearNum);
    void rotate(int n, int r);
    void machine();
    void printAll();
    
    void cw(int gearNum) { //시계방향으로 회전
    	int temp = gear[gearNum].back();
    	gear[gearNum].pop_back();
    	gear[gearNum].push_front(temp);
    }
    
    void ccw(int gearNum) { //반시계방향으로 회전
    	int temp = gear[gearNum].front();
    	gear[gearNum].pop_front();
    	gear[gearNum].push_back(temp);
    }
    
    //기어의 오른쪽, 왼쪽(맞닿는 부분)을 출력한다.
    int gear_p(int gearNum, bool right) { 
    	int res = 0;
    	if (right) { //오른쪽 정보를출력
    		//3번째 즉 2번인덱스값
    		res = gear[gearNum][2];
    	}else{ //왼쪽정보를 출력
    		//7번째, 즉 6번인덱스값
    		res = gear[gearNum][6];
    	}
    	return res;
    }
    
    void rotate(int n, int r) { //n번기어를 r방향으로 돌림
    	for (int i = 0; i < 3; i++) //초기화
    		gaps[i] = false;
    	//세 구간에서 회전이 일어나는가
    	if (gear_p(0, true) != gear_p(1, false)) gaps[0] = true;
    	if (gear_p(1, true) != gear_p(2, false)) gaps[1] = true;
    	if (gear_p(2, true) != gear_p(3, false)) gaps[2] = true;
    
    	//n에따라 기어상태들을 변화
    	if (n == 1) {
    		if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			gear_r(2, r * -1);
    			gear_r(3, r);
    			gear_r(4, r * -1);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			gear_r(2, r * -1);
    			gear_r(3, r);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			gear_r(2, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			//pass
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			//pass
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			gear_r(2, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			//pass
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			//pass
    		}
    		gear_r(1, r);
    	}
    	else if (n == 2) {
    		if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			gear_r(1, r * -1);
    			gear_r(3, r * -1);
    			gear_r(4, r);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			gear_r(1, r * -1);
    			gear_r(3, r * -1);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			gear_r(1, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			gear_r(3, r * -1);
    			gear_r(4, r);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			//pass
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			gear_r(1, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			gear_r(3, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			//pass
    		}
    		gear_r(2, r);
    	}
    	else if (n == 3) {
    		if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			gear_r(1, r);
    			gear_r(2, r * -1);
    			gear_r(4, r * -1);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			gear_r(1, r);
    			gear_r(2, r * -1);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			gear_r(4, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			gear_r(2, r * -1);
    			gear_r(4, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			gear_r(4, r * -1);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			//pass
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			gear_r(2, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			//pass
    		}
    		gear_r(3, r);
    	}
    	else if (n == 4) {
    		if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			gear_r(1, r * -1);
    			gear_r(2, r);
    			gear_r(3, r * -1);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			//pass
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			gear_r(3, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == true) {
    			gear_r(2, r);
    			gear_r(3, r * -1);
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == true) {
    			gear_r(3, r * -1);
    		}
    		else if (gaps[0] == true &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			//pass
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == true &&
    			gaps[2] == false) {
    			//pass
    		}
    		else if (gaps[0] == false &&
    			gaps[1] == false &&
    			gaps[2] == false) {
    			//pass
    		}
    		gear_r(4, r);
    	}
    }
    
    void gear_r(int gearNum, int r) {
    	int num = gearNum - 1;
    	if (num < 0 || num > 3) //기어범위가 잘못된경우
    		return;
    
    	//기어를 해당방향으로돌림
    	if (r == 1) {
    		//시계방향
    		cw(num);
    	}
    	else if (r == -1) {
    		//반시계방향
    		ccw(num);
    	}
    }
    
    void machine() { //회전시킨 정보를 모두 실행
    	for (int i = 0; i < K; i++) {
    		//i번째 요소(회전시킨기어, 방향)를 꺼냄
    		int n = rot[i].first;
    		int r = rot[i].second;
    		rotate(n, r);
    	}
    }
    
    void printAll() {
    	cnt++;
    	int res = 0;
    	res += 1 * gear[0].front();
    	res += 2 * gear[1].front();
    	res += 4 * gear[2].front();
    	res += 8 * gear[3].front();
    	
    	printf("%d\n", res);
    }
    
    int main(void) {
    	int temp=0, temp2=0;
    	for (int i = 0; i < 4; i++) {
    		for (int j = 0; j < 8; j++) { //기어상태 저장
    			scanf("%1d", &temp);
    			gear[i].push_back(temp); //거꾸로넣어야 처음원소가 front가됨
    		}
    	}
    	scanf("%d", &K);
    	for (int i = 0; i < K; i++) { //회전시킨정보를 저장
    		scanf("%d%d", &temp, &temp2);
    		//회전시킨기어번호, 방향 
    		rot.push_back({ temp, temp2 });
    	}
    	machine();
    	printAll();
    
    	return 0;
    }
    約300行のコード.再帰構造を利用すれば、もっと簡単に書くことができるはずです.