[伯俊C+]20164奇数独石

質問する

偶数と奇数では、浩錫は頭文字が同じ奇数が好きだ.車を運転しているホソクは、前の車のナンバープレートが単数でいっぱいになったとき、かわいいと思った.電話番号も単数しかないと思います.こうして奇数に迷い込んだ浩錫は、一連の数N演算を通じて、出現した数字の中でできるだけ多くの奇数を見たいと思っている.
1つの数を指定すると、スズは1回の演算で以下のステップを経ます.
数字の各桁数に奇数を紙に書く.
一桁数えたら、何もできずに終わります.
2桁まで数えると、2つに分けて和を求め、新しい数とします.
3桁以上になると、任意の位置から切り離して3つの数に分け、3つの数を加算した値を新しい数とします.
胡石は演算が終わった瞬間、紙の数字を合わせた.こうして最終的に得られる数を最終値と呼びましょう.例えば、最初の数は82019です.では、以下のように分割すると5個の奇数が見られるため、最終値は5となる.

最初はスズが自分が持っている数がNだと言ったとき、創造できる最終値の中で最高値と最低値を見つけた.

入力

最初の行は号石が最初に持っていた数Nを与えた.

しゅつりょく

最初の行では、号石が生成できる最終値の最上位値と最上位値を順番にスペースで区切って出力します.
https://www.acmicpc.net/problem/20164

に答える

さいきこうぞう

無条件終了条件は、1つのコードブロックで処理される.

の値を計算するプロセスがあり、複雑であれば、できるだけグローバル変数で値を計算します.
例えば、あるベクトルのアドレスを取得し、そのベクトルに格納する.

この2点を覚えておけば、コードを書くのは難しくありません.
ハサミで切ると、いつか1桁になります.
では、このときコードを書き、問題の条件を終わらせます.
数値と文字列を計算する必要があるため、必要に応じて変換プロセスを関数に設定できます.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int N, max=0, min=0x7fffffff;

int findOddCnt(char* c, int size) {
	int odd = 0;
	for (int i = 0; i < size; i++)
		if ((c[i] - '0') % 2 != 0) odd++;
	return odd;
}

//최솟값을 구함
void func(int n, int cnt) {
	int size = 1, _ = n, n2, odd = 0; 
	while (_ / 10 != 0) { //자릿수구하기
		size++;
		_ /= 10;
	}
	char c[10];
	sprintf(c, "%d", n); //문자열로 변환
	//1단계 : 각자리 숫자중 홀수 갯수를 저장
	odd += findOddCnt(c, size);

	//2단계 : 한자리면 종료 : 유일한 종료조건.
	//이곳에서 모든 최대 최소 연산이 이루어짐
	if (size == 1) {
		if (max < cnt + odd) max = cnt + odd;
		if (min > cnt + odd) min = cnt + odd;
		return;
	}

	//3단계 : 두자리면
	if (size == 2)
		func((c[0] - '0') + (c[1] - '0'), cnt + odd);

	//4단계 세자리이상이면
	if (size >= 3) {
		for (int i = 1; i < size - 1; i++) {
			for (int j = i + 1; j < size; j++) {
				int s1=0, s2=0, s3=0;
				char c1[10] = {'\0',}, c2[10] = { '\0', }, c3[10] = { '\0', };
				//3등분으로 자름
				for (int k = 0; k < i; k++) { 
					c1[s1] = c[k];
					s1++;
				}
				for (int k = i; k < j; k++) {
					c2[s2] = c[k];
					s2++;
				}
				for (int k = j; k < size; k++) {
					c3[s3] = c[k];
					s3++;
				}
				//정수로 변환
				n2 = atoi(c1) + atoi(c2) + atoi(c3);

				func(n2, cnt + odd);
			}
		}
	}
}

int main(void) {
	scanf("%d", &N);

	func(N, 0);
	printf("%d %d", min, max);

	return 0;
}