ABC-113

Author Avatar
ZC 11月 04, 2018
  • 在其它设备中阅读本文章

A - Discount Fare


Time limit : 2sec / Memory limit : 1024MB

Score: 100 points

Problem Statement

There is a train going from Station A to Station B that costs X yen (the currency of Japan).

Also, there is a bus going from Station B to Station C that costs Y yen.

Joisino got a special ticket. With this ticket, she can take the bus for half the fare if she travels from Station A to Station B by train and then travels from Station B to Station C by bus.

How much does it cost to travel from Station A to Station C if she uses this ticket?

Constraints

  • 1≤X,Y≤100
  • Y is an even number.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

If it costs x yen to travel from Station A to Station C, print x.


Sample Input 1

81 58

Sample Output 1

110
  • The train fare is 81 yen.
  • The train fare is 58 ⁄ 2=29 yen with the 50% discount.

Thus, it costs 110 yen to travel from Station A to Station C.


Sample Input 2

4 54

Sample Output 2

31

题解:

很简单。第一张车票+第二张的一半

#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T>
    #define Fur(i,x,y) for(ri i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(ri i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 2122219134
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define l2(n) (ceil(log2(n)))
    #define fast ios::sync_with_stdio(false)
    MB il T ABS(T x){return x>0?x:-x;}
    MB il T MAX(T x,T y){return x>y?x:y;}
    MB il T MIN(T x,T y){return x<y?x:y;}
    MB il T GCD(T x,T y){return y?GCD(y,x%y):x;}
}using namespace ZDY;using namespace std;
#define N 55
int x,y;
int main(){
    cin>>x>>y;
    cout<<db(db(x)+db(y/2.0));
}

B - Palace


Time limit : 2sec / Memory limit : 1024MB

Score: 200 points

Problem Statement

A country decides to build a palace.

In this country, the average temperature of a point at an elevation of x meters is Tx×0.006 degrees Celsius.

There are N places proposed for the place. The elevation of Place i is H**i meters.

Among them, Princess Joisino orders you to select the place whose average temperature is the closest to A degrees Celsius, and build the palace there.

Print the index of the place where the palace should be built.

It is guaranteed that the solution is unique.

Constraints

  • 1≤N≤1000
  • 0≤T≤50
  • −60≤AT
  • 0≤H**i≤105
  • All values in input are integers.
  • The solution is unique.

Input

Input is given from Standard Input in the following format:

N
T A
H1 H2 … HN

Output

Print the index of the place where the palace should be built.


Sample Input 1

2
12 5
1000 2000

Sample Output 1

1
  • The average temperature of Place 1 is 12−1000×0.006=6 degrees Celsius.
  • The average temperature of Place 2 is 12−2000×0.006=0 degrees Celsius.

Thus, the palace should be built at Place 1.


Sample Input 2

3
21 -11
81234 94124 52141

Sample Output 2

3

题解:

模拟

#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T>
    #define Fur(i,x,y) for(ri i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(ri i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 2122219134
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define l2(n) (ceil(log2(n)))
    #define fast ios::sync_with_stdio(false)
    MB il T ABS(T x){return x>0?x:-x;}
    MB il T MAX(T x,T y){return x>y?x:y;}
    MB il T MIN(T x,T y){return x<y?x:y;}
    MB il T GCD(T x,T y){return y?GCD(y,x%y):x;}
}using namespace ZDY;using namespace std;
#define N 1010
int n,a[N],t,k,ap;
db ans=inf,p;
int main(){
    cin>>n>>t>>k;
    Fur(i,1,n){
        scanf("%d",&a[i]);
        p=db(t-db(a[i])*0.006);
        if(ABS(p-k)<ans)ans=ABS(p-k),ap=i;
    }
    cout<<ap<<endl;
}

C - ID


Time limit : 2sec / Memory limit : 1024MB

Score: 300 points

Problem Statement

In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.

City i is established in year Y**i and belongs to Prefecture P**i.

You can assume that there are no multiple cities that are established in the same year.

It is decided to allocate a 12-digit ID number to each city.

If City i is the x-th established city among the cities that belong to Prefecture i, the first six digits of the ID number of City i is P**i, and the last six digits of the ID number is x.

Here, if P**i or x (or both) has less than six digits, zeros are added to the left until it has six digits.

Find the ID numbers for all the cities.

Note that there can be a prefecture with no cities.

Constraints

  • 1≤N≤105
  • 1≤M≤105
  • 1≤P**iN
  • 1≤Y**i≤109
  • Y**i are all different.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
P1 Y1
:
PM YM

Output

Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, …).


Sample Input 1

2 3
1 32
2 63
1 12

Sample Output 1

000001000002
000002000001
000001000001
  • As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.
  • As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.
  • As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.

Sample Input 2

2 3
2 55
2 77
2 99

Sample Output 2

000002000001
000002000002
000002000003

题解:

因为懒惰和想快,就选择了stl

原想用邻接表代替。

但还是想练习一下vector

  1. vector的排序是sort(a.begin(),a.end())

    不用加&

  2. printf("%06d",...);表示如果不满6位前面用0补齐

#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T>
    #define Fur(i,x,y) for(ri i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(ri i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 2122219134
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define l2(n) (ceil(log2(n)))
    #define fast ios::sync_with_stdio(false)
    MB il T ABS(T x){return x>0?x:-x;}
    MB il T MAX(T x,T y){return x>y?x:y;}
    MB il T MIN(T x,T y){return x<y?x:y;}
    MB il T GCD(T x,T y){return y?GCD(y,x%y):x;}
}using namespace ZDY;using namespace std;
#define N 100010
int n,m,a1[N],a2[N];
struct city{
    int id,y;
    friend bool operator <(const city &a,const city &b){
        return a.y<b.y;
    }
};
vector<city> a[N];
int main(){
    cin>>n>>m;
    int p,y;
    Fur(i,1,m){
        scanf("%d%d",&p,&y);
        a[p].push_back((city){i,y});
    }
    Fur(i,1,n)if(!a[i].empty()){
        sort(a[i].begin(),a[i].end());
        Fur(j,0,a[i].size()-1)a1[a[i][j].id]=i,a2[a[i][j].id]=j+1;
    }
    Fur(i,1,m)printf("%06d%06d\n",a1[i],a2[i]);
}

D的话题意太繁琐,懒得看