列表

详情

NC25002. [USACO 2008 Ope S]Roads Around The Farm

描述

Farmer John's cows have taken an interest in exploring the territory around the farm. Initially, all N (1 <= N <= 1,000,000,000) cows commence traveling down a road in one big group. Upon encountering a fork in the road, the group sometimes chooses to break into two smaller (nonempty) groups with each group continuing down one of the roads. When one of those groups arrives at another fork, it might split again, and so on.
The cows have crafted a peculiar way of splitting: if they can split into two groups such that the sizes of the groups differ by exactly K (1 <= K <= 1000), then they will split in that way; otherwise, they stop exploring and just start grazing peacefully.
Assuming that there will always be new forks in the road, compute the final number of groups of peacefully grazing cows.

输入描述

* Line 1: Two space-separated integers: N and K

输出描述

* Line 1: A single integer representing the number of groups of grazing cows

示例1

输入: 

6 2

输出: 

3

说明:

There are 3 final groups (with 2, 1, and 3 cows in them).
6
/ \
2 4
/ \
1 3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 408K, 提交时间: 2022-01-17 13:02:40 

#include <bits/stdc++.h>
using namespace std;
int n,k;
int f(int n)
{
    if((n+k)%2||n<=k) return 1;
    int x;
    return f(x=(n+k)/2)+f(n-x);
}
int main()
{
    cin>>n>>k;
    cout<<f(n);
    return 0;
}

上一题

© 2024 nowcoder.com