AtCoder Regular Contest 062 题解_综合

C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

Time Limit: 2 sec / Memory Limit: 256 MB

Score : 300300 points

Problem Statement

AtCoDeer the deer is seeing a quick report of election results on TV. Two candidates are standing for the election: Takahashi and Aoki. The report shows the ratio of the current numbers of votes the two candidates have obtained, but not the actual numbers of votes. AtCoDeer has checked the report NN times, and when he checked it for the ii-th (1≦i≦N)(1≦i≦N) time, the ratio was Ti:AiTi:Ai. It is known that each candidate had at least one vote when he checked the report for the first time.

Find the minimum possible total number of votes obtained by the two candidates when he checked the report for the NN-th time. It can be assumed that the number of votes obtained by each candidate never decreases.

Constraints

1≦N≦10001≦N≦1000
1≦Ti,Ai≦1000(1≦i≦N)1≦Ti,Ai≦1000(1≦i≦N)
TiTi and AiAi (1≦i≦N)(1≦i≦N) are coprime.
It is guaranteed that the correct answer is at most 10181018.

Input

The input is given from Standard Input in the following format:

NN
T1T1 A1A1
T2T2 A2A2
::
TNTN ANAN

Output

Print the minimum possible total number of votes obtained by Takahashi and Aoki when AtCoDeer checked the report for the NN-th time.

Sample Input 1 Copy

Copy

Sample Output 1 Copy

Copy

When the numbers of votes obtained by the two candidates change as 2,3→3,3→6,42,3→3,3→6,4, the total number of votes at the end is 1010, which is the minimum possible number.

Sample Input 2 Copy

Copy

Sample Output 2 Copy

Copy

It is possible that neither candidate obtained a vote between the moment when he checked the report, and the moment when he checked it for the next time.

Sample Input 3 Copy

Copy

Sample Output 3 Copy

Copy

题意：

给你n时间的人数比例，算出最后的最小人数。

分析：

一个简单思维题，

a b

a1 b1

只要保证a1*x>=a b1*x>=b即可

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input=new Scanner( System.in);long n=input.nextLong();long a=input.nextLong();long b=input.nextLong();for(int i=1;i<n;i++) {// System.out.println("s:"+a+"   "+b);long a1=input.nextLong();long b1=input.nextLong();if(a1>=a&&b1>=b) {a=a1;b=b1;continue;}long d1=a/a1;if(a%a1!=0) d1++;long d2=b/b1;if(b%b1!=0) d2++;//System.out.println("ss:"+d1+"   "+d2);long d=Math.max(d1, d2);a=d*a1;b=d*b1;}System.out.println(a+b);}
}

D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

Time Limit: 2 sec / Memory Limit: 256 MB

Score : 300300 points

Problem Statement

AtCoDeer the deer and his friend TopCoDeer is playing a game. The game consists of NN turns. In each turn, each player plays one of the two gestures, Rockand Paper, as in Rock-paper-scissors, under the following condition:

(※) After each turn, (the number of times the player has played Paper)≦≦(the number of times the player has played Rock).

Each player's score is calculated by (the number of turns where the player wins) ?? (the number of turns where the player loses), where the outcome of each turn is determined by the rules of Rock-paper-scissors.

(For those who are not familiar with Rock-paper-scissors: If one player plays Rock and the other plays Paper, the latter player will win and the former player will lose. If both players play the same gesture, the round is a tie and neither player will win nor lose.)

With his supernatural power, AtCoDeer was able to foresee the gesture that TopCoDeer will play in each of the NN turns, before the game starts. Plan AtCoDeer's gesture in each turn to maximize AtCoDeer's score.

The gesture that TopCoDeer will play in each turn is given by a string ss. If the ii-th (1≦i≦N)(1≦i≦N) character in ss is g, TopCoDeer will play Rock in the ii-th turn. Similarly, if the ii-th (1≦i≦N)(1≦i≦N) character of ss in p, TopCoDeer will play Paper in the ii-th turn.

Constraints

1≦N≦1051≦N≦105
N=|s|N=|s|
Each character in ss is g or p.
The gestures represented by ss satisfy the condition (※).

Input

The input is given from Standard Input in the following format:

ss

Output

Print the AtCoDeer's maximum possible score.

Sample Input 1 Copy

Copy

gpg

Sample Output 1 Copy

Copy

Playing the same gesture as the opponent in each turn results in the score of 00, which is the maximum possible score.

Sample Input 2 Copy

Copy

ggppgggpgg

Sample Output 2 Copy

Copy

For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy earns three victories and suffers one defeat, resulting in the score of 22, which is the maximum possible score.

题意：

给你一串字符串，g表示石头，p表示布，你给出迎战策略，需要任意前缀满足g的个数始终比p多，赢得一分，输失一分，问最后得分？

分析：

这题我也不知道怎么过的，玄学贪心，我就用gpgpgp....应对就过了，我想的是能出布就出布。

后来我又试了ggggppp.....

结果也过了，其实主要思想就是布能出多少就出多少

import java.util.Scanner;import jdk.management.cmm.SystemResourcePressureMXBean;public class Main {public static void main(String[] args) {Scanner input=new Scanner( System.in);String string=input.next();int len=string.length();int ans=0;for(int i=0;i<len;i++){if(i%2==0){if(string.charAt(i)=='p')ans--;}else{if(string.charAt(i)=='g')ans++;}}System.out.println(ans);}
}

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input=new Scanner( System.in);String string=input.next();int len=string.length();int ans=0;for(int i=0;i<=(len+1)/2-1;i++){if(string.charAt(i)=='p'){ans--;}}for(int i=(len+1)/2;i<len;i++){if(string.charAt(i)=='g'){ans++;}}System.out.println(ans);}
}