Linear DataStructures: 1D Array Problems

Problems based on 1D Arrays:

1. UVa 00230 - Borrowers 

2. UVa 00394 - Mapmaker

3. UVa 00414 - Machined Surfaces 

4. UVa 00467 - Synching Signals 

5. UVa 00482 - Permutation Arrays 

6. UVa 00591 - Box of Bricks 

7. UVa 00665 - False Coin 

8. UVa 00755 - 487-3279 

9. UVa 10038 - Jolly Jumpers

10. UVa 10050 - Hartals

11. UVa 10260 - Soundex

12. UVa 10978 - Let’s Play Magic

13. UVa 11093 - Just Finish it up

14. UVa 11192 - Group Reverse

15. UVa 11222 - Only I did it

16. UVa 11340 - Newspaper

17. UVa 11496 - Musical Loop

18. UVa 11608 - No Problem

19. UVa 11850 - Alaska

20. UVa 12150 - Pole Position

21. UVa 12356 - Army Buddies *

Here is the link to the questions: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=623

Here are my solutions to selected questions:

Uva 591: Box of Bricks

Hint: Sum all the items, get the average, sum the total absolute difference of each item from the average divided by two is what you want.

int main(int argc, char const *argv[]) {
	int i=0;
	while (true) {
	i++;
	int n;
	scanf("%d", &n);
	if(n==0)
	break;
	int arr[n];
	int sum=0;
	for (size_t i = 0; i < n; i++) {
	scanf("%d", &arr[i]);
	sum += arr[i];
	}
	int average = sum/n;
	int numberofMoves = 0;
	for (size_t i = 0; i < n; i++) {
	arr[i] -= average;
	numberofMoves += abs(arr[i]);
	}
	numberofMoves= numberofMoves >>1;
	printf("Set #%d\n", i);
	printf("The minimum number of moves is %d.\n\n", numberofMoves);
	}
	return 0;
	}

Uva 11340: Newspaper

Hint: Simple. Two arrays to keep track of that character have what value, and one string is worked on.

int main()
	{
	int t,v,n;
	string s;
	cin>>t;
	while(t--){
	cin>>n;
	char c[n];
	int brr[n];
	for(int i=0;i<n;i++){
	cin>>c[i]>>brr[i];
	}
	double sum=0;
	cin>>v;
	getline(cin,s);
	for(int j=0;j<v;j++){
	getline(cin,s);
	for(int k=0;k<s.size();k++){
	for(int l=0;l<n;l++){
	if(s[k]==c[l]){
	sum+=(double)brr[l];
	}
	}
	}
	}
	printf("%.2lf",sum/100.00);
	cout<<"$"<<endl;
	}
	return 0;
	}

Uva-10038: Jolly Jumpers

Simple: You need to use 1D boolean flags to check [1....n-1]. 

int main(int argc, char const *argv[]) {
	int n;
	while (scanf("%d", &n)==1) {
	int arr[n];// [] [] [] []
	for(int i=0;i<n;i++){
	scanf("%d", &arr[i]);
	}
	//arr -> 1 4 2 3
	if(n==1){
	printf("%s\n", "Jolly");
	continue;
	}
	bool is[n] = {false}; // false false false false
	bool success = true;
	for (size_t i = 0; i < n-1; i++) {
	int temp = abs(arr[i+1] - arr[i]);
	if(temp<n&&temp>=1)
	is[temp] = true;
	else{
	success =false;
	break;
	}
	}
	// 3 2 1
	if(!success){
	printf("%s\n", "Not jolly");
	continue;
	}
	for(int i=1;i<n;i++){
	bool temp = is[i];
	if(temp==false){
	success = false;
	break;
	}
	}
	if(success)
	printf("%s\n", "Jolly");
	else
	printf("%s\n", "Not jolly");
	}
	return 0;
	}

Uva 482: Permutation Arrays

Hint: Use the substr and reverse stl functions in c++.

int main(int argc, char const *argv[]) {
	int N;
	while (scanf("%d", &N)==1&&N) {
	string str;
	cin>>str;
	string arr[N];
	int len = str.length()/N;
	for(int i=0;i<N;i++){
	arr[i] = str.substr(i*len, len);
	}
	for (size_t i = 0; i < N; i++) {
	reverse(arr[i].begin(), arr[i].end());
	}
	string output = "";
	for (size_t i = 0; i < N; i++) {
	output += arr[i];
	}
	cout<<output<<endl;
	}
	return 0;
	}

Uva 11608: No problem:

Simple: One mistake that I was making is, we are not using problems that once have been used. We don't repeat problems.

int main(int argc, char const *argv[]) {
	int S;
	int i=1;
	int arr[13];
	int brr[13];
	while (scanf("%d", &S)) {
	if(S<0)
	break;
	arr[0] = S;
	for (size_t i = 1; i <= 12; i++) {
	scanf("%d", &arr[i]);
	}
	printf("Case %d:\n", i);
	for (size_t i = 0; i < 12; i++) {
	scanf("%d", &brr[i]);
	}
	for (size_t i = 0; i < 12; i++) {
	if(arr[i]-brr[i]>=0){
	arr[i+1] = arr[i+1] + arr[i]-brr[i];
	printf("%s\n", "No problem! :D");
	}else{
	arr[i+1] += arr[i];
	printf("%s\n", "No problem. :(");
	}
	}
	i++;
	}
	return 0;
	}