[C]白駿1644小数の連合

1315 ワード
Algorhtim two pointer テキストリンク
https://www.acmicpc.net/problem/1644

質問する


1つ以上の連続する少数の和が表すことができる自然数がある.いくつかの自然数の例を挙げると以下のようになります.
  • 3:3(一種)
  • 41:2+3+5+7+11+13=11+13+17=41(3種)
  • 53:5+7+11+13+17=53(両方)
    • しかし、いくつかの自然数は連続的な少数の和で表すことができず、20は一例である.7+13を計算すると20ですが、7と13は連続していないので適切な表現ではありません.また、小数は1回の加算にしか使用できないため、3+5+7のような表現にも適していない.
    自然数が与えられた場合、連続する小数の和で自然数を表すことができる場合は、プログラムを作成して解きます.
    送信15437正解率42%

    コード#コード#

    #include <stdio.h>
#inclue <stdlib.h>

int main(void) {
	int prime[25] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
	int n = 0;
	scanf("%d", &n);


	int cnt = 0, sum = 0;
	int left = 0, right = 0;
	while (right <= 25) {
		if (sum >= n) {
			sum -= prime[left];
			left++;
		}
		else {
			right++;
			sum += prime[right];
		}

		if (sum == n)
			cnt++;
	}
	
	printf("%d", cnt);


}
    [TIL] Day-20
    せいためんたい