Tävlingsprogrammering/Uppgifter/Chokladkartongen

Chokladkartongen

Bosse tycker om choklad. Han har därför alltid en öppnad chokladkartong i skafferiet. När den tar slut köper han i hemlighet en ny och låtsas som ingenting. Bosses fru, som är misstänksam av naturen, förundras över att den där kartongen aldrig tar slut. Därför börjar hon då och då räkna antalet chokladbitar som är kvar. Skriv ett program som, givet hennes observationer, beräknar det minsta antalet nya kartonger Bosse kan ha köpt under perioden.

Indata

På första raden står ett heltal N ≤ 100, antal observationer. Därefter följer en rad med N heltal, antalet chokladbitar i asken (mellan 1 och 100) vid varje observation, i den ordning de görs.

Utdata

Programmet ska skriva ut en rad med ett heltal: det minsta antal nya kartonger Bosse bevisligen måste ha köpt under perioden.

Exempel: Indata

10
17 15 16 16 18 17 14 12 13 9

Exempel: Utdata

3

Lösning

Det är bara att räkna hur många gånger ett tal i input-datan är större än det precis innan.

#include <iostream>
using namespace std;
 
int main(){
	int antal_observationer;
	cin >> antal_observationer;
	int antal = 0;
	int last = 100;
	for (int i=0; i<antal_observationer; i++){
		int tmp;
		cin >> tmp;
		if (tmp > last)
			antal++;
		last = tmp;
	}
	cout << antal << endl;
	return 0;
}

Är man extra cool skriver man i x86_64 assembler:

	.section .rodata.str1.1,"aMS",@progbits,1
.L_FORMAT_INT:
	.string "%d"
.L_FORMAT_INT_NEWLINE:
	.string "%d\n"
	.text
	.globl main
	.type main,@function
main:
	pushq	%rbx
	pushq	%r13
	pushq	%r14
	pushq	%r15
	subq	$8, %rsp

	movl	$.L_FORMAT_INT, %edi
	xorl	%eax, %eax
	leaq	(%rsp), %rsi
	call	scanf
	movl	(%rsp), %ebx	#antal_observationer
	
	xorl	%r13d, %r13d	#antal
	movl	$100, %r14d	#last

	xorl	%r15d, %r15d	#i
.L_FOR_PRETEST:
	cmpl	%ebx, %r15d
	je	.L_DONE
.L_FOR:
	movl	$.L_FORMAT_INT, %edi
	xorl	%eax, %eax
	leaq	(%rsp), %rsi
	call	scanf
	movl	(%rsp), %eax
	xorl	%ecx, %ecx
	cmpl	%r14d, %eax
	setg	%cl
	addl	%ecx, %r13d
	movl	%eax, %r14d
	addl	$1, %r15d
	cmpl	%ebx, %r15d
	jne	.L_FOR
	
.L_DONE:
	xorl	%eax, %eax
	movl	%r13d, %esi
	movl	$.L_FORMAT_INT_NEWLINE, %edi
	call	printf
	
	addq	$8, %rsp
	popq	%r15
	popq	%r14
	popq	%r13
	popq	%rbx
	xorl	%eax, %eax
	ret
	.size	main, .-main

Och om man är coolare än cool så skriver man i DSP-språket som introduceras några uppgifter senare (av Anton Fors Hurdén):

CONST 1 1
INPUT 0
INPUT 3
SUB 1 0
CONST 0 2
ADD 3 2
INPUT 3
ADD 3 4
SUB 1 2
SUB 1 4
JNZ 2 15
ADD 1 5
JNZ 4 14
SUB 1 5
CONST 0 4
JNZ 4 8
SUB 1 0
JNZ 0 4
OUTPUT 5
HALT