Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2014
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.43 KB | None | 0 0
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.*;
  4.  
  5.  
  6. public class J {
  7.  
  8.     long gcd(long x,long y){
  9.         if(x==0)return y;
  10.         return gcd(y%x,x);
  11.     }
  12.  
  13.     void solve() throws IOException {
  14.         int t=nextInt();
  15.         while(t-->0){
  16.             int n=nextInt();
  17.             long c1=0;
  18.             long c2=0;
  19.             int[] count=new int[n];
  20.             int[] type=new int[n];
  21.             for(int i=0;i<n;i++){
  22.                 count[i]=nextInt();
  23.                 char c=nextToken().charAt(0);
  24.                 if(c=='B')type[i]=1;
  25.                 else type[i]=0;
  26.                 if(type[i]==0)c1+=count[i];
  27.                 else c2+=count[i];
  28.             }
  29.             if(c1==0||c2==0){
  30.                 out.println(c1+c2);
  31.                 continue;
  32.             }
  33.             long g=gcd(c1,c2);
  34.             c1/=g;
  35.             c2/=g;
  36.             long x1=0;
  37.             long x2=0;
  38.  
  39.             if(type[0]==0)x1+=count[0];
  40.             else x2+=count[0];
  41.             int ans=0;
  42.             for(int i=1;i<n;i++){
  43.                 if(type[i]==0){
  44.                     long q=x2*c1;
  45.                     if(q%c2==0){
  46.                         long y=q/c2;
  47.                         if(y<=x1){
  48.                             x1+=count[i];
  49.                             continue;
  50.                         }
  51.                         if(y>x1+count[i]){
  52.                             x1+=count[i];
  53.                             continue;
  54.                         }
  55.                         //long z=y-x1;
  56.                         x1+=count[i];
  57.                         //x2+=z;
  58.                         ans++;
  59.                     }
  60.                     else x1+=count[i];
  61.                 }
  62.                 else{
  63.                     long q=x1*c2;
  64.                     if(q%c1==0){
  65.                         long y=q/c1;
  66.                         if(y<=x2){
  67.                             x2+=count[i];
  68.                             continue;
  69.                         }
  70.                         if(y>x2+count[i]){
  71.                             x2+=count[i];
  72.                             continue;
  73.                         }
  74.                         //long z=y-x2;
  75.                         //x2=y;
  76.                         //x1+=z;
  77.                         x2+=count[i];
  78.                         ans++;
  79.                     }
  80.                     else
  81.                         x2+=count[i];
  82.                 }
  83.             }
  84.             out.println(ans);
  85.         }
  86.     }
  87.  
  88.     public static void main(String[] args) throws IOException {
  89.         new J().run();
  90.     }
  91.  
  92.     void run() throws IOException {
  93.         reader = new BufferedReader(new InputStreamReader(System.in));
  94.         tokenizer = null;
  95.         out = new PrintWriter(new OutputStreamWriter(System.out));
  96.         solve();
  97.         reader.close();
  98.         out.flush();
  99.  
  100.     }
  101.  
  102.     BufferedReader reader;
  103.     StringTokenizer tokenizer;
  104.     PrintWriter out;
  105.  
  106.     int nextInt() throws IOException {
  107.         return Integer.parseInt(nextToken());
  108.     }
  109.  
  110.     long nextLong() throws IOException {
  111.         return Long.parseLong(nextToken());
  112.     }
  113.  
  114.     double nextDouble() throws IOException {
  115.         return Double.parseDouble(nextToken());
  116.     }
  117.  
  118.     String nextToken() throws IOException {
  119.         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  120.             tokenizer = new StringTokenizer(reader.readLine());
  121.         }
  122.         return tokenizer.nextToken();
  123.     }
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement