codeforces 245C Game with Coins
4559 단어 탐욕스럽다
Polycarpus and Vasily move in turns. Polycarpus moves first. During a move a player is allowed to choose a positive integer x(2·x + 1 ≤ n) and take a coin from each chest with numbers x, 2·x, 2·x + 1. It may turn out that some chest has no coins, in this case the player doesn’t take a coin from this chest. The game finishes when all chests get emptied.
Polycarpus isn’t a greedy scrooge. Polycarpys is a lazy slob. So he wonders in what minimum number of moves the game can finish. Help Polycarpus, determine the minimum number of moves in which the game can finish. Note that Polycarpus counts not only his moves, he also counts Vasily’s moves.
Input The first line contains a single integer n(1 ≤ n ≤ 100) — the number of chests with coins. The second line contains a sequence of space-separated integers: a1, a2, …, an(1 ≤ ai ≤ 1000), where ai is the number of coins in the chest number i at the beginning of the game.
Output Print a single integer — the minimum number of moves needed to finish the game. If no sequence of turns leads to finishing the game, print -1.
Sample Input Input 1 1 Output -1 Input 3 1 2 3 Output 3 Hint In the first test case there isn’t a single move that can be made. That’s why the players won’t be able to empty the chests.
In the second sample there is only one possible move x = 1. This move should be repeated at least 3 times to empty the third chest.
제목: 번호 1-n의 상자 한 무더기, 매번 세 개의 상자를 찾습니다. 번호는 n, 2*n, 2*n-1입니다. 그중의 은화 한 개를 꺼내서 최소한 몇 번을 찾으면 안에 있는 돈을 다 찾을 수 있는지 물어보세요.상자가 찾을 수 없을 때(예를 들어 n이 3보다 작거나 짝수) 마이너스 1을 출력한다.
방법: 욕심 전략.먼 곳의 상자를 찾을 기회가 가장 적고 한 번일 수도 있으며, 먼 곳의 상자를 갈 때 가까운 상자도 수익을 따라갈 수 있기 때문에 n번째 상자에서 역추한다.
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
int main()
{
int n;
int a[1005];
while(scanf("%d",&n)==1)
{
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
if(n<3||n%2==0) printf("-1
");
else
{
int cnt=0;
for(i=n;i>=1;i--)
{
while(a[i]>0)
{
a[i]--;
if(i%2==1) a[i-1]--; //2*i+1
else a[i+1]--; //2*i
a[i/2]--;
cnt++;
}
}
printf("%d
",cnt);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[noip2013] 꽃장인DP||욕심화공의 동채에 한 줄의 꽃을 심었는데, 꽃마다 모두 자신의 높이가 있다.꽃은 자랄수록 커지고 비좁아진다.동동은 이 줄의 일부 꽃을 옮기고 나머지는 제자리에 남겨 남은 꽃이 자랄 수 있는 공간을 마련하기로 했다. 또한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.