UVA - 10167 - Birthday Cake

/*You don't have to brute force A from -500 to 500 and B from -500 to 500.
You can brute force A from 0 to 500 and B from -500 to 500  as if (-500,-500) is the same as (500,500) .
*/
#include<stdio.h>
#include<string.h>
#define MAX 101

int x[MAX],y[MAX];

int ans(int A,int B,int n){
    int i,pos=0,neg=0;
    for(i=0;i<2*n;i++){
        int temp=A*x[i]+B*y[i];
        if(temp>0){
            pos++;
        }
        else if(temp<0){
            neg++;
        }else{
            return 0;
        }
    }
    if(pos==neg)
        return 1;
    return 0;
}

int main()
{
    int i,j,n;
    while(1){
        scanf("%d",&n);
        if(n==0)
            break;
        for(i=0;i<2*n;i++){
            scanf("%d %d",&x[i],&y[i]);
        }
        int temp=-1,tempA=-1,tempB=-1;
        for(i=0;i<501;i++){
            for(j=-500;j<501;j++){
                temp=ans(i,j,n);
                if(temp==1){
                    tempA=i;
                    tempB=j;
                    break;
                }
            }
            if(temp==1){
                break;
            }
        }
        printf("%d %d\n",tempA,tempB);
    }
    return 0;
}

UVA - 270 - Lining Up

#include<stdio.h>
#include<string.h>
#define MAX 701

int coolinear(int x1,int y1,int x2,int y2,int x3,int y3){
    return (y1 - y2) * (x1 - x3) == (x1 - x2) * (y1 - y3);
}

int main()
{
    int i,ic,n ,j, z, counter, points,max;
    int x[MAX], y[MAX], arr[MAX][MAX], temp[MAX] ;
    char str[150];
    gets(str);
    sscanf(str, "%d", &n);
    gets(str);
    for(ic=0;ic<n;ic++){
        if(ic>0)
            printf("\n");
        points = 0;
        while(gets(str) != NULL){
            if(str[0] == '\0')
                break;
            sscanf(str, "%d%d", &x[points], &y[points]);
            points++;
        }
        memset(arr, -1, sizeof(arr));
        max = 0;
        for(i = 0; i < points; i ++)
            for(j = i + 1; j < points; j ++)
                if(arr[i][j]){
                    counter = 0;
                    for(z = 0; z < points; z++)
                        if(coolinear(x[i],y[i],x[j],y[j],x[z],y[z]))
                            temp[counter++] = z;
                    if(counter > max)
                        max = counter;
                    int l,m;
                    for(l = 0; l < counter; l ++)
                        for(m = l + 1; m < counter; m ++){
                            arr[temp[l]][temp[m]] = 0;
                            arr[temp[m]][temp[l]] = 0;
                        }
                }
        printf("%d\n", max);
    }
    return 0;
}

UVA - 184 - Laser Lines

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
            String m="";
            LinkedList<Point> list=new  LinkedList<Point>();
            while(true){
                m=br.readLine();
                if(m.equals("0 0")){
                    break;
                }
                StringTokenizer st=new StringTokenizer(m);
                int tokens=st.countTokens()/2;
                int lastX=0,lastY=0;
                for(int j=0;j<tokens;j++){
                    if(j==tokens-1){
                        lastX=Integer.parseInt(st.nextToken());
                        lastY=Integer.parseInt(st.nextToken());
                        if(!(lastX==0&&lastY==0)){
                            list.add(new Point(lastX,lastY));
                        } 
                    }else{
                        list.add(new Point(Integer.parseInt(st.nextToken()),
                                Integer.parseInt(st.nextToken())));
                    }
                }
                if(lastX!=0||lastY!=0){
                    continue;
                }
                Point[]arr=new Point[list.size()];
                for(int i=0;i<arr.length;i++){
                    arr[i]=list.remove();
                }
                Arrays.sort(arr);
                boolean getit=false;
                boolean checked[][]=new boolean[arr.length][arr.length];
                for(int i=0;i<arr.length;i++){  
                   for(int j=i+1;j<arr.length;j++){
                       if(checked[i][j]){
                           continue;
                       }
                        LinkedList<Point> temp=new LinkedList<Point>();
                        LinkedList<Integer> zs=new LinkedList<Integer>();
                        temp.add(arr[i]);
                        temp.add(arr[j]);
                        boolean tempL[]=new boolean[arr.length];
                        for(int z=j+1;z<arr.length;z++){
                            if(checked[i][z]||checked[j][z]){
                                continue;
                            }
                            if(coolinear(arr[i],arr[j], arr[z])){
                                temp.add(arr[z]);
                                checked[i][j]=true;
                                checked[j][z]=true;
                                checked[i][z]=true;
                                zs.add(z);
                            }
                        }
                        if(temp.size()>2){
                            if(!getit){
                                 sb.append("The following lines were found: \n");
                            }
                            getit=true;
                            while(!temp.isEmpty()){
                                sb.append(temp.remove().out());
                            }
                            sb.append("\n");
                        }
                        int[]zsArr=new int[zs.size()];
                        for(int k=0;k<zsArr.length;k++){
                           zsArr[k]=zs.remove();
                        }
                        for(int k=0;k<zsArr.length;k++){
                            for(int l=k+1;l<zsArr.length;l++){
                                checked[zsArr[k]][zsArr[l]]=true;
                            }
                        }
                    }
                  
                }
                if(!getit){
                    sb.append("No lines were found\n");
                }
            }
        System.out.print(sb);
    }
  
    static boolean coolinear(Point a,Point b,Point c){
        return ((a.getY())-(b.getY()))*((a.getX())-(c.getX()))==
               ((a.getY())-(c.getY()))*((a.getX())-(b.getX()));
    }
}
class Point implements Comparable<Point> {
    private int x;
    private int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

   
    @Override
    public int compareTo(Point o) {
        if(this.x>o.getX()){
            return 1;
        }else if(this.x<o.getX()){
            return -1;
        }
        if(this.y>o.getY()){
            return 1;
        }else{
            return -1;
        }
    }
   
