# Rubabandiere v2

**URL:** <https://forum.olinfo.it/t/rubabandiere-v2/6278>\
**Category:** Aiuto\
**Created:** [2 Settembre 2020, 8:48pm UTC](https://forum.olinfo.it/t/rubabandiere-v2/6278 "2020-09-02T20:48:51Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![peppe17](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/p/a8b319/32.png) [@peppe17](https://forum.olinfo.it/u/peppe17)\
**Post date:** [2 Settembre 2020, 8:48pm UTC](https://forum.olinfo.it/t/rubabandiere-v2/6278/1 "2020-09-02T20:48:51Z")

</div>

Come posso migliorare?

```auto
#include <iostream>
using namespace std;

int rubabandiera(int n);

int main(){
//p e la posizione in cui il ragazzo si deve posizionare per vincere
	int n,q,p;
	cin>>q;
	for(int i=0;i<q;i++){
	cin>>n;
	p=rubabandiera(n);
	cout<<p<<"\n";
	}
}
int rubabandiera(int n){
	int i=0,c=0,p;
	bool colpito=false;
	int v[n];
	for(int j=0;j<n;j++)v[j]=1;
	while(c!=n-1){//continuo fin quando sono stati tutti colpiti tranne 1 
		if(i>=n)i=n-i;//controllo se lindice ha superato la dimensione del vettore
		if(v[i]!=0){
			p=i;
			while(colpito==false){//continuo fin quando non trovo uno da colpire
				if(++i>=n)i=n-i;
				if(v[i]!=0){
					v[i]=0;
					colpito=true;
					c++;
					}
			}
			colpito=false;
		}
		i++;
	}
	return p+1;
}

```

---

<div class="post-metadata">

**Author:** ![porcelli](https://forum.olinfo.it/user_avatar/forum.olinfo.it/porcelli/32/668_2.png) [@porcelli](https://forum.olinfo.it/u/porcelli)\
**Post date:** [2 Settembre 2020, 9:21pm UTC](https://forum.olinfo.it/t/rubabandiere-v2/6278/2 "2020-09-02T21:21:22Z")

</div>

In un secondo abbiamo un limite di complessità che si aggira sul miliardo di operazioni ovviamente questo in linea di massima , non considerando specifiche tecniche della macchina su cui stiamo sottoponendo il code; nel tuo caso peggiore , arrivi ad una complessità di 10^21 che rispetto al limite di 10^9 è un po troppo xd . pensa a come semplificare l eliminazione non più calcolandoti passo per passo se devi abbattere o no la persona, ma cercando di trovare una formula o una legge che riesca a semplificarti il calcolo della soluzione.

---

<div class="post-metadata">

**Author:** ![porcelli](https://forum.olinfo.it/user_avatar/forum.olinfo.it/porcelli/32/668_2.png) [@porcelli](https://forum.olinfo.it/u/porcelli)\
**Post date:** [2 Settembre 2020, 9:26pm UTC](https://forum.olinfo.it/t/rubabandiere-v2/6278/3 "2020-09-02T21:26:21Z")

</div>

ps: per formattare il code puoi usare questi simboli ```

```auto
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  cout<<a+b+c<<"\n";
}
```

---

<div class="post-metadata">

**Author:** ![peppe17](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/p/a8b319/32.png) [@peppe17](https://forum.olinfo.it/u/peppe17)\
**Post date:** [5 Settembre 2020, 10:38am UTC](https://forum.olinfo.it/t/rubabandiere-v2/6278/4 "2020-09-05T10:38:29Z")

</div>

come hai fatto a calcolarti 10^21?

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [5 Settembre 2020, 12:56pm UTC](https://forum.olinfo.it/t/rubabandiere-v2/6278/5 "2020-09-05T12:56:56Z")

</div>

In realtà un lower bound è O(NQ)=10^{23} , in quanto hai Q=10^5 query dove in ognuna delle quali hai almeno N=10^{18} istruzioni: `for(int j=0;j<n;j++)v[j]=1;`

La complessità effettiva è in realtà più alta di O(NQ) in quanto quella simulazione non è lineare.

In ogni caso avendo così tante query devi trovare un modo veloce ( O(logN) o O(1) ) per svolgere una singola query. Il consiglio che posso darti per questo esercizio è controllare a mano i risultati per N= 1, 2, 3, ... e cercare un eventuale pattern.