第二十八届“和巨耀通杯”NOJ邀请赛

三人团队赛，正好最近在刷PTA，于是一个人报名尝试了一下。

一共AC了三题， Rank28

C. Battle game

签到题

Description:

You are playing a game which you will battle with an enemy. As you don’t want to lose, your total power can’t be lower than your enemy’s. Your power is simply added by the power of your soldiers, and all of your soldiers’ power is exactly aa. Now you have known that your enemy’s total power is bb. You want to know how many soldiers you need in order not to lose the battle.

Input:

A line with two integers a,ba,b, (1≤a,b≤109)(1≤a,b≤109).

Output:

A line with one integer, denotes the minimum number of soldiers you need.

Sample Input:

123 456

Sample Output:

AC代码

#include <iostream>

using namespace std;

int main(){
    int a, b;
    while(cin >> a>> b){
        int ans=1;
        if ( b%a != 0)
            ans= b/a+1;
//            cout << b/a+1<< endl;
        else
            ans = b/a;
//            cout << b/a << endl;
        cout << ans << endl;
    }
    return 0;
}

D. Gomoku

Description:

Alice and Bob are playing a game called Gomoku (a.k.a. Five in a Row). Alice is sente(black, moves first) and Bob is gote(white, moves second). Alice wants to know whether she can win(have five or more consecutive stones of the same color in a diagonal, vertical, or horizontal row) in one step, and now is Alice’s turn. It is guranteed that neither Alice or Bob wins currently. Prohibitions are not considered in this problem.

Input:

The first line contains one integer nn, which denotes the size of the board is n×nn×n.

Next nn lines each has a string of length nn, use @ to represent black, O to represent white, + to represent there’s no stone at that position.

Output:

If Alice can win in one step, output YES, otherwise output NO.

Sample Input:

7
+++O+++
+@+@+++
+O@@@++
+++@+++
+++O@++
++OOOO+
+++++++

Sample Output:

YES

AC代码

#include <iostream>
#include <sstream>
#include <string>
#include <cstdio>
#include <stdlib.h>
const int  maxn = 1e3 + 5;

/*
7
+++O+++
+@+@+++
+O@@@++
+++@+++
+++O@++
++OOOO+
+++++++
*/
using namespace std;

char maze[maxn][maxn];
bool can=false;

const int dirnum = 8;
// -> , 2, <- , 8,
int xdir[dirnum] = {1, 0, -1, 0, 1, -1, -1, 1};
int ydir[dirnum] = {0, 1, 0, -1, 1, 1, -1, -1};

void dfs(int x, int y, int depth, int dir, int plustime){


    if (depth == 5){
        can = true;
//        cout << x << y << endl;
        return;
    }
    if (plustime == 2) return;
    if (maze[x][y] == 'O') return;
    if (!maze[x][y]) return;
    if (can == false){
        int xt = xdir[dir] + x;
        int yt = ydir[dir] + y;
//        cout << "      x:" << xt << " y:"<< yt <<  " " <<  maze[xt][yt] << "plustime:"<< plustime<< endl;
        if (maze[xt][yt] == '+' && plustime==0){
            maze[xt][yt] = '@';
            dfs(xt, yt, depth+1, dir, plustime+1);
            maze[xt][yt] = '+';
        }else if(maze[xt][yt] == '@' ){
            dfs(xt, yt, depth+1, dir, plustime);
        }else return;
    }else return;
}

int main(){
    // 5- 1e3
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cin >>maze[i][j];
    }

//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++)
//            cout << maze[i][j];
//        cout << endl;
//    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if (maze[i][j]== '@'){
//                cout << "test" << "x:" << i << " y:"<< j << " "<<  maze[i][j]<< endl;
                for(int k=0; k<dirnum; k++){
                    int xt = xdir[k] + i;
                    int yt = ydir[k] + j;
                    if (maze[xt][yt]=='@')
//                    cout << "  in " << "x:" << xt << " y:"<< yt << " "<<  maze[xt][yt]<< endl;
                        dfs(xt, yt, 2, k, 0);
                    else if (maze[xt][yt] == '+')
                        dfs(xt, yt, 2, k, 1);
                }
            }
//            else cout << "new" << "x:" << i << " y:"<< j << " "<<  maze[i][j]<< endl;
        }
    }


    if (can) printf("YES\n");
    else printf("NO\n");
    return 0;
}

G. Number

规律题

Description:

0xfaner just learned the factorial today, and the factorial is defined as follows: $x!=1×2×⋯×xx!=1×2×⋯×x$

He found that $10!=362880010!=3628800 $， $20!=2432902008176640000$ , the number of trailing zeros is increasing.

Now 0xfaner wants to know the the number of trailing zeros of n!n!to each given nn .

Input:

The only line contains one integer nn ( 1≤n≤1091≤n≤109 ).

Output:

Print the number of trailing zeros of n!n! .

Sample Input:

Sample Output:

规律题

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    
	public static int solve(int n){
		BigInteger res =  new BigInteger("1");
		for(int i=1;i<=n;i++){
			BigInteger tmp =  new BigInteger(String.valueOf(i));
			res = res.multiply(tmp);
		}
//		System.out.printf("%s\n",res.bitCount());
//		System.out.printf("%s\n",res.bitLength());
//		System.out.printf("%d\n",res.byteValue());
		String s = res.toString();
		int ans = 0;
		for(int j=s.length()-1;j>=0;j--){
			if (s.charAt(j)=='0') ans ++;
			else break;
		}
		return ans;
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		System.out.printf("%d",solve(n));
	}

    
}

执行后一直TLE，于是猜测是否有规律

AC代码

#include <iostream>
typedef long long ll;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    ll n;
    while(cin >> n){
        ll ans = 0;
        while(n){
            ans += n/5;
            n /= 5;
        }
        cout << ans << endl;
    }
    return 0;
}