    public String out(){
        String ans=String.format("(%4d,%4d)", this.x,this.y);
        return ans;
    }
}

UVA - 10489 - Boxes of Chocolates

#include<stdio.h>

int main()
{

   long n,friends,boxes,k,product,sum,temp;
   scanf("%ld",&n);
   while(n--){
      scanf("%ld %ld",&friends,&boxes);
      sum=0;
      while(boxes--){
         product=1;
         scanf("%ld",&k);
         while(k--){
            scanf("%ld",&temp);
            product=(product*temp)%friends;
         }
         sum=(sum+product)%friends;
      }
      printf("%ld\n",sum);
   }
   return 0;
}

UVA - 10515 - Powers Et Al.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        int[]mods={1, 1, 4, 4, 2, 1, 1, 4, 4, 2};
        while(true){
            StringTokenizer st=new StringTokenizer(br.readLine());
            String str=st.nextToken();
            int m=Integer.parseInt(str.charAt(str.length()-1)+"");
            str=st.nextToken();
            int n;
            if(str.length()>1){
                n=Integer.parseInt(str.charAt(str.length()-2)+""+str.charAt(str.length()-1)+"");
            }else{
                n=Integer.parseInt(str.charAt(str.length()-1)+"");
            }
            if(m==0 && n==0 &&str.length()==1){
                break;
            }
            if(m==0 ||m==1 ||m==5 ||m==6){
                sb.append(m).append("\n");
            }else if(n==0){
                if(str.length()==1)
                    sb.append("1\n");
                else{
                    sb.append(modP(m, 4,mods)).append("\n");
                }
            }else{
                sb.append(modP(m, n,mods)).append("\n");
            }
        }
        System.out.print(sb);
    }
   
    static int modP(int m,int n,int[]mods){
        if(n%mods[m]>0)
            n= n%mods[m];
        else
            n=mods[m];
        int res=1;
        for (int i = 0; i < n; i++) {
            res*=m;
        }
        return res%10;
    }
}

UVA - 481 - What Goes Up

#include <vector>
#include <cstdio>

using namespace std;

void LIS(vector<int> &input, vector<int> &lis){
    vector<int> temp(input.size());
    lis.push_back(0);
    int s, e;
    for (size_t i = 1; i < input.size(); i++){
        if (input[lis.back()] < input[i]){
            temp[i] = lis.back();
            lis.push_back(i);
            continue;
        }
        s = 0;
        e = lis.size()-1;
        while (s < e){
            int m = (s + e) / 2;
            if (input[lis[m]] < input[i])
                s=m+1;
            else
                e=m;
        }
        if (input[i] < input[lis[s]]){
            if (s > 0)
                temp[i] = lis[s-1];
            lis[s] = i;
        }
    }
    for (s = lis.size(), e = lis.back(); s--; e = temp[e])
        temp[s] = e;
}


int main()
{
    int x;
    vector<int> seq;
    while(scanf("%d",&x)==1){
        if(x==22)
            break;
        seq.push_back(x);
    }
    vector<int> lis;
    LIS(seq, lis);
    printf("%d\n-\n", lis.size());
    for (unsigned int i = 0; i < lis.size(); i++)
        printf("%d\n", seq[lis[i]]);
    return 0;
}

UVA - 10409 - Die Game

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        while(true){
            int step=Integer.parseInt(br.readLine());
            if(step==0){
                break;
            }
            LinkedList<Integer> ver=new LinkedList<Integer>();
            LinkedList<Integer> hor=new LinkedList<Integer>();
            ver.add(2);
            ver.add(1);
            ver.add(5);
            ver.add(6);
            hor.add(3);
            hor.add(1);
            hor.add(4);
            for(int i=0;i<step;i++){
                String temp=br.readLine();
                if(temp.equals("east")){
                    hor.add(0,ver.removeLast());
                    ver.add(hor.removeLast());
                    ver.remove(1);
                    ver.add(1, hor.get(1));
                }
                else if(temp.equals("west")){
                    hor.add(ver.removeLast());
                    ver.add(hor.remove());
                    ver.remove(1);
                    ver.add(1, hor.get(1));
                }else if(temp.equals("north")){
                    ver.add(ver.remove());
                    hor.remove(1);
                    hor.add(1, ver.get(1));
                }else if(temp.equals("south")){
                    ver.add(0,ver.removeLast());
                    hor.remove(1);
                    hor.add(1, ver.get(1));
                }
            }
            sb.append(ver.get(1)).append("\n");
        }
        System.out.print(sb);
    }
}