ICPC 2014 Domestic

A

#include<bits/stdc++.h>
using namespace std;

int x,y,s;

bool input(){
  cin>>x>>y>>s;
  if(x==0&&y==0)return false;
  return true;
}

int pre(int a){
  for(int i=s+100;i>=0;i--){
    if(i*(x+100)/100 == a){
      return i;
    }
  }
  return 0;
}

int solve2(int a,int b){
  a = pre(a);
  b = pre(b);
  if(a==0)return 0;
  if(b==0)return 0;
  return a*(y+100)/100 + b*(y+100)/100;
}

int solve(){
  int tmp = 0;
  for(int i=0;i<s;i++){
    tmp = max(tmp,solve2(i,s-i));
  }
  return tmp;
}

int main(){
  while(input()){
    cout<<solve()<<endl;
  }

}

B
nikollsonさんが通してくれました

C
終わったあと書いたコード（正しい保証はない）
追記：：climpetさんがdiffとってくれました　大丈夫っぽいそうです

#include<bits/stdc++.h>
using namespace std;

const double EPS = 1e-8;
int n,r;

struct S{
  double l,r,h;
};
vector<S> in;
vector<double> check;
void init(){
  in.clear();
  check.clear();
}
void setCheck(double x){
  check.push_back(x+2*EPS);
  check.push_back(x-2*EPS);
}
bool input(){
  cin>>r>>n;
  if(r==0)return false;
  setCheck(0);
  for(int i=0;i<n;i++){
    double l,r,h;
    cin>>l>>r>>h;
    in.push_back(S{l,r,h});
    setCheck(l);
    setCheck(r);
  }
  return true;
}

double y(double x,double t){
  if(abs(x)>r)return -1;
  return t + sqrt(r*r - x*x) - r;
}

bool checkXjudge(double x,double y){
  if(y<0)return true;
  for(int i=0;i<in.size();i++){
    if(in[i].l<x && x< in[i].r){
      if(y<=in[i].h)return true;
    }
  }
  return false;
}

bool judge(double t){
  for(int i=0;i<check.size();i++){
    if(!checkXjudge(check[i],y(check[i],t))){
      return false;
    }
  }
  return true;
}

double solve(double lt,double rt,int nn){
  if(nn==0)return lt;
  double v = (lt + rt)/2;
  if(judge(v)){
    return solve(v,rt,nn-1);
  }else{
    return solve(lt,v,nn-1);
  }
}


int main(){
  while(init(),input()){
    cout<<fixed<<setprecision(10)<<solve(0,100,100)<<endl;
    cerr<<fixed<<setprecision(10)<<solve(0,100,100)<<endl;
  }
}

D

#include<bits/stdc++.h>
using namespace std;

string s;

bool input(){
  cin>>s;
  return s!="#";
}

vector<string> ans;


string conv(string s,int n){
  for(int i=0;i<s.size();i++){
    if(n & (1<<i)){
      if(s[i] == 'z')return "#";
      s[i] = s[i]+1;
    }
  }
  return s;
}


bool judge(string s,string pre){
  for(int i=1;i<26;i++){
    for(int j=0;j<pre.size();j++){
      if(pre[j]=='a'+i){
        pre[j] = 'a'+i-1;
        break;
      }
    }
  }
  return s == pre;
}

void solve(){
  ans.clear();
  for(int i=0;i<(1<<s.size());i++){
    string tmp = conv(s,i);
    if(tmp=="#")continue;
    if(judge(s,tmp)){
      ans.push_back(tmp);
    }
  }
}

void print(){
  cout<<ans.size()<<endl;
  cerr<<ans.size()<<endl;
  sort(ans.begin(),ans.end());
  if(ans.size()<10){
    for(auto i:ans){
      cout<<i<<endl;
    }
    return ;
  }
  for(int i=0;i<5;i++){
    cout<<ans[i]<<endl;
  }
  for(int i=5;i>=1;i--){
    cout<<ans[ans.size()-i]<<endl;
  }
}

int main(){
  while(input()){
    solve();
    print();
  }
}

E

#include<bits/stdc++.h>
using namespace std;
struct S{
  long long to,cost;
};

vector<long long> p;
vector<long long> d;

vector<vector<S>> edge;
vector<long long> use;
void init(){
  p.clear();
  d.clear();
  edge.clear();
  use.clear();
}


bool input(){
  long long n;
  cin>>n;
  if(n==0)return false;
  for(long long i=0;i<n-1;i++){
    long long tmp;
    cin>>tmp;
    p.push_back(tmp);
  }
  for(long long i=0;i<n-1;i++){
    long long tmp;
    cin>>tmp;
    d.push_back(tmp);
  }
  return true;
}



void make_edge(){
  edge.clear();
  edge.resize(p.size()+1);
  for(long long i=0;i<p.size();i++){
    long long c = i+1;
    long long to = p[i]-1;
    edge[c].push_back(S{to,d[i]});
    edge[to].push_back(S{c,d[i]});
  }
}


long long hoge(long long start){
  stack<S> st;
  st.push(S{start,0});
  vector<long long> use1(use.size(),-1);
  while(!st.empty()){
    S now = st.top();st.pop();
    if(use1[now.to]>=0)continue;
    use1[now.to] = now.cost;
    for(long long i=0;i<edge[now.to].size();i++){
      if(use[edge[now.to][i].to]){
        st.push(S{edge[now.to][i].to,now.cost + edge[now.to][i].cost});
      }
    }
  }
  long long ans = 0;
  long long cost = 0;
  for(long long i=0;i<use1.size();i++){
    if(cost<use1[i]){
      cost = use1[i];
      ans = i;
    }
  }
  return ans;
}

long long make_cost(long long start,long long end){
  stack<S> st;
  long long l;
  st.push(S{start,0});
  vector<long long> use1(use.size(),-1);
  while(!st.empty()){
    S now = st.top();st.pop();
    if(use1[now.to]>=0)continue;
    use1[now.to] = now.cost;
    for(long long i=0;i<edge[now.to].size();i++){
      if(use[edge[now.to][i].to]){
        st.push(S{edge[now.to][i].to,now.cost + edge[now.to][i].cost});
      }
    }
  }
  return use1[end];
}


long long make_use(){
  use.clear();
  use.resize(edge.size());
  for(long long i=0;i<edge.size();i++){
    use[i] = (edge[i].size()>1);
  }
  long long res = 0;
  for(long long i=0;i<edge.size();i++){
    for(long long j=0;j<edge[i].size();j++){
      if(use[i] && use[edge[i][j].to]){
        res += edge[i][j].cost;
      }
    }
  }
  long long c = 0;
  for(long long i=0;i<use.size();i++){
    for(long long j=0;j<use.size();j++){
      if(use[i]&&use[j]){
        c = max(c,make_cost(i,j));
      }
    }
  }
  res -= c;
  return res;
}


long long solve(){
  long long ans = 0;
  for(long long i=0;i<d.size();i++){
    ans +=d[i];
  }
  long long tmp = make_use();
  ans += tmp;
  return ans;
}


int main(){
  while(init(),input()){
    make_edge();
    long long tmp = solve();
    cout<<tmp<<endl;
    cerr<<tmp<<endl;

  }
